力扣面试经典150题

E 是Easy N 是 Normal，也就是Medium，H 是 Hard

Array / String

1. Merge Sorted Array E

设置答案表ans，设置两个指针i和j，表示当前所指的位置，一开始指针指向表头。比较两个指针所指元素大小，谁小谁先进ans表。如果有一个指针指到了表尾就不比了，直接把剩下没处理完的内容直接放进ans表。

2. Remove Element E

太简单，略过。至于怎么使用O(1)的空间复杂度来进行操作。可以用双指针进行操作。i是表头，j是表尾，如果i表示的元素要被删除，就从j中取一个元素放到i对应的位置。（这样就被删掉了），如果不要被删除，那么让i+1就好。

3. Remove Duplicates from Sorted Array E

这是有序数组，那么一切都好办了。规定一个双指针i和j都指向开头，如果这是重复元素，就移动j，如果不是重复元素，是新元素，那就先把j上的元素放到i处，然后i和j都移动（j是快指针，i是慢指针）

4. Remove Duplicates from Sorted Array II N

这和上一题的区别就是只允许存在一次和两次的区别。改动也就是重复元素的判断。上一题是判断i和i-1是不是相等，这一题是i和i-2是不是相等。

5. Majority Element E

可以使用哈希表，统计每个元素出现的次数，然后输出出现次数最多的元素。如果想省空间复杂度的话可以先排序，然后最中间的那个元素就是结果（因为）

6. Rotate Array N

这一题可以使用数组翻转。比如说 1 2 3 4 5 6 7，移动k下，新数组的[0,k - 1]来源于尾部的k个元素。那么可以做一次翻转（把后面的k个元素放到前面），然后对[0,k - 1]和[k,n - 1]的元素进行调转。（把顺序调整回来）

7. Best Time to Buy and Sell Stock E

不知道为什么现在就出现了dp，我们可以把这个状态记录在dp[i][j]。j=0的时候表示在第i天已经买入股票的收入最大值。j=1的时候就是在第i天卖出股票的收入最大值。

那么dp[i][0] = max(dp[i-1][0],-price[i])。dp[i][1] = max(dp[i-1][1],dp[i][0] + price[i])。初始值dp[0][0] = -price[0],dp[0][1] = 0。

8. Best Time to Buy and Sell Stock II N

上面一题从只可以买一次编程可以买两次。那么dp的的第二维就是有4个状态。买了一个，买了一个卖了一个，买了两个卖了一个，买了两个卖了两个。

dp[i][0] = max(dp[i-1][0],-price[i])。dp[i][1] = max(dp[i-1][1],dp[i][0] + price[i])。dp[i][2] = max(dp[i-2][2],dp[i][1] - prices[i])。dp[i][3] = max(dp[i-1][3],dp[i][2] + price[i])。

9. Jump Game N

这一题看题解似乎是可以用贪心。但我用倒推dp做的，dp[i]记录了可以到达最后结束位置的可能性。dp[最后一个位置]肯定为1，记录一个使dp[k]=1最小的k值，然后依次往后倒，如果nums[i] + i <= k的话就说明可以到达。dp[i] = 1，否则为0，看看dp[0]的取值就好。

10. Jump Game II N

这一题相较于上一题多了一个记录最小步数的。那么这次就用dp[i]表示从0到这里最少几步。这里可以有这样的递推方程对于j属于[i,i+nums[i]],dp[j]=min(dp[j],dp[i]+1)

11. H-Index N

对文章引用进行排序。h指的是什么，是h个index比h高的数，那就从0开始试，如果index[size - h - 1] > h，说明可以往上升。

12. Insert Delete GetRandom O(1) N

O(1)的CURD，空间换时间，用一个额外的哈希表记录是否有重复元素。这个哈希表不记录元素的个数，记录元素在表中的索引。添加的时候在表中添加这个元素，哈希表记录index。删除k，如果k没有，就返回false，如果k有的话，那么找到index。表的index位置替换成表尾元素。删掉表尾元素更换哈希表。在O(1)时间内查询不说，太简单。

13. Product of Array Except Self N

这里为什么不能计算出所有元素的积然后再除本元素呢，是因为可能本元素是0，所以可能有问题。所以可以进行一次前缀后缀积。s[i]记录从0一直积到i的值，[i]记录从最后积到i的值，后面就是s[i-1]*b[i+1]（注意考虑一下边界）

14. Gas Station N

先从0开始走，如果能绕一圈自然是好的，但是如果不能的话，在哪里走不动了，就在哪里的下一站试。为什么呢，比如说0->1->2，到2走不动了，那么从1出发从2出发也是不行的，只能试一下从3出发。这样可以减少搜索的次数。

15. Candy H

分糖果，那么可以进行两次贪心。首先先从左往右走，如果i比i-1大，那么s[i] = s[i-1] + 1，如果小，s[i] = 1。然后从右往左走，如果i比i+1大，那么b[i] = b[i+1] + 1，如果小那么b[i] = 1。最后这个小孩分配的糖果数量是max(s[i],b[i])。首先这样可以保证题目的条件满足，如果是2 1 2的情况，那么就是1，如果是1 2 1的情况，那么就是max（左，右）。如果是3 2 1的情况，那么就以右边 + 1为准，右边+1怎么都比1大。所以这样做是可以保证对的。其次由于是贪心，我们可以保证分配的糖果数量是最少的。

16. Trapping Rain Water H

维护一个单调栈，这里就是记录从[s[i],i]中的元素都满足单调性。（这里是单调递减）。这里说一下单调栈的维护，其实就是比较。如果元素比栈顶大，那么栈顶退出，一直到元素比栈顶小或者栈中没元素了。

如果栈中有元素退栈了，但是栈中元素还是不空，这是发生了什么呢？就是有水背围住了，这个时候可以记录水的数量了。这里套用题解就是：

1
2
3

int currWidth = i - left - 1;
int currHeight = min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;

作者：力扣官方题解
链接：https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

17. Roman to Integer E

模拟即可。对字符串进行遍历。

18. Integer to Roman N

贪心算法，先算有多少个1000，再算900，再算500，再算400，以此类推。然后做字符串的加运算即可，有多少个1000就加多少个’M’。

19. Integer to Roman E

统计连续的非空格字符数。有一种优化方式是从后往前遍历字符串，遇到非空格字符开始计数，计数到遇到空格字符，即为答案。

