剑指offer刷体集(更新中)

题目链接

二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

	//方法一:将每行一维数组进行折半查找
    public  boolean binarySearch(int target,int[] array) {
    	
    	int min = 0;
    	int max = array.length-1;
	    int index = 0;
	    int val = 0;
	    while(min<=max){
	          index = (min+max)/2;
	          val = array[index];
	          if(val == target) {
	              return true;	
	          }
	          if(val > target){
	              max = index - 1 ;
	          }
	          
	          if(val < target){
	              min = index + 1;
	          }
	      }
    	return false;
    }
       
    public  boolean Find(int target, int [][] array) {
    	  int rows = array.length;   	  
    	  for(int i=0;i<rows;i++) {
    		  boolean flag = binarySearch(target,array[i]);   		  
    		  if(flag) {
    			  return true;
    		  }
    	  }	
    	return false;
    }

	//方法二:我是看了这道题的讨论才发现有这种解法，这种解法太巧妙了，
	//这种解法产生的原因：
	//这个二维数组：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序
	//所以就可以，使用这种方法。
	//可以从两个角，出发，
	//①从左下角出发，
	//如果target > array[i][j] 那么j++  ，如果 target < array[i][j] 那么i-- 
	//知道找到  target == array[i][j]，找到就ture没有找到就false；
	//②从右上角出发，和从左下角出发原理基本相似
	public  boolean Find(int target, int [][] array) {
	
		int rows = array.length;
		int cols = array[0].length;
		int i = rows - 1;
		int j= 0;
		
		while(( i>=0 && i<rows ) && ( j>=0 && j<cols ) ) {
			
			if(target > array[i][j]) {
				j++;
			}			
			if(target < array[i][j]) {
				i--;
			}			
			if(target == array[i][j]) {
				return true;
			}
		}	
		return false;
	}

斐波那契数列

题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

public class Solution {
    public int Fibonacci(int n) {
/*
        递归方法
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        return Fibonacci(n-2) + Fibonacci(n-1);
*/
        //非递归
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        int a=0,b=1,val=0;
        for(int i=2;i<=n;i++){
            val = a+b;
            if(i==n)
                break;
            a = b;
            b = val; 
        }
        return val;
    }
}