代码随想录算法训练营第36期 last day

标签：last int res 随想录 36 height vector dp size

最后一次更新，之后去复习专业课和简历

583两个字符串的删除操作

自己做出来了：

Code:

1. class Solution {
2. public:
3. //找到公共子序列的最大长度dp 最小步数=串1.size-dp+串2.size-dp
4.     int minDistance(string word1, string word2) {
5.         vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));
6.         dp[0][0]=0;
7.         for(int i=1;i<=word1.size();i++){
8.             for(int j=1;j<=word2.size();j++){
9.                 if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
10.                 else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
11.             }
12.         }
13.         return word1.size()+word2.size()-2*dp[word1.size()][word2.size()];
14.     }
15. };

72编辑距离

没思路，明天学。积累经验

拓展思维：word2转变到word1也可以。

别人的删，就相当于我的增。Dp[i][j]=dp[i][j-1]+1

1. class Solution {
2. public:
3.     int minDistance(string word1, string word2) {
4.         vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));
5.         for(int i=0;i<=word1.size();i++) dp[i][0]=i;
6.         for(int i=0;i<=word2.size();i++) dp[0][i]=i;
7.         for(int i=1;i<=word1.size();i++){
8.             for(int j=1;j<=word2.size();j++)
9.             {
10.                 if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
11.                 else dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+1));
12.             }
13.         }
14.         return dp[word1.size()][word2.size()];
15.     }
16. };

647回文子串

写的很好，我想不到用i j的距离（而不是索引字符）来做单字符与双字符的回文。

Code:

注意都是在s[i]==s[j]时候改值

1. class Solution {
2. public:
3.     int countSubstrings(string s) {
4.         int res = 0;
5.         vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
6.         for (int i = s.size() - 1; i >= 0; i--) {
7.             for (int j = i; j < s.size(); j++) {
8.                 if (s[j] == s[i]) {
9.                     if (j - i <= 1) {
10.                         res++;
11.                         dp[i][j] = true;
12.                     } else if (dp[i + 1][j - 1]) {
13.                         res++;
14.                         dp[i][j] = true;
15.                     }
16.                 }
17.             }
18.         }
19.         return res;
20.     }
21. };

516最长回文子序列

经验题，继续学：

注意里面的加减符号别弄错，理解题意是关键。

1. class Solution {
2. public:
3.     int longestPalindromeSubseq(string s) {
4.         vector<vector<int>>dp(s.size(),vector<int>(s.size(),0));
5.         for(int i=0;i<s.size();i++) dp[i][i]=1;
6.         for(int i=s.size()-1;i>=0;i--){
7.             for(int j=i+1;j<s.size();j++){
8.                 if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
9.                 else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
10.             }
11.         }
12.         return dp[0][s.size()-1];
13.     }
14. };

单调栈

整半天才发现自己把栈顶(top), 栈底给弄反了，要重做之前的题目。

739每日温度

朴素法，超时：

1. class Solution {
2. public:
3. //朴素法
4.     vector<int> dailyTemperatures(vector<int>& temperatures) {
5.         vector<int> res(temperatures.size(),0);
6.         for(int i=0;i<temperatures.size();i++){
7.             int idx=temperatures[i];
8.             for(int j=i+1;j<temperatures.size();j++){
9.                 if(idx<temperatures[j]){
10.                     res[i]=j-i;
11.                     break;
12.                 }
13.             }
14.         }
15.         return res;
16.     }
17. };

注意！

单调栈里存的是下标。

未精简的代码：

1. class Solution {
2. public:
3.     vector<int> dailyTemperatures(vector<int>& temperatures) {
4.         vector<int> res(temperatures.size(),0);
5.         stack<int> s;
6.         s.push(0);
7.         for(int i=1;i<temperatures.size();i++){
8.             if(temperatures[i]<temperatures[s.top()]) s.push(i);
9.             else if(temperatures[i]==temperatures[s.top()]) s.push(i);
10.             else{
11.                 while(!s.empty()&&temperatures[i]>temperatures[s.top()]){
12.                     res[s.top()]=i-s.top();
13.                     s.pop();
14.                 }
15.                 s.push(i);
16.             }
17.         }
18.         return res;
19.     }
20. };

精简后的代码：

1. class Solution {
2. public:
3.     vector<int> dailyTemperatures(vector<int>& temperatures) {
4.         vector<int> res(temperatures.size(),0);
5.         stack<int> s;
6.         for(int i=0;i<temperatures.size();i++){
7.             while(!s.empty()&&temperatures[i]>temperatures[s.top()]){
8.                 res[s.top()]=i-s.top();
9.                 s.pop();
10.             }
11.             s.push(i);
12.         }
13.         return res;
14.     }
15. };

496下一个更大元素i

没想到：“数组中没有重复数字，用map做两个数组的映射。