20. Longest Common Prefix E

找最长公共前缀。就遍历一下即可。比如说第一个单词的第一个字母是A，看看别的单词的第一个字母是不是A，是的话就把A放入答案中，以此类推，直到有差异或者到了一个单词的末尾。

21. Reverse Words in a String N

这道题就是考验对字符串处理的基本功，首先把所有的单词提取出来，然后把单词逆序处理即可。提取出来的办法我想得比较笨，就是str += 非空格元素。遇到空格就代表单词处理完毕了，加入到一个单词表中。

22. Zigzag Conversion N

数学题，首先先计算要用到的行数和列数。

1
2

int route = numRows + (numRows > 1? numRows - 2:0);
int lie = numRows < 2 ? 1 : numRows - 1;

然后分配一下具体的位置。

1
2

if(r < numRows) c[r][lie * p] = s[i];
else c[2 * numRows - r - 2][lie * p + r - numRows + 1] = s[i];

其实就是数学题，建立字符串和Zigzag的映射。

23. Find the Index of the First Occurrence in a String E

可以使用KMP算法进行匹配，但这里没有使用。就是使用朴素匹配的思路就可以。当然用KMP算法会更快。

24. Text Justification

暂时略过。

Two Pointers

25. Valid Palindrome E

设置两个指针i和j，i指向字符串头，j指向字符串尾。i和j相等的话就往内移。不相等返回false。如果i和j相遇了(i >= j)，就可以返回true。

26. Is Subsequence E

这个比字符串匹配要简单一点，设置两个指针i和j，i指向长串，j指向慢串。i和j对应的相等，则i后移j后移，否则就只有i后移。当i移动到最后j没移动到最后就返回false，否则返回true。

27. Two Sum II - Input Array Is Sorted N

设置两个指针i和j，i指向表前，j指向表后。如果s[i]+s[j]大了，那就j–，如果小了i++，如果j比i小了，说明没结果。如果s[i]+s[j]刚刚好，说明结果找到了！

28. Container With Most Water N

设置两个指针i和j，i指向表前，j指向表后。记录ans = min(height[i],height[j]) * (j - i)的最大值。如果s[i] < s[j]，那就i++，否则j–，一直到j < i为止。（贪心+双指针）

29. 3Sum N

基于第27题的题目，其实在第27题的基础上加了一个遍历。遍历1-n为i，然后在i+1~n之间做一次二数之和。

Sliding Window（滑动窗口【单调队列】）

30. Minimum Size Subarray Sum N

首先先规定滑动窗口的范围[j,k]。假设滑动窗口内部的和是p。现在遍历这个数组，下标为i

（1）如果p + a[i] < target，让k = i

（2）p + a[i] = target，这是一个可能的结果，记录一下。

（3）p + a[i] > target。这时候要吐出滑动窗口的元素了。做p -= a[j++]一直到p + a[i] <= target为止。

对所有的可能的结果找最小值。

31. Longest Substring Without Repeating Characters N

首先先规定滑动窗口的范围[j,k]，然后构造一个Hash表来维护不重复性。遍历字符串，下标为i

（1）s[i]不重复，可以扩展k = i。记录一下当前滑动窗口长度。维护滑动窗口长度的最大值。

（2）s[i]重复，j++到不重复为止。

32. Substring with Concatenation of All Words H

首先先规定滑动窗口的范围[j,k]，然后构造一个Hash表来维护不重复性。首先我们直到滑动窗口的移动是按照单词表的元素为基准的。也就是说我们的初始滑动窗口是不同的，假设单词表元素的长度为k，那么从0,1,2…k-1开始都可以。所以说要遍历（0,k-1）。

之后和之前的滑动窗口操作一样。但是每次取字符串都是k个k个去取。

（1）不在单词表里。那么滑动窗口从[i+单词表长度,i+单词表长度]开始。

（2）在单词表里，而且在滑动窗口内没出现过（用std::map来维护）。k+=单词表长度。

（3）在单词表里，而且在滑动窗口内出现过，那就移动j一直到滑动窗口内部没出现过。

33. Minimum Window Substring H

滑动窗口的范围[j,k]，首先遍历一下要判别的串K。看看串内部字母的数量。构建一个hash表记录滑动窗口内部每个字母的数量。然后遍历字符串

（1）没达到要求，滑动窗口向右拓展。

（2）达到要求了，滑动窗口往左尽量收缩，尽量的含义是，收缩到i以致于滑动窗口[i+1,k]不满足要求而[i,k]满足要求，记录答案，维护答案的最小值。

矩阵（大部分就是做模拟）

34. Valid Sudoku N

模拟，首先先把数独构造出来，然后按行按列去检查有无重复项（哈希表）

35. Spiral Matrix N

这道题也是模拟。就是模拟矩阵旋转的过程。旋转可以分为四个部分，左下右上。做几次旋转可以通过min(m,n) + 1这个式子算出。左下右上每次怎么放元素的也可以算出。

36. Rotate Image N

旋转矩阵，其实可以拆成四块去做的。左上到右上，右上到右下，右下到左下，左下到左上。每一次都是四个四个做的，而且可以写出映射。那么矩阵一块有多大呢，一块就是(n/2) * (n+1/2)大，四块的具体的划分也可以说出来。那么就做那么多次的循环交换就好了。

1
2
3
4
5

int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = temp;

37. Set Matrix Zeroes N

维护一个表b，记录哪些元素要设置为0。遍历一遍矩阵，对0元素，其所在行和所在列上所有位置，在表b中设置为1。矩阵遍历完了就统一设置为0。这样做是防止新生成出来的0会干扰操作。

38. Game of Life N

暂时略过。

HashMap（哈希表）

39. Ransom Note E

首先遍历magazine，记录magazine每个元素出现的次数，记录在哈希表中。然后遍历ransomNote，记录ransomNote每个元素出现的次数，出现比magazine多就判定false，没有的话就判定true。

40. Isomorphic Strings E

将两个串进行字数统计，记录在哈希表1和2中，然后排序哈希表1和2，比较哈希表中元素数量是否相同。（当然也可以对哈希表进行再哈希）

41. Word Pattern E

