70. 爬楼梯(简单)

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:
matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
target = 3
输出: true

示例 2:

输入:
matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
target = 13
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix

思路：

与剑指offer5一样，，可以从右上角开始找，这个思路比较简单

思路2

二分思路，未写

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
  //f(n)=f(n-1)+f(n-2)
//本质就是斐波那契数列
class Solution {
    public int climbStairs(int n) {
        int f1 = 0,f2 = 1;
        int f3=0;
        for(int i=1;i<=n;i++){
            f3 = f2+f1;
            f1=f2;
            f2=f3;
        } 
        return f3;
    }
}

//更好理解一点
class Solution {
    public int climbStairs(int n) {
        if(n<=2)
            return n;
        int f1 = 1,f2 = 2;
        int f3=0;
        for(int i=2;i<n;i++){
            f3 = f2+f1;
            f1=f2;
            f2=f3;
        } 
        return f3;
    }
}

//另一种解决方法就是递归
int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}