- 21 Merge Two Sorted Lists
思路：朴素的思想就可以了
可以作为模板的解法：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1) return l2;
if(!l2) return l1;
if(l1->val > l2->val) return mergeTwoLists(l2, l1);
ListNode* ret = l1;
while(l1->next && l2){
if(l1->next->val < l2->val) l1 = l1->next;
else{
ListNode* curr = l2;
l2 = l2->next;
curr->next = l1->next;
l1 = l1->next = curr;
}
}
if(l2) l1->next = l2;
return ret;
}
};
- 22 Generate Parentheses
思路：Backtracking
- 24 Swap Nodes in Pairs
思路：每一次变化需要4个临时节点，画张图出来
- 26 Remove Duplicates from Sorted Array
思路：只用修改前面的，并将最后的vector长度返回就好
- 27 Remove Element
思路：和上一题相同思路
- 28 Implement strStr()
思路：KMP算法和普通算法都看一下
其中KMP算法思路：
回退——到达起点或者前进一步——步步为营
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.size() == 0) return 0;
int needle_size = needle.size();
vector<int> next(needle_size,0);
next[0] = -1;
for(int i = 1,j = -1;i < needle_size;++i){
while(j != -1 && needle[j + 1] != needle[i]) j = next[j];
j = (j == -1) ? (needle[0] == needle[i]) - 1 : j + 1;
next[i] = j;
}
for(int i = 0,j = -1;i < haystack.size();++i){
while(j != -1 && needle[j + 1] != haystack[i]) j = next[j];
j = (j == -1) ? (needle[0] == haystack[i]) - 1 : j + 1;
if(j == needle_size - 1) return i - j;
}
return -1;
}
};
- 29 Divide Two Integers
题意：不使用乘除法以及取模运算来实现除法
思路：位运算。需要考虑边界条件，除数为零或者除法溢出的情况。