感觉这题并不像E的难度。将句子拆成若干个单词组，然后尝试构建一个字符串对字符的哈希映射，如果出现了哈希冲突，就是false，反之就是true。比如说dog cat cat dog和abba，就可以成功建立 dog-a cat-b的映射，dog cat cat dog和abbc，那么dog可以对a或者c，就产生了冲突，dog cat cat fog和abba，a可以对dog或者fog，也是出现了冲突。（查冲突的方法就是查哈希表的元素是否为空或者是否为不空）

42. Valid Anagram E

构建两个字符串的哈希表，看哈希表是否完全相等。

43. Group Anagrams N

这里本来是想让每组单词之间两两调用42题的API，结果TLE。上网看题解发现可以对字符串做sort，这样互为Anagrams的单词就是一样的。

44. Two Sum E

这里本来可以使用暴力方式，搜索一遍就可以过。但是可以用哈希表。首先构建一个哈希表，然后。遍历数组，对于数组的元素x，希望能找到target-x的存在性，就搜索哈希表即可。

45. Happy Number E

首先我们模拟上述的操作，然后我们用一个哈希表记录操作的结果的循环性，如果结果循环出现，我们知道时遇到了循环，就要返回false。遇到了1就返回true（我们知道如果不是快乐数就是一定遇到了循环，因为在做操作的时候，对于高位数，会单调递减，对于三位数以内的值，最多最多只能到243，所以一定会出现循环）只不过我们知道当遇到4的时候就代表遇到了循环，可以以此为着手进行优化。

46. Contains Duplicate II E

在这里依然使用哈希，但是我哈希表的值记录上一次出现在数组的下标。然后每次出现就使用哈希表的值进行判断。

47. Longest Consecutive Sequence N

做哈希然后找哈希表上连续元素的个数。

Intervals

48. Summary Ranges E

遍历数组。记录连续的区间，记录的方法就是比较当前元素和之前元素的关系，如果满足+1，就不管，不满足+1，就意味着新的区间已经出现了。然后把记录的结果转化成字符串。

49. Merge Intervals N

将区间按照左端递增的方式进行排序，然后每次比较都是比较上一个区间的右端和下一个区间的左端，观察可合并性。如果可合并，就更改右端的值作为一个新的区间。如果不可合并就重新构建新的待合并区间。（最重要的还是排序这一步）

50. Insert Interval N

其实就是把新区间加进去，然后调用一次49。当然还可以直接遍历一遍所有区间，找到合适的位置进行合并。（找位置其实就是插入排序，因为左端的值是递增的，按照左端递增的规律进行插入就好）

51. Minimum Number of Arrows to Burst Balloons N

按照右端递增进行排序。然后取一个p=第一个元素的右端。如果下一个元素的左端比上一个元素的右端要大，就说明不能在一起射了，就只能ans++，p=下一个元素的右端。如果不大，说明可以一起射，就可以不用做任何操作。

Stack

52. Valid Parentheses E

非常典型的Stack问题，括号匹配，如果是左括号，入栈，右括号就和栈顶匹配。

53. Simplify Path N

非常搞人心态的模拟题。首先用一个栈模拟文件夹路径。首先如果遇到了/，就代表该往下或者往上走一步了，如果是一个dot，就啥也不用做，两个dot就退栈，如果都不是，就往栈里push一个新的文件夹名字。其实本题的难dot在dot的处理上，有量个变量k和p（只有dot和不是只有dot）来记录上一级的名字里面是不是只有dot，如果不是只有dot就一律按照普通的名字来。如果遇到了..word.，在遇到第一个dot的时候k++，第二个也是k++，在遇到w的时候就把k=0，p=1。当p=1的时候，再遇到dot都不会k++了。而是保存起来。 反正是一个很折磨的模拟题。

54. Min Stack N

维护最小值的栈。那就维护两个栈，一个是原始的栈，一个是到目前为止最小值的栈。在push的时候，就把要push的值push到原始栈中，要push的值和最小值栈的最小值push到最小值栈中。

55. Evaluate Reverse Polish Notation N

暂时略过。

56. Basic Calculator

力扣的链表数据结构定义：

1
2
3
4
5
6
7
8

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

LinkList

57. Linked List Cycle

双指针。设置一个快指针和慢指针。快指针一次性走两次，慢指针一次性走一次。如果有环，那么快慢指针会碰面，如果没有环，那么快指针马上会指向NULL。（当然要注意边界条件，因为当链表为空或者链表根本只有一个元素不可能有环。）

58. Add Two Numbers

用链表模拟加，很折磨。用数组模拟竖式加法本来就很折磨，更何况链表。构建result表，首先先判断l1和l2指针是不是为空，如果为空的话就默认这是0，不为空的话该是什么是什么（后面移动l1和l2指针也是判断是否为空，为空的话就不用做操作）。然后两个指针对应内容和上一级进位相加。得到这一级加数和进位。加数插入进result表。以此类推，一直到l1和l2都是空。都是空了之后，在result表的队尾加上carry对应的节点。

这题和一般的模拟一样，首先要考虑两个加数不是同一个位的情况。然后还要考虑result表要构造头指针和尾指针。

59. Merge Two Sorted Lists

构建一个res表，然后构建三个指针。i，j，k。i指向链表1，j指向链表2。k指向res表。i比j小，k后面补个i，i往后移。反之k后面补个j，j往后移，一直到i或者j到了尾部，把剩下那个没到尾部的那个表补到k后面

60. Copy List with Random Pointer

深拷贝复制一个链表。那就构建一个老链表结点到新链表结点的映射，新链表构建完了需要完善random指针和next指针。所以之后遍历老链表。假设现在老链表遍历到了k，那么新链表为Hash(k)，那么可以写出Hash(k)->next = Hash(k->next[老链表])[新链表]，巧妙构建了新链表之间的联系。

61. Reverse Linked List II N

详见62，62就是用了61的代码：

62. Reverse Nodes in k-Group H

