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
网友评论