根据数值快速找到下标，还可判断nums2[i]是否在nums1中出现过。

当使用集合来解决哈希问题的时候，优先使用unordered_set，因为他的查询和增删效率是最优的。”

注意注释上的东西：

1. class Solution {
2. public:
3.     vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
4.         unordered_map<int,int> map;
5.         vector<int> res(nums1.size(),-1);
6.         for(int i=0;i<nums1.size();i++) map[nums1[i]]=i;
7.         stack<int> s;
8.         s.push(0);
9.         for(int i=1;i<nums2.size();i++){
10.             while(!s.empty()&&nums2[i]>nums2[s.top()]){
11.                 if(map.count(nums2[s.top()])>0){
12.                     //idx注意怎么求，别弄错
13.                     int idx=map[nums2[s.top()]];
14.                     res[idx]=nums2[i];
15.                 }
16.                 //这句话不要写在if里面
17.                 s.pop();
18.             }
19.             s.push(i);
20.         }
21.         return res;
22.     }
23. };

待理清思路，二刷：

1. class Solution {
2. public:
3.     vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
4.         unordered_map<int,int> map;
5.         vector<int> res(nums1.size(),-1);
6.         for(int i=0;i<nums1.size();i++) map[nums1[i]]=i;
7.         stack<int> s;
8.         s.push(0);
9.         for(int i=1;i<nums2.size();i++){
10.             while(!s.empty()&&nums2[i]>nums2[s.top()]){
11.                 if(map.count(nums2[s.top()])>0){
12.                     res[map[nums2[s.top()]]]=nums2[i];
13.                 }
14.                 s.pop();
15.             }
16.             s.push(i);
17.         }
18.         return res;
19.     }
20. };

503下一个更大元素ii

1 很妙的想法：数组拼接，取res.size()/2

注意insert的写法：

1. class Solution {
2. public:
3.     vector<int> nextGreaterElements(vector<int>& nums) {
4.         vector<int> newnums(nums.begin(),nums.end());
5.         nums.insert(nums.end(),newnums.begin(),newnums.end());
6.         vector<int> res(nums.size(),-1);
7.         stack<int> s;
8.         s.push(0);
9.         for(int i=1;i<nums.size();i++){
10.             while(!s.empty()&&nums[i]>nums[s.top()]){
11.                 res[s.top()]=nums[i];
12.                 s.pop();
13.             }
14.             s.push(i);
15.         }
16.         res.resize(res.size()/2);
17.         return res;
18.     }
19. };

2 对于“循环”，要想到：用mod （%）来操作。

要注意的是 ，res[idx];; idx=s.top()相关的。

1. class Solution {
2. public:
3.     vector<int> nextGreaterElements(vector<int>& nums) {
4.         vector<int> res(nums.size(),-1);
5.         stack<int> s;
6.         s.push(0);
7.         for(int i=1;i<2*nums.size();i++){
8.             while(!s.empty()&&nums[i%nums.size()]>nums[s.top()]){
9.                 res[s.top()]=nums[i%nums.size()];
10.                 s.pop();
11.             }
12.             s.push(i%nums.size());
13.         }
14.         return res;
15.     }
16. };

42接雨水，困难

对于不规则的阴影面积（由单位面积组成）求解，应当明确：按行计算还是按列计算。

按列计算，朴素法：一次性写对了，真的进步了很多，坚持每天复现+做复试真题来加强吧。

1. class Solution {
2. public:
3.     int trap(vector<int>& height) {
4.         int sum=0;
5.         for(int i=0;i<height.size();i++){
6.             if(i==0||i==height.size()-1) continue;
7.             int maxleft=height[0];
8.             int maxright=height[height.size()-1];
9.             for(int j=0;j<=i;j++) maxleft=max(maxleft,height[j]);
10.             for(int j=height.size()-1;j>=i;j--) maxright=max(maxright,height[j]);
11.             int mywater=min(maxleft,maxright)-height[i];
12.             if(mywater>0) sum+=mywater;
13.         }
14.         return sum;
15.     }
16. };

按列计算，双指针优化：

双指针优化 求左右最大的语句写错了。在纸上写一下就写对了，不要空想：

求右边的最大：如果当前自己的高度是最大的，那么自己就是最大height[i],；

反正，我们需要继承之前的maxright结果。即：maxright[i+1];

1. class Solution {
2. public:
3.     int trap(vector<int>& height) {
4.         int sum=0;
5.         vector<int> maxleft(height.size(),height[0]);
6.         vector<int> maxright(height.size(),height[height.size()-1]);
7.         for(int j=1;j<height.size();j++) maxleft[j]=max(maxleft[j-1],height[j]);
8.         for(int j=height.size()-2;j>=0;j--) maxright[j]=max(maxright[j+1],height[j]);
9.         for(int i=0;i<height.size();i++){
10.             if(i==0||i==height.size()-1) continue;
11.             int mywater=min(maxleft[i],maxright[i])-height[i];
12.             if(mywater>0) sum+=mywater;
13.         }
14.         return sum;
15.     }
16. };