这一题就是折磨，狠狠地模拟了。这里Sukuna用了一个取巧的方法，用了一个Hash，把链表结点和结点所在的位置做了一次Hash。然后写了一个调换结点的代码。说白了就是对所有的next节点进行了狠狠地替换，代码非常长，算法很好懂，就是代码非常不好写：（注意一下首部的处理）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void reverseBetween(ListNode* head, int left, int right) {
    if(!head) return;
    if(left > 1) {
        //printf("Let %d to %d\n",maps[left-1]->val,maps[right]->val);
        maps[left-1]->next = maps[right];
        //printf("Let %d to %d\n",maps[left]->val,maps[right+1]->val);
        maps[left]->next = maps[right+1];
        for(int i = right;i > left;i--){
            //printf("Let %d to %d\n",maps[i]->val,maps[i-1]->val);
            maps[i]->next = maps[i-1];
        }
        //return maps[1];
    }
    else{
        //printf("Let %d to %d\n",maps[1]->val,maps[right + 1]->val);
        maps[1]->next = maps[right + 1];
        for(int i = right;i > left;i--){
            //printf("Let %d to %d\n",maps[i]->val,maps[i-1]->val);
            maps[i]->next = maps[i-1];
        }
        //return maps[right];
    }
    
}

然后以k个为一组进行替换。最后不足k个的就直接复制过去。

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

ListNode* reverseKGroup(ListNode* head, int k) {
       if(k==1)return head;
       int i = 1;
       ListNode* res = head;
       while(res){
           maps[i] = res;
           res = res->next; 
           i++;
       }
       maps[i]=nullptr;
       i--;
       int total = i;
       int flag = 0;
       for(int j = 1;j + k - 1 <= total;j+=k){
           
           //printf("Do %d %d\n",j,j+k-1);
           reverseBetween(head,j,j+k-1);
           ListNode* head = maps[k];
           while(head){
               //printf("%d ",head->val);
               head = head->next;
           }
           ListNode* res = flag?maps[1]:maps[k];
           flag = 1;
           i = 1;
           while(res){
               maps[i] = res;
               res = res->next; 
               i++;
           }
           i--;
           //printf("\n");
       }
       return maps[1];
   }

63. Remove Nth Node From End of List N

链表的删除。首先计算链表的长度l，然后删除掉l - n + 1上的节点。删除的办法在C语言课上讲过了。首先找到l - n + 2上的节点，然后让l - n + 2指向l - n即可（第l个默认是NULL）这样有个好处就是，不用对空指针进行处理。

但是如果要删除第一个的话，可以直接让head = head->next，就不能找到前一个了。

64. Remove Duplicates from Sorted List II N

构造hash表，然后构造一个新表，把hash表里所有出现次数为1的数插到新表里。

65. Rotate List N

首先要明确一点，rotate的次数 = k % 链表的长度。然后找到最后第k个元素，记作a，第k-1个元素为a-1。然后原链表的头head和尾tail。tail->next = head。a-1->next = NULL。（这里要考虑边界条件，如果k=0，就什么都不用做）

66. Partition List N

构建两个表1和2，小于x的放入1，否则放入2.如果表1或者2是空表，就直接返回表2或者表1.如果不是的话表1末尾->next=表二开头。

67. LRU Cache N

暂且不表。

Binariy Tree

1
2
3
4
5
6
7
8
9
10
11

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

68. Maximum Depth of Binary Tree E

求二叉树最大深度。那就是求左子树和右子树深度最大值+1。（如果是空树的话返回0）

69. Same Tree E

先判空，如果两方有一个是空，返回false，如果两方都是空，返回true。如果都不是空，就看本节点值，左子树和右子树的一致性。(p->val == q->val) && (isSameTree(p->left,q->left)) && (isSameTree(p->right,q->right))

70. Invert Binary Tree E

如果该树为空，那就什么都不用做。如果不空，那就交换左右子树，然后对左右子树递归调用交换函数。

71. Symmetric Tree E

调用一下70，把右子树进行一次调转。然后看左子树和右子树是不是一个树（69）

72. Construct Binary Tree from Preorder and Inorder Traversal N

给定前序排列和中序排列，构建一个树。非常经典的数据结构题。如果排列只有一个，那么就直接返回即可。如果有两个及以上，那首先要知道前序排列的第一个元素，在中序排列的位置，假设为i，那么中序遍历的[0,i-1]就是左子树[i+1,n]是右子树。然后递归构造就好。

73. Construct Binary Tree from Inorder and Postorder Traversal N

还是经典，只不过从前序改成后序，还是一样的做法。只不过是后序排列的最后一个元素，在中序的位置。

74. Populating Next Right Pointers in Each Node II N

这个可以首先构造一个层次的链表数组L。然后假设一个节点r的层数为n，那么L[n]->next = r，L[n] = r。这样子就可以巧妙地构造一个层次表了。

75. Flatten Binary Tree to Linked List N

这个可以用一个很笨的方法，就是先前序遍历，把前序遍历的结果放在一个vector内部，然后遍历vector以分配左右子树指针的朝向。

76. Path Sum E

递归计算。假设target=k，那就计算 左子树存在路径使路径和 == k - val || 右子树存在路径使路径和 == k - val。在递归的时候，有一个函数参数保留k - val的值。

77. Sum Root to Leaf Numbers N

假设root的值是k，那么这个root对应的值可以这么表示，假设父亲传来了两个数，k和p（p是引用）【这相当于编译原理里面的综合变量和传递变量】，如果没有子树了，那么就让p += 10k + val。如果有子树，那么令k = 10k + val。（这样子可以把之前几层的信息传递给最后的叶节点，让叶节点做加法有依据）。可以这么理解：就是有儿子，奖池还在继续，没有儿子了，那么就把奖池兑现。

78. Binary Tree Maximum Path Sum H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maxs = -1000000000;
    int dfs(TreeNode* root,int isroot){
        if(!root) return 0;
        int res1 = dfs(root->left,0);
        int res2 = dfs(root->right,0);
        if(res1 + root->val + res2 > maxs) maxs = res1 + root->val + res2;
        if(max(res1,res2) + root->val > maxs) maxs = max(res1,res2) + root->val;
        if(root->val > maxs) maxs = root->val;
        return max(max(res1,res2),0) + root->val;
    }
    int maxPathSum(TreeNode* root) {
        int k = dfs(root,1);
        return max(maxs,k);
    }
};

其实这个代码用得挺笨，我也不知道我搞了个isroot有啥用。不过在这里解释一下代码是怎么做的。我们假设路径是I型和V型。I型就是直勾勾往下走，V型是在某处拐了个弯。首先先记录一下左子树和右子树的I型路径的最大值，假设为l，r。那么算上本路径的I型路径最大值是$max(l,r)+val$。

那么在考虑V型路径（V型路径就是左右子树两部分构成的I型路径+自己，这样可以组成一个V型路径）：if(res1 + root->val + res2 > maxs) maxs = res1 + root->val + res2;

