最后一次更新,之后去复习专业课和简历
583两个字符串的删除操作
自己做出来了:
Code:
- class Solution {
- public:
- //找到公共子序列的最大长度dp 最小步数=串1.size-dp+串2.size-dp
- int minDistance(string word1, string word2) {
- vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));
- dp[0][0]=0;
- for(int i=1;i<=word1.size();i++){
- for(int j=1;j<=word2.size();j++){
- if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
- else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
- }
- }
- return word1.size()+word2.size()-2*dp[word1.size()][word2.size()];
- }
- };
72编辑距离
没思路,明天学。积累经验
拓展思维:word2转变到word1也可以。
别人的删,就相当于我的增。Dp[i][j]=dp[i][j-1]+1
- class Solution {
- public:
- int minDistance(string word1, string word2) {
- vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));
- for(int i=0;i<=word1.size();i++) dp[i][0]=i;
- for(int i=0;i<=word2.size();i++) dp[0][i]=i;
- for(int i=1;i<=word1.size();i++){
- for(int j=1;j<=word2.size();j++)
- {
- if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
- else dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+1));
- }
- }
- return dp[word1.size()][word2.size()];
- }
- };
647回文子串
写的很好,我想不到用i j的距离(而不是索引字符)来做单字符与双字符的回文。
Code:
注意都是在s[i]==s[j]时候改值
- class Solution {
- public:
- int countSubstrings(string s) {
- int res = 0;
- vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
- for (int i = s.size() - 1; i >= 0; i--) {
- for (int j = i; j < s.size(); j++) {
- if (s[j] == s[i]) {
- if (j - i <= 1) {
- res++;
- dp[i][j] = true;
- } else if (dp[i + 1][j - 1]) {
- res++;
- dp[i][j] = true;
- }
- }
- }
- }
- return res;
- }
- };
516最长回文子序列
经验题,继续学:
注意里面的加减符号别弄错,理解题意是关键。
- class Solution {
- public:
- int longestPalindromeSubseq(string s) {
- vector<vector<int>>dp(s.size(),vector<int>(s.size(),0));
- for(int i=0;i<s.size();i++) dp[i][i]=1;
- for(int i=s.size()-1;i>=0;i--){
- for(int j=i+1;j<s.size();j++){
- if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
- else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
- }
- }
- return dp[0][s.size()-1];
- }
- };
单调栈
整半天才发现自己把栈顶(top), 栈底给弄反了,要重做之前的题目。
739每日温度
朴素法,超时:
- class Solution {
- public:
- //朴素法
- vector<int> dailyTemperatures(vector<int>& temperatures) {
- vector<int> res(temperatures.size(),0);
- for(int i=0;i<temperatures.size();i++){
- int idx=temperatures[i];
- for(int j=i+1;j<temperatures.size();j++){
- if(idx<temperatures[j]){
- res[i]=j-i;
- break;
- }
- }
- }
- return res;
- }
- };
注意!
单调栈里存的是下标。
未精简的代码:
- class Solution {
- public:
- vector<int> dailyTemperatures(vector<int>& temperatures) {
- vector<int> res(temperatures.size(),0);
- stack<int> s;
- s.push(0);
- for(int i=1;i<temperatures.size();i++){
- if(temperatures[i]<temperatures[s.top()]) s.push(i);
- else if(temperatures[i]==temperatures[s.top()]) s.push(i);
- else{
- while(!s.empty()&&temperatures[i]>temperatures[s.top()]){
- res[s.top()]=i-s.top();
- s.pop();
- }
- s.push(i);
- }
- }
- return res;
- }
- };
精简后的代码:
- class Solution {
- public:
- vector<int> dailyTemperatures(vector<int>& temperatures) {
- vector<int> res(temperatures.size(),0);
- stack<int> s;
- for(int i=0;i<temperatures.size();i++){
- while(!s.empty()&&temperatures[i]>temperatures[s.top()]){
- res[s.top()]=i-s.top();
- s.pop();
- }
- s.push(i);
- }
- return res;
- }
- };
496下一个更大元素i
没想到:“数组中没有重复数字,用map做两个数组的映射。
根据数值快速找到下标,还可判断nums2[i]是否在nums1中出现过。
当使用集合来解决哈希问题的时候,优先使用unordered_set,因为他的查询和增删效率是最优的。”
注意注释上的东西:
- class Solution {
- public:
- vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
- unordered_map<int,int> map;
- vector<int> res(nums1.size(),-1);
- for(int i=0;i<nums1.size();i++) map[nums1[i]]=i;
- stack<int> s;
- s.push(0);
- for(int i=1;i<nums2.size();i++){
- while(!s.empty()&&nums2[i]>nums2[s.top()]){
- if(map.count(nums2[s.top()])>0){
- //idx注意怎么求,别弄错
- int idx=map[nums2[s.top()]];
- res[idx]=nums2[i];
- }
- //这句话不要写在if里面
- s.pop();
- }
- s.push(i);
- }
- return res;
- }
- };
待理清思路,二刷:
- class Solution {
- public:
- vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
- unordered_map<int,int> map;
- vector<int> res(nums1.size(),-1);
- for(int i=0;i<nums1.size();i++) map[nums1[i]]=i;
- stack<int> s;
- s.push(0);
- for(int i=1;i<nums2.size();i++){
- while(!s.empty()&&nums2[i]>nums2[s.top()]){
- if(map.count(nums2[s.top()])>0){
- res[map[nums2[s.top()]]]=nums2[i];
- }
- s.pop();
- }
- s.push(i);
- }
- return res;
- }
- };
503下一个更大元素ii
1 很妙的想法:数组拼接,取res.size()/2
注意insert的写法:
- class Solution {
- public:
- vector<int> nextGreaterElements(vector<int>& nums) {
- vector<int> newnums(nums.begin(),nums.end());
- nums.insert(nums.end(),newnums.begin(),newnums.end());
- vector<int> res(nums.size(),-1);
- stack<int> s;
- s.push(0);
- for(int i=1;i<nums.size();i++){
- while(!s.empty()&&nums[i]>nums[s.top()]){
- res[s.top()]=nums[i];
- s.pop();
- }
- s.push(i);
- }
- res.resize(res.size()/2);
- return res;
- }
- };
2 对于“循环”,要想到:用mod (%)来操作。
要注意的是 ,res[idx];; idx=s.top()相关的。
- class Solution {
- public:
- vector<int> nextGreaterElements(vector<int>& nums) {
- vector<int> res(nums.size(),-1);
- stack<int> s;
- s.push(0);
- for(int i=1;i<2*nums.size();i++){
- while(!s.empty()&&nums[i%nums.size()]>nums[s.top()]){
- res[s.top()]=nums[i%nums.size()];
- s.pop();
- }
- s.push(i%nums.size());
- }
- return res;
- }
- };
42接雨水,困难
对于不规则的阴影面积(由单位面积组成)求解,应当明确:按行计算还是按列计算。
按列计算,朴素法:一次性写对了,真的进步了很多,坚持每天复现+做复试真题来加强吧。
- class Solution {
- public:
- int trap(vector<int>& height) {
- int sum=0;
- for(int i=0;i<height.size();i++){
- if(i==0||i==height.size()-1) continue;
- int maxleft=height[0];
- int maxright=height[height.size()-1];
- for(int j=0;j<=i;j++) maxleft=max(maxleft,height[j]);
- for(int j=height.size()-1;j>=i;j--) maxright=max(maxright,height[j]);
- int mywater=min(maxleft,maxright)-height[i];
- if(mywater>0) sum+=mywater;
- }
- return sum;
- }
- };
按列计算,双指针优化:
双指针优化 求左右最大的语句写错了。在纸上写一下就写对了,不要空想:
求右边的最大:如果当前自己的高度是最大的,那么自己就是最大height[i],;
反正,我们需要继承之前的maxright结果。即:maxright[i+1];
- class Solution {
- public:
- int trap(vector<int>& height) {
- int sum=0;
- vector<int> maxleft(height.size(),height[0]);
- vector<int> maxright(height.size(),height[height.size()-1]);
- for(int j=1;j<height.size();j++) maxleft[j]=max(maxleft[j-1],height[j]);
- for(int j=height.size()-2;j>=0;j--) maxright[j]=max(maxright[j+1],height[j]);
- for(int i=0;i<height.size();i++){
- if(i==0||i==height.size()-1) continue;
- int mywater=min(maxleft[i],maxright[i])-height[i];
- if(mywater>0) sum+=mywater;
- }
- return sum;
- }
- };
单调栈:
一旦形成槽,就要计算接水量,所以从栈顶部到栈底,应当是维护递增。
注意是按行计算。
- class Solution {
- public:
- int trap(vector<int>& height) {
- int sum=0;
- stack<int> s;
- s.push(0);
- for(int i=1;i<height.size();i++){
- if(height[i]<height[s.top()]) s.push(i);
- else if(height[i]==height[s.top()]){
- s.pop();
- s.push(i);
- }
- else{
- while(!s.empty()&&height[i]>height[s.top()]){
- int mid=s.top();
- s.pop();
- if(!s.empty()){
- int h=min(height[i],height[s.top()])-height[mid];
- int w=i-s.top()-1;
- int mywater=h*w;
- if(mywater>0) sum+=mywater;
- //按行计算,所以下一句还不能做pop();
- }
- }
- //记得入栈
- s.push(i);
- }
- }
- return sum;
- }
- };
正好二刷,单调栈写法:
- class Solution {
- public:
- int trap(vector<int>& height) {
- int sum=0;
- stack<int> s;
- s.push(0);
- for(int i=1;i<height.size();i++){
- while(!s.empty()&&height[i]>height[s.top()]){
- int mid=s.top();
- s.pop();
- if(!s.empty()){
- int h=min(height[i],height[s.top()])-height[mid];
- int w=i-s.top()-1;
- if(w*h>0) sum+=(w*h);
- }
- }
- s.push(i);
- }
- return sum;
- }
- };
你可能会好奇:为什么while 里面的if要去计算宽度呢?不是按行计算吗?
因为外层是while,i不更新,却一直在弹出并计算水量。所以宽度不一定是1,宽度是动态变化的(根据栈的弹出。)
84柱状图中最大的矩形,困难
最后一题了,以后都是二刷或者做类似的题型。
因为每次只在一个柱子上搜结果,不累加,期望尽量搜到最大结果。
那么应当:往i的左边找最矮在哪,往i的右边找最矮的在哪(这些都要高于或等于i)。若左右有矮于i的,就不往那边搜(因为这样搜到的结果必定小于等于其他矮柱子搜到的结果,画图就知道了)。跨度*高度就是i搜到的矩形结果。
知道上述思路,就可以写算法去实现了。
朴素(超时):
- class Solution {
- public:
- int largestRectangleArea(vector<int>& heights) {
- int res=0;
- for(int i=0;i<heights.size();i++){
- int left=i,right=i;
- for(;left>=0;left--){
- if(heights[left]<heights[i]) break;
- }
- for(;right<heights.size();right++){
- if(heights[right]<heights[i]) break;
- }
- int w=right-left-1;
- int h=heights[i];
- res=max(res,h*w);
- }
- return res;
- }
- };
双指针写法比较复杂,不管了。
单调栈:与“接雨水”不一样的是,这题最左边和最右边柱子都有相应的结果,在接雨水里不是这样。为了普适性,我们需要把heights数组开头及末尾加入元素0.
你可能会好奇:为什么while 里面的if要去计算宽度呢?并且能实现题意呢?
因为外层是while,i不更新,却一直在弹出并计算面积。所以间距不一定是1,间距是动态变化的(根据栈的弹出。)
- class Solution {
- public:
- int largestRectangleArea(vector<int>& heights) {
- int res=0;
- stack<int> s;
- s.push(0);
- heights.insert(heights.begin()+0,0);
- heights.push_back(0);
- for(int i=1;i<heights.size();i++){
- while(!s.empty()&&heights[i]<heights[s.top()]){
- int mid=s.top();
- s.pop();
- if(!s.empty()){
- int left=s.top();
- int right=i;
- int w=right-left-1;
- int h=heights[mid];
- res=max(res,h*w);
- }
- }
- s.push(i);
- }
- return res;
- }
- };
感谢支持,之后会写的其他的东西。