单调栈：

一旦形成槽，就要计算接水量，所以从栈顶部到栈底，应当是维护递增。

注意是按行计算。

1. class Solution {
2. public:
3.     int trap(vector<int>& height) {
4.         int sum=0;
5.         stack<int> s;
6.         s.push(0);
7.         for(int i=1;i<height.size();i++){
8.             if(height[i]<height[s.top()]) s.push(i);
9.             else if(height[i]==height[s.top()]){
10.                 s.pop();
11.                 s.push(i);
12.             }
13.             else{
14.                 while(!s.empty()&&height[i]>height[s.top()]){
15.                     int mid=s.top();
16.                     s.pop();
17.                     if(!s.empty()){
18.                         int h=min(height[i],height[s.top()])-height[mid];
19.                         int w=i-s.top()-1;
20.                         int mywater=h*w;
21.                         if(mywater>0) sum+=mywater;
22.                         //按行计算，所以下一句还不能做pop();
23.                     }
24.                 }
25.                 //记得入栈
26.                 s.push(i);
27.             }
28.         }
29.         return sum;
30.     }
31. };

正好二刷，单调栈写法：

1. class Solution {
2. public:
3.     int trap(vector<int>& height) {
4.         int sum=0;
5.         stack<int> s;
6.         s.push(0);
7.         for(int i=1;i<height.size();i++){
8.             while(!s.empty()&&height[i]>height[s.top()]){
9.                 int mid=s.top();
10.                 s.pop();
11.                 if(!s.empty()){
12.                     int h=min(height[i],height[s.top()])-height[mid];
13.                     int w=i-s.top()-1;
14.                     if(w*h>0) sum+=(w*h);
15.                 }
16.             }
17.             s.push(i);
18.         }
19.         return sum;
20.     }
21. };

你可能会好奇：为什么while 里面的if要去计算宽度呢？不是按行计算吗？

因为外层是while，i不更新，却一直在弹出并计算水量。所以宽度不一定是1，宽度是动态变化的（根据栈的弹出。）

84柱状图中最大的矩形，困难

最后一题了，以后都是二刷或者做类似的题型。

因为每次只在一个柱子上搜结果，不累加，期望尽量搜到最大结果。

那么应当：往i的左边找最矮在哪，往i的右边找最矮的在哪（这些都要高于或等于i）。若左右有矮于i的，就不往那边搜（因为这样搜到的结果必定小于等于其他矮柱子搜到的结果，画图就知道了）。跨度*高度就是i搜到的矩形结果。

知道上述思路，就可以写算法去实现了。

朴素（超时）：

1. class Solution {
2. public:
3.     int largestRectangleArea(vector<int>& heights) {
4.         int res=0;
5.         for(int i=0;i<heights.size();i++){
6.             int left=i,right=i;
7.             for(;left>=0;left--){
8.                 if(heights[left]<heights[i]) break;
9.             }
10.             for(;right<heights.size();right++){
11.                 if(heights[right]<heights[i]) break;
12.             }
13.             int w=right-left-1;
14.             int h=heights[i];
15.             res=max(res,h*w);
16.         }
17.         return res;
18.     }
19. };

双指针写法比较复杂，不管了。

单调栈：与“接雨水”不一样的是，这题最左边和最右边柱子都有相应的结果，在接雨水里不是这样。为了普适性，我们需要把heights数组开头及末尾加入元素0.

你可能会好奇：为什么while 里面的if要去计算宽度呢？并且能实现题意呢？

因为外层是while，i不更新，却一直在弹出并计算面积。所以间距不一定是1，间距是动态变化的（根据栈的弹出。）

1. class Solution {
2. public:
3.     int largestRectangleArea(vector<int>& heights) {
4.         int res=0;
5.         stack<int> s;
6.         s.push(0);
7.         heights.insert(heights.begin()+0,0);
8.         heights.push_back(0);
9.         for(int i=1;i<heights.size();i++){
10.             while(!s.empty()&&heights[i]<heights[s.top()]){
11.                 int mid=s.top();
12.                 s.pop();
13.                 if(!s.empty()){
14.                     int left=s.top();
15.                     int right=i;
16.                     int w=right-left-1;
17.                     int h=heights[mid];
18.                     res=max(res,h*w);
19.                 }
20.             }
21.             s.push(i);
22.         }
23.         return res;
24.     }
25. };

感谢支持，之后会写的其他的东西。

标签：last,int,res,随想录,36,height,vector,dp,size
From： https://blog.csdn.net/illuosion7/article/details/139683887