那么维护一个最大值来记录答案。

79. Binary Search Tree Iterator N

写一个基于二叉树的迭代器。这个非常简单，把二叉树做一次搜索，搜索结果放到stack里。

80. Count Complete Tree Nodes E

左子树节点数 + 右子树节点数 + 1

81. Lowest Common Ancestor of a Binary Tree

最近公共祖先（LCA）。首先维护一个dfs(k)，这个值代表k内部是否存在p和q（我们找公共祖先的节点）。

如果左儿子的dfs和右儿子的dfs都是true，就说明本节点是一个公共祖先。或者本节点就是p或者q，然后左儿子的dfs和右儿子的dfs有一个是true，那也可以说明本节点是一个公共祖先。

Binariy Tree BFS

82. Binary Tree Right Side View N

到了二叉树的层次遍历了。其实还是可以和之前一样，构造一个层次表L，然后做一次dfs(k,n)【代表第k个元素再第n层】然后令L[n] = k即可。

83. Average of Levels in Binary Tree E

计算每一层的平均值。dfs一下，计算每一层的总和和结点数。除一下就好。

84. Binary Tree Level Order Traversal

其实还是可以和之前一样，构造一个层次表L，然后做一次dfs(k,n)【代表第k个元素再第n层】然后令L[n].push_back(k)即可。当然还可以用队列模拟层次遍历（广度优先搜索），这样做不仅要维护一个搜索队列，还要维护一个搜索队列对应的层次队列。

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

class Solution {
public:
    int getDepth(TreeNode* root){
        if(!root) return 0;
        return max(getDepth(root->left),getDepth(root->right)) + 1;
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        int p = getDepth(root);
        vector<vector<int>> res = *new vector<vector<int>>(p);
        queue<int> l;
        queue<TreeNode*> t;
        l.push(1);
        if(root) t.push(root);
        while(!t.empty()){
            TreeNode* k = t.front();
            int i = l.front();
            t.pop();
            l.pop();
            res[i-1].push_back(k->val);
            if(k->left) {t.push(k->left); l.push(i+1);}
            if(k->right){t.push(k->right);l.push(i+1);}
        }
        return res;
    }
};

85. Binary Tree Zigzag Level Order Traversal N

暂不讨论

BST

86. Minimum Absolute Difference in BST E

BST的前序遍历是按照升序排序的。那就先前序遍历，存一下遍历的结果，然后遍历比较即可。

87. Kth Smallest Element in a BST N

第K小元素，那就还是存前序遍历的结果，然后取第k个元素就好。

88. Validate Binary Search Tree N

验证BST的性质，存前序遍历的结果，看是不是前面的比后面的小。

Graph

89. Number of Islands N

求连通分量的题目。首先找到一个1，把所有和这个连通分量一起的1全部改成0（这需要上下左右搜索，搜索的时候要注意边界条件）。再继续找1，以此循环往复。然后答案就是循环往复的次数。

90. Surrounded Regions N

这里是将被围住的O变成X，那么标记和边界的O相同连通分量的O，没被标记的O就说明被围住了，变成X。

91. Clone Graph N

深拷贝一个图。做一个老结点到新节点的Hash。然后对图做一次dfs。假设dfs(k)，那么先查询Hash(k)存在否，不存在的话赋新值，对k每一个链接的节点，做一次dfs。然后把dfs的结果加入到链接表中。如果存在，就什么也不做。最后直接返回Hash(k)。其实还是和之前链表深拷贝一样，做一个老结点到新节点的Hash。

92. Evaluate Division N

暂时不表

93. Course Schedule N

建图。节点是课程号，边是上x课之前要上y课。这里使用邻接表。用E[x]表示所有y->x。这样很好计算入度了，那就是E[x].length。取出一个入度为0的元素，从图中删掉，更新一下邻接表。如果找不到入度为0的元素，但是还是有元素存在，说明有环，返回false。所有元素都可以被处理，返回true。

94. Course Schedule II N

和之前一样，只不过把每一个入度为0的元素从图中删除的顺序记录下来而已。

Graph BFS

95. Snakes and Ladders N

暂且不表

96. Minimum Genetic Mutation

建图，顶点是可能出现的基因序列。边x->y，代表x可以变到y。建图之后然后求步数。求步数的方法可以使用bfs。构建一个结点队列和结点对应的步数队列，做dfs。把初始结点和0加入队列中做搜索，搜索到了返回答案，搜索不到（队列空了）就返回-1。

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
38
39
40
41
42
43
44
45

