Day6 合并两个排序的链表+青蛙跳台阶问题+二维数组中的查找

TODO:
再做，二维数组中的查找

一、合并两个排序的链表(简单)

就很简单

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* l = new ListNode(0);
        ListNode* head = l;
        while(l1 &&l2){
            if(l1->val < l2->val){
                l->next = l1;
                l1 = l1->next !=nullptr? l1->next:nullptr;
            }else if(l1->val >= l2->val){
                l->next = l2;
                l2 = l2->next != nullptr?l2->next:nullptr;
            }
            l = l->next;
        }
        if(l1 ||l2)
        l -> next = l1==nullptr?l2:l1;
        return head->next;
    }
};

二、 剑指 Offer 10- II. 青蛙跳台阶问题（简单）

就很简单，注意0台阶的时候返回1和取模就好。

class Solution {
public:
    int numWays(int n) {
        int a = 1, b = 2;
        if(n == 0) return 1;
        if(n == 1) return a;
        if(n == 2) return b;
        for(int i = 3; i <= n; i++){
            int t = a;
            a = b;
            b = (a + t)%1000000007;
        }
        return b;

    }
};

三、剑指 Offer 04. 二维数组中的查找（中等）

没做出来
本来应该是个简单题，思路没有理清楚。
一定要灵活！！！
从左上不行那就试试右上！
如果目标值比第一个元素小那一定是往左走，如果比它大一定是
如果目标值是13那么搜索路径是:

可以证明这种方法不会错过目标值

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
      int n = matrix.size();
      if(n ==0) return false; 
      int m = matrix[0].size();
      if( m==0) return false;
      int i=0,j =m-1;
      while(i < n && j >=0){
          if(matrix[i][j] == target) return true;
          else if(matrix[i][j] < target){i++;}
          else{j--;}
      }
      return false;
    }
};

不知道为啥把1换成2，leetcode上运行时间就从20ms变成了32ms...

image.png