少女祈祷中...

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

Array / String

  1. Merge Sorted Array E

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

  1. Remove Element E

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

  1. Remove Duplicates from Sorted Array E

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

  1. Remove Duplicates from Sorted Array II N

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

  1. Majority Element E

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

  1. Rotate Array N

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

  1. 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。

  1. 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])。

  1. Jump Game N

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

  1. Jump Game II N

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

  1. H-Index N

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

  1. Insert Delete GetRandom O(1) N

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

  1. Product of Array Except Self N

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

  1. Gas Station N

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

  1. 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大。所以这样做是可以保证对的。其次由于是贪心,我们可以保证分配的糖果数量是最少的。

  1. 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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

  1. Roman to Integer E

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

  1. Integer to Roman N

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

  1. Integer to Roman E

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

  1. Longest Common Prefix E

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

  1. Reverse Words in a String N

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

  1. 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的映射。

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

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

  1. Text Justification

暂时略过。

Two Pointers

  1. Valid Palindrome E

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

  1. Is Subsequence E

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

  1. Two Sum II - Input Array Is Sorted N

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

  1. 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为止。(贪心+双指针)

  1. 3Sum N

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

Sliding Window(滑动窗口【单调队列】)

  1. 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为止。

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

  1. Longest Substring Without Repeating Characters N

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

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

(2)s[i]重复,j++到不重复为止。

  1. 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一直到滑动窗口内部没出现过。

  1. Minimum Window Substring H

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

(1)没达到要求,滑动窗口向右拓展。

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

矩阵(大部分就是做模拟)

  1. Valid Sudoku N

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

  1. Spiral Matrix N

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

  1. 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;
  1. Set Matrix Zeroes N

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

  1. Game of Life N

暂时略过。

HashMap(哈希表)

  1. Ransom Note E

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

  1. Isomorphic Strings E

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

  1. 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,也是出现了冲突。(查冲突的方法就是查哈希表的元素是否为空或者是否为不空)

  1. Valid Anagram E

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

  1. Group Anagrams N

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

  1. Two Sum E

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

  1. Happy Number E

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

  1. Contains Duplicate II E

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

  1. Longest Consecutive Sequence N

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

Intervals

  1. Summary Ranges E

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

  1. Merge Intervals N

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

  1. Insert Interval N

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

  1. Minimum Number of Arrows to Burst Balloons N

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

Stack

  1. Valid Parentheses E

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

  1. 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++了。而是保存起来。 反正是一个很折磨的模拟题。

  1. Min Stack N

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

  1. Evaluate Reverse Polish Notation N

暂时略过。

  1. 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) {}
* };
*/
  1. Linked List Cycle

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

  1. Add Two Numbers

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

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

  1. 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后面

  1. Copy List with Random Pointer

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

  1. Reverse Linked List II N

详见62,62就是用了61的代码:

  1. 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];
}
  1. 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,就不能找到前一个了。

  1. Remove Duplicates from Sorted List II N

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

  1. Rotate List N

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

  1. Partition List N

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

  1. 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) {}
* };
*/
  1. Maximum Depth of Binary Tree E

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

  1. Same Tree E

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

  1. Invert Binary Tree E

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

  1. Symmetric Tree E

调用一下70,把右子树进行一次调转。然后看左子树和右子树是不是一个树(69)

  1. Construct Binary Tree from Preorder and Inorder Traversal N

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

  1. Construct Binary Tree from Inorder and Postorder Traversal N

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

  1. Populating Next Right Pointers in Each Node II N

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

  1. Flatten Binary Tree to Linked List N

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

  1. Path Sum E

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

  1. Sum Root to Leaf Numbers N

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

  1. 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;

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

  1. Binary Search Tree Iterator N

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

  1. Count Complete Tree Nodes E

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

  1. Lowest Common Ancestor of a Binary Tree

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

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

Binariy Tree BFS

  1. Binary Tree Right Side View N

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

  1. Average of Levels in Binary Tree E

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

  1. 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;
}
};
  1. Binary Tree Zigzag Level Order Traversal N

暂不讨论

BST

  1. Minimum Absolute Difference in BST E

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

  1. Kth Smallest Element in a BST N

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

  1. Validate Binary Search Tree N

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

Graph

  1. Number of Islands N

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

  1. Surrounded Regions N

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

  1. Clone Graph N

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

  1. Evaluate Division N

暂时不表

  1. Course Schedule N

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

  1. Course Schedule II N

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

Graph BFS

  1. Snakes and Ladders N

暂且不表

  1. 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;
}
};
  1. Word Ladder

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

Trie(字典树)

  1. 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标记代表有一个完整的单词的存在。

  1. Design Add and Search Words Data Structure N

是98的字典树的应用。

  1. Word Search II H

暂且不表。

Backtracking(回溯,其实也是一种搜索)

  1. Letter Combinations of a Phone Number N

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

  1. 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个的,那就趁早结束,不做了。

  1. 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丢出来。

  1. 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,也没必要继续做了。

  1. N-Queens II H

太经典了,暂且不表。

  1. 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,都是不可以的。

  1. 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(分治)

  1. 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]}

  1. Sort List N

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

  1. Construct Quad Tree N

暂且不表

  1. 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

  1. Maximum Subarray N

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

  1. 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(二分搜索)

  1. Search Insert Position E

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

  1. Search a 2D Matrix N

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

  1. Find Peak Element N

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

  1. 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右侧。

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

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

  1. Find Minimum in Rotated Sorted Array N

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

  1. Median of Two Sorted Arrays H

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

Heap(堆)

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

1
2
3
4
5
/*
第三个参数是自己写的cmp函数。
剩下的用法就是和队列一样
*/
priority_queue<int, vector<int>, greater<int>>
  1. Kth Largest Element in an Array N

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

  1. IPO H

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

  1. 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;
}
};
  1. Find Median from Data Stream H

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

Bit Manipulation(位运算)

  1. 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;
}
};
  1. 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;
}
};
  1. 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;
}
};
  1. Single Number E

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

  1. Single Number II N

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

  1. Bitwise AND of Numbers Range N

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

Math

  1. Palindrome Number E

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

  1. Plus One E

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

  1. Factorial Trailing Zeroes N

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

  1. 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;
}
};
  1. 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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
  1. Max Points on a Line H

暂且不表

1D DP(一维动态规划)

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

  1. Climbing Stairs E

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

  1. 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])

  1. Word Break N

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

  1. Coin Change N

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

  1. Longest Increasing Subsequence N

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

对于dp,其递推方程的数据来源可以是一个数据(之前一个,之前两个);也可以一组数据中最大的或者是最小的。

  1. 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]

  1. 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]

  1. 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])

  1. Longest Palindromic Substring N

暂时不表

  1. 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]构造。

  1. 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]的编辑距离。

  1. 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]);
}
  1. 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]);
}
}
  1. 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;
}
};