class Solution {
public:    
    int minMutation(string start, string end, vector<string>& bank) {
        unordered_set<string> cnt;
        unordered_set<string> visited;
        char keys[4] = {'A', 'C', 'G', 'T'};        
        for (auto & w : bank) {
            cnt.emplace(w);
        }
        if (start == end) {
            return 0;
        }
        if (!cnt.count(end)) {
            return -1;
        }
        queue<string> qu;
        qu.emplace(start);
        visited.emplace(start);
        int step = 1;
        while (!qu.empty()) {
            int sz = qu.size();
            for (int i = 0; i < sz; i++) {
                string curr = qu.front();
                qu.pop();
                for (int j = 0; j < 8; j++) {
                    for (int k = 0; k < 4; k++) {
                        if (keys[k] != curr[j]) {
                            string next = curr;
                            next[j] = keys[k];
                            if (!visited.count(next) && cnt.count(next)) {
                                if (next == end) {
                                    return step;
                                }
                                qu.emplace(next);
                                visited.emplace(next);
                            }
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }
};

97. Word Ladder

和96一样的bfs。暂且不表。

Trie（字典树）

98. Implement Trie (Prefix Tree)

字典树就是前缀树，通过查前缀来判断是不是有。那就构建下面的26叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class TrieNode {
public:
    char c;
    vector<TrieNode*> list;
    bool end;
    TrieNode(char c) {
        this->c = c;
        list = vector<TrieNode*>(26);
        end = false;
    }
    // for root
    TrieNode() {
        list = vector<TrieNode*>(26);
        end = false;
    }
};

比如说插入了单词cat，那么从字典树头开始在头的list[3]建立一个新的结点，c=’c’，然后再在这个结点的list[1]建立一个新的结点，c=’a’。最后在这个新的结点的list[‘t’-‘a’]建立一个新的结点，标记end=true，就是说有一个单词在这里结束了。

然后查cat的存在性就是按照上面的逻辑去查。如果走到某一步节点为空，说明肯定不对，如果走完了前缀存在。（如果end=true，说明这个单词也存在）这就是字典树，一个26叉树，树中有一个end标记代表有一个完整的单词的存在。

99. Design Add and Search Words Data Structure N

是98的字典树的应用。

100. Word Search II H

暂且不表。

Backtracking（回溯，其实也是一种搜索）

101. Letter Combinations of a Phone Number N

构建dfs(stage,target,str)。如果stage == target，说明结束了，可以写入到res数组。如果是stage < target，说明还要继续往下搜索。那么str += 所有有可出现的字母，然后搜索k次 dfs(stage+1,target,str’)（k=所有可能出现的字母数量）

102. Combination N

还是构建dfs(cur,n,k,temp)cur是当前所选的位置，n是个数，k是组合的个数。如果temp.size() == k，那么temp是一个正确的答案，return。然后在考虑选择cur和不选择cur，两个问题上做搜索。一个是temp.push(cur)之后在做dfs(cur+1,n,k,temp)，做完这一部分搜索回溯之后 ，然后temp.pop()在做dfs(cur+1,n,k,temp)。

这里涉及到n的问题，这里就要对不满足n的要求的做一次剪枝。如果当前temp.size()+n-cur+1 < k，也就是说剩下的所有元素全放进去都不够k个的，那就趁早结束，不做了。

103. Permutations N

涉及选不选的问题。还是构建dfs(p,n,temp,tag)，用tag数组标记访问的情况。如果p == n，说明搜索到了终点。如果p < n，那么就在把所有tag=0的元素放入搜索中。首先找一个tag=0的数据，然后令tag=1，temp加入这个数，做dfs(p+1,n,temp,tag)，结束搜索，也就是回溯后tag=0，temp丢出来。

104. Combination Sum N

还是搜索。dfs(now,target,index)。搜索是对数组的每一项进行选取（dfs(now.push(x),target-x,index+1)）和不选取（dfs(now,target,index+1)）的搜索。搜索到的话就是target=0。

然后可以进行剪枝，就是index = nums.size()的话，就没必要继续做了，还有target<0，也没必要继续做了。

105. N-Queens II H

太经典了，暂且不表。

106. Generate Parentheses N

还是搜索，dfs(l,r,str,n)。对l和r构成的空间组进行搜索，要么加一个(，要么加一个)。dfs(l+1,r,str+’(‘),dfs(l,r+1,str+’)’)。搜索到了就是l=r=n。

还可以进行剪枝。如果l > n，r > n，l > r，都是不可以的。

107. Word Search N

找存不存在word。dfs(pos,l,n)。上下左右搜索没有被搜索过的位置。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

class Solution {
public:
    int m;
    int n;
    int w;
    int hashset[130];
    int b(int i,int j){
        return i*n + j;
    }
    void p(int k,int& i,int& j){
        i = k / n;
        j = k % n;
    }
    bool dfs(int k,int q,string word,vector<vector<char>>& board,vector<int> tag){
        if(q == w - 1) return true;
        int i,j;
        p(k,i,j);
        if(i > 0 && tag[b(i-1,j)] == 0 && board[i-1][j] == word[q+1]){
            tag[b(i-1,j)] = 1;
            if(dfs(b(i-1,j),q+1,word,board,tag)) return true;
            tag[b(i-1,j)] = 0;
        }
        if(i < m - 1 && tag[b(i+1,j)] == 0 && board[i+1][j] == word[q+1]){
            tag[b(i+1,j)] = 1;
            if(dfs(b(i+1,j),q+1,word,board,tag)) return true;
            tag[b(i+1,j)] = 0;
        }
        if(j > 0 && tag[b(i,j-1)] == 0 && board[i][j-1] == word[q+1]){
            tag[b(i,j-1)] = 1;
            if(dfs(b(i,j-1),q+1,word,board,tag)) return true;
            tag[b(i,j-1)] = 0;
        }
        if(j < n - 1 && tag[b(i,j+1)] == 0 && board[i][j+1] == word[q+1]){
            tag[b(i,j+1)] = 1;
            if(dfs(b(i,j+1),q+1,word,board,tag)) return true;
            tag[b(i,j+1)] = 0;
        }
        return false;
    }
    
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        w = word.size();
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                hashset[board[i][j]]++;
            }
        }
        for(int i = 0;i < w;i++){
            if(--hashset[word[i]] < 0) return false;
        }
        vector<int> tag(m*n);
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(board[i][j] == word[0]){
                    tag[b(i,j)] = 1;
                    if(dfs(b(i,j),0,word,board,tag)) return true;
                    tag[b(i,j)] = 0;
                } 
            }
        }
        return false;
    }
};

这样子会超时，要加一个hash的判断。比如说单词出现了N，但是matrix里一个N都没有，就可以直接剪枝了。

Divide & Conquer（分治）

108. Convert Sorted Array to Binary Search Tree E

有序数组转化成BST。那就做分治。设置一个constructor，输入一个有序数组返回一个BST。那就c[0,n] = {val = c[n / 2],left = c[0, n / 2 - 1],right = [n / 2 + 1,n]}

109. Sort List N

为链表排序。那就先用快慢指针找到链表的中间，然后做一次分支排序。l1 = sort(head),l2 = sort(slow).l = merge(l1,l2)。merge的办法是构建一个新的链表，方法参考题59。

110. Construct Quad Tree N

暂且不表

111. Merge k Sorted Lists H

假设有k个list。（力扣的测试集很弱，你按照顺序merge k次也可以过）

可以只用merge logk 级的次数。就是做分治。把merge k次的任务分解成。merge[0,k/2]和merge[k/2+1,k]两个子问题+对于子问题的结果进行一次merge。

Kadane’s Algorithm

112. Maximum Subarray N

动态规划。dp[n] = max[a[n],dp[n-1] + a[n]] 要么接着拿，要么重开。

113. Maximum Sum Circular Subarray N

动态规划，正常操作：dp[n] = max[a[n],dp[n-1] + a[n]]。现在有不涉及到循环的一个最大值max(dp[n])

现在考虑涉及到循环的最大值。固定最右边的元素，找到左边的元素。首先记最大前缀和l[k] = max(l[k-1],l1+l2+…lk)

