Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。
🌈个人主页：主页链接
🌈算法专栏：专栏链接
我会一直往里填充内容哒！
🌈LeetCode专栏：专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出
🌈代码仓库：Gitee链接
🌈点击关注=收获更多优质内容🌈
最长回文子序列:
题解:
老样子,我们依旧按照这个方法去分析问题
先明白这里的集合是什么?
要求的是回文子序列,那这里的集合必然和子序列有关,分析回文的属性.
发现:回文需要从头尾来看自然而然 dp[i][j]其中i,j的含义就为以i开头,j结尾的最长回文子序列的长度
再看看看下一个状态:这题要的属性是什么?
观察题意不难得出,是Max
再来看看最难的部分,状态转移方程的表示.上文说过i,j的含义是以i开头j结尾的回文子串的含义,
所以是由短的推到长的一个过程.
所以从末尾开始递推,
若遇到s[i]==s[j]的情况,则让dp[i][j]+=2;
若s[i]!=s[j]的情况,则判断 在dp[i][j-1]与dp[i-1][j]下谁更大保存较大的那个值即可.
所以dp方程为dp[i][j]=dp[i+1][j-1]+2 / / dp[i][j]=max(dp[i+1][j],dp[i][j-1])
至此这张表就填完了,那么也可以开始解题了
注意这里有个初始条件的问题:当i与j指向同一个字母时,此时的回文长度为1,所以将dp[i][i]都设置为1
循环模式为:依次确定左端点i,遍历其右端点,寻找最长回文子序列
代码实现:
class Solution { public: int longestPalindromeSubseq(string s) { vector<vector<int>>dp(s.size(),vector<int>(s.size())); //dp[i][j] 从i-j中最长的回文子序列长度 for(int i=0;i<s.size();i++)dp[i][i]=1; for(int i=s.size()-2;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][j-1],dp[i+1][j]); } } return dp[0][s.size()-1]; } };
俄罗斯信封套娃问题:
题解:
依旧用这种方法来分析下题目.
先分析下问题是啥? 在一个绝对大的(长宽都大于另一个子信封的长宽)信封中看看能套几个子信封?
也就是如下图所示
所以自然而然的我们可以想到,那如果从小到大将信封排序.找出绝对小于的情况不就满足题意了?
是的!这种思想可以解决一部分问题,例如第一个测试用例中排完序如下图所示(相等的为乱序)
排完序,若第一个数相等那么第二个数如何处理呢?
这里可以回顾下我们之前所做的最长上升子序列的问题.不就可以用来处理第二个数嘛?
所以现在的逻辑就是这样,若第一个数不同则直接将长度加一,若相同则寻找最长上升子序列.
但观察代码中的最后两个,若将6 4 放在6 7之前,最后取最长上升子序列时,就有可能将6 4也取到
所以我们要这样处理 若第一个数相同,则第二个数进行逆序存储,变成如下这种情况
这样我们仅需要对第二列数据求最长上升子序列即可,因为若第一个数相同,则小的那个不会被算入最终答案中
所以回到开头的那个问题.
这里的集合表示为dp[j],以j结尾的最长上升子序列长度
属性为Max
状态方程为 if(s[i]>=s[i-1])dp[i]=max(dp[j]+1,dp[i])
至此这道问题就解决完了,当然还要考虑一个dp初始值的问题:这里显然就是dp[j]=1(最短的上升子序列为其本身)
代码实现:
class Solution { public: int maxEnvelopes(vector<vector<int>>& envelopes) { if(envelopes.empty())return 0; sort(envelopes.begin(),envelopes.end(),[](const auto &c1,const auto&c2){ return c1[0]<c2[0]||(c1[0]==c2[0] &&c1[1]>c2[1]); }); vector<int>dp(envelopes.size(),1); for(int i=1;i<envelopes.size();i++) { for(int j=0;j<i;j++) { if(envelopes[i][1]>envelopes[j][1]) { dp[i]=max(dp[j]+1,dp[i]); } } } int ans=INT_MIN; for(int i=0;i<dp.size();i++) { if(dp[i]>ans)ans=dp[i]; } return ans; } };
单调队列优化:
这里虽然做出来了,且官解也是这样的.但力扣更新完测试用例之后就超时了.
单调队列比较像贪心,uu们可以去看看我这篇关于单调队列优化的理解.这里就不过多赘述
其大意思想就是,利用二分找到比插入值小的最大的一个值,之后将插入值更新到其前面,并更新队列长度与顶元素
class Solution { public: int maxEnvelopes(vector<vector<int>>& envelopes) { if(envelopes.empty())return 0; sort(envelopes.begin(),envelopes.end(),[](const auto &c1,const auto&c2){ return c1[0]<c2[0]||(c1[0]==c2[0] &&c1[1]>c2[1]); }); vector<int>dp(envelopes.size()+1,1); int len=0; for(int i=0;i<envelopes.size();i++) { int l=0,r=len; while(l<r) { int mid=l+r+1>>1; if(dp[mid]<envelopes[i][1])l=mid; else r=mid-1; } len=max(len,r+1); dp[r+1]=envelopes[i][1]; } return len; } };
🌈本篇博客的内容【俄罗斯信封套娃问题，最长回文子序列】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！