假设右边的元素选了k个。那么左边的元素是n-k个，假设dp1[k] = (ln+ln-1+…l_k + l[n-k])

那么答案是max(max(dp[n]),max(dp1[n]))

Binary Search（二分搜索）

114. Search Insert Position E

二分搜索。b(0,n-1,target). if a[mid] < target,l = mid + 1,ans = mid. else r = mid - 1.

115. Search a 2D Matrix N

把矩阵展开成向量形式进行二分搜索。

116. Find Peak Element N

如果mid比mid+1位置的元素小，说明答案很有可能是在右边。反之，说明答案很有可能在左边。然后以此为逻辑二分查找即可。

117. Search in Rotated Sorted Array N

二分查找，但是这个查找相较于其他查找不同的是，数组分成两部分[A][B]。如果nums[mid] >= nums[0]。就说明mid在A区。如果target >= nums[0] 并且 target < nums[mid]。就说明target在A区mid左侧。否则target在A区mid右侧或者B区。

如果mid在B区。那么需要保证target > nums[mid]并且target <= nums[n-1]才能保证target在B区mid右侧。

118. Find First and Last Position of Element in Sorted Array N

先二分查找，找到一个位置k，然后再往左往右遍历。

119. Find Minimum in Rotated Sorted Array N

在这样的旋转表里找最小值。还是一样分成两部分[A][B]，我们找B区第一个。如果nums[mid] < nums[r]，则说明mid在B区。那就应该在左边找。那就令r = mid（因为mid可能是B区第一个）。的否则l = mid + 1.

120. Median of Two Sorted Arrays H

想不到特别好的办法，我这里用的是朴素思考。

Heap（堆）

堆是一种有序队列。在C++的STL里有一个数据结构满足堆的要求，这里不需要我们搓轮子了。（下面叫优先队列）

1
2
3
4
5

/*
    第三个参数是自己写的cmp函数。
    剩下的用法就是和队列一样
*/
priority_queue<int, vector<int>, greater<int>>

121. Kth Largest Element in an Array N

放进所有元素，pop K-1个元素，取队列的top

122. IPO H

这一题就是贪心。因为确保了最小投入资本capital是递增的。所以可以先找到所有满足的最小资本数 <= 持有资本数的项目。然后按照净利润递减的顺序放入优先队列里，每一次取出优先队列的最大值作为净利润，更新持有资本 = 之前持有资本 + 净利润。

123. Find K Pairs with Smallest Sums

找到K个最小的pair。下面给一个使用这个STL，自定义比较函数的例子：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51

struct lis {
    vector<int> p; // 存储的值
    vector<int> w; // 相对数组的位置
};
struct compare {
    bool operator()(lis a, lis b) { return a.p[0] + a.p[1] > b.p[0] + b.p[1]; }
};
class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2,
                                       int k) {
        priority_queue<lis, vector<lis>, compare> que;
        int m = nums1.size(), n = nums2.size();
        // 先把第1行的处理好
        for (int i = 0; i < min(m, k); i++) {
            vector<int> temp;
            vector<int> temp1;
            temp.push_back(nums1[i]);
            temp.push_back(nums2[0]);
            // printf("1 push %d %d %d %d\n", i, 0, nums1[i], nums2[0]);
            temp1.push_back(i);
            temp1.push_back(0);
            lis l;
            l.p = temp;
            l.w = temp1;
            que.push(l);
        }
        // 取一个放一个。 取一个x，y。放一个x，y + 1
        vector<vector<int>> p;
        while (k-- && !que.empty()) {

            lis r = que.top();
            que.pop();
            vector<int> temp;
            vector<int> temp1;
            p.push_back(r.p);
            if (r.w[1] + 1 < n) {
                temp.push_back(nums1[r.w[0]]);
                temp.push_back(nums2[r.w[1] + 1]);
                temp1.push_back(r.w[0]);
                temp1.push_back(r.w[1] + 1);
                lis l;
                l.p = temp;
                l.w = temp1;
                que.push(l);
            }
        }

        return p;
    }
};

124. Find Median from Data Stream H

找中位数。那就构建一个递增的优先队列和一个递减的优先队列。这两个优先队列分别记录大于中位数的数和小于中位数的数。还要保证小于中位数的数量和大于中位数的数量差不多一致。

Bit Manipulation（位运算）

125. Add Binary E

位运算没有任何算法，就是纯模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int n = max(a.size(), b.size()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.size() ? (a.at(i) == '1') : 0;
            carry += i < b.size() ? (b.at(i) == '1') : 0;
            ans.push_back((carry % 2) ? '1' : '0');
            carry /= 2;
        }

        if (carry) {
            ans.push_back('1');
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};

126. Reverse Bits E

先转化成二进制，在reverse一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> temp;
    uint32_t reverseBits(uint32_t n) {
        for(int i = 0;i < 32;i++){
            //printf("Push back %d\n",n%2);
            temp.push_back(n % 2);
            n /= 2;
        }
        uint32_t res = 0;
        uint32_t j = 1;
        for(int i = 31;i >= 0;i--){
            res += (j * temp[i]);
            //printf("get %d\n",temp[i]);
            j *= 2;
        }
        return res;
    }
};

127. Number of 1 Bits E

一直÷2，然后找÷2的余数为1的次数。

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int hammingWeight(int n) {
        int res = 0;
        while(n > 0){
            res += (n % 2);
            n /= 2;
        }
        return res;
    }
};

128. Single Number E

根据a ^ a = 0的定律。对所有数异或在一起。剩下的那个数就是唯一一个。

129. Single Number II N

这个比较搞。可以计算每一位出现1的次数。如果这一位出现1的次数 mod 3不为0，说明只出现1次的那个元素这一位为1.（看力扣题解好像可以用状态机来表示，感觉很酷）

130. Bitwise AND of Numbers Range N

脑筋急转弯。对于按位与，我们知道，与里面出现一次0，那最终的答案就一定是0了。所以我们就可以推出，答案是m和n的二进制形态的公共前缀。

Math

131. Palindrome Number E

回文数字。如果是负数就一定是错的。如果是正数的话可以构造逆数字，看看逆数字是不是和正数字一样。假设x的最后一位是k，那么令逆数字 = 逆数字 * 10 + k。

132. Plus One E

模拟加。这里需要注意万一全部为9的情况。

133. Factorial Trailing Zeroes N

0的个数，大家知道0 是由 2 和 5构成的。2明显很充裕，那就是看项目中5因数的个数。（25算两个，125算三个，625算四个）

134. Sqrt(x) E

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int mySqrt(int x) {
        for(int i = 1;i < 46341;i++){
            if(i * i > x) return i - 1;
        }
        return 46340;
    }
};

135. Pow(x, n) N

快速幂算法。这里直接搬题解的。基于x^n + x^n = x^{2n}的道理快速算出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    double quickMul(double x, long long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/powx-n/solutions/238559/powx-n-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

136. Max Points on a Line H

暂且不表

1D DP（一维动态规划）

动态规划就需要把dp递推方程给出来。给出dp递推方程就好办了。

137. Climbing Stairs E

dp[n] = dp[n-1] + dp[n-2] dp[1] = 1,dp[2] = 2

138. House Robber N

对于第n个要么偷，要么不偷（那就算上第n-1个）。可以写出

dp[n] = max(dp[n-2]+a[n],dp[n-1])
dp[1] = a[1]
dp[2] = max(a[1],a[2])

139. Word Break N

dp[0] = true. 如果有个单词，长度为k，单词的最后一位刚好到n处，那么dp[n] = dp[n-k]。（这个的做法就是遍历n，然后从n往后推1，2，3….，k个字母，看构不构成单词，如果一个都构成不了，那就是false）

140. Coin Change N

首先令dp[i] = 114514。那么dp[i] = min(dp[i],dp[i-coin[i]]+1)

141. Longest Increasing Subsequence N

dp[0] = 1. 对于所有a[n] > a[k] dp[n] = max(dp[n],dp[k] + 1)，然后找到最大的dp

对于dp，其递推方程的数据来源可以是一个数据（之前一个，之前两个）；也可以一组数据中最大的或者是最小的。

142. Triangle N

dp[0][0] = a[0][0]
dp[i][0] = dp[i-1][0] + a[i][0]
dp[i][i] = dp[i-1][i-1] + a[i][i]
dp[i][k] = min(dp[i-1][k-1],dp[i-1][k]) + a[i][k]

143. Minimum Path Sum N

dp[0][0] = a[0][0]
dp[i][0] = a[i][0] + dp[i-1][0]
dp[0][i] = a[0][i] + dp[0][i-1]
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + a[i][j]

144. Unique Paths II N

dp[0][0] = 1
dp[i][0] = 有阻碍？0 : (上一个有无阻碍？0：dp[i-1][0])
dp[0][i] = 有阻碍？0 : (左一个有无阻碍？0：dp[0][i-1])
dp[i][j] = 有阻碍？0 : (上一个有无阻碍？0：dp[i-1][j]) + (左一个有无阻碍？0：dp[i][j-1])

145. Longest Palindromic Substring N

暂时不表

146. Interleaving String N

首先看两个字符串的长度，长度不等是不可能成立的。

dp[0][0] = T
dp[i][j] = (dp[i-1][j] & s1[i-1] = s3[i+j-1]) | (dp[i][j-1] & s2[j-1] = s3[i+j-1])

解释：dp[i][j]解释了s3[i+j-1]可以被s1[0…i-1]和s2[0…j-1]构造。

147. Edit Distance N

D[i][j]=min(D[i][j−1]+1,D[i−1][j]+1,D[i−1][j−1])=1+min(D[i][j−1],D[i−1][j],D[i−1][j−1]−1)
​D[i][j]=1+min(D[i][j−1],D[i−1][j],D[i−1][j−1])

解释：D[i][j]是A[0..i]到B[0…j]的编辑距离。

148. Best Time to Buy and Sell Stock III H

1
2
3
4
5
6
7
8
9
10
11

p[0] = -prices[0]; // buy once
p[1] = 0; // buy 1 sell 1
p[2] = -prices[0]; // buy 2 sell 1
p[3] = 0; // buy 2 sell 2
for(int i = 1;i < s;i++){
    p[0] = max(p[0],-prices[i]); // for buy 1 when buy once?
    p[1] = max(p[1],p[0]+prices[i]);
    p[2] = max(p[2],p[1]-prices[i]);
    p[3] = max(p[3],p[2]+prices[i]);
    //printf("%d %d %d %d %d\n",prices[i],p[0],p[1],p[2],p[3]);
}

149. Best Time to Buy and Sell Stock IV H

从2次到k次，很快能能找到关系，从4个状态到2k个状态

1
2
3
4
5
6
7
8
9
10

for(int i = 1;i <= k;i++){
    p[2 * i - 1] = -prices[0];
    p[2 * i + 0] = 0;
}
for(int j = 1;j < s;j++){
    for(int i = 1;i <= k;i++){
        p[2 * i - 1] = max(p[2 * i - 1],p[2 * i - 2] - prices[j]);
        p[2 * i + 0] = max(p[2 * i + 0],p[2 * i - 1] + prices[j]);
    }
}

150. Maximal Square

dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1（dp为为1的边长）

这里我做了个很复杂的写法，贴在这里算了

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int dp[305][305];
        dp[0][0] = matrix[0][0] - '0';
        for(int i = 1;i < n;i++){
            dp[0][i] =matrix[0][i] - '0';
        }
        for(int i = 1;i < m;i++){
            dp[i][0] = matrix[i][0] - '0';
        }
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                if(matrix[i][j] == '0'){
                    dp[i][j] = 0;
                }
                else{
                    int flag = 1;
                    int n = dp[i-1][j-1];
                    int p = 0,q = 0;
                    for(int k = 0;k < n;k++){
                        if(matrix[i][j-1-k] == '0'){
                            flag = 0;
                            
                            break;
                        }
                        p = k + 1;
                    }
                    //p = min(p+1,n);
                    for(int k = 0;k < n;k++){
                        if(matrix[i-1-k][j] == '0'){
                            flag = 0;
                            break;
                        }
                        q = k + 1;
                    }
                    //q = min(q+1,n);
                    if(flag) dp[i][j] = dp[i-1][j-1] + flag;
                    else dp[i][j] = min(p,q) + 1;
                }
            }
        }
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                printf("%d ",dp[i][j]);
            }
            printf("\n");
        }
        int ma = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                ma = max(ma,dp[i][j]);
            }
        }
        return ma*ma;
    }
};