怎么建立网站数据库连接,vi 设计,德州seo整站优化,手机网站建设商场文章目录 一、300. 最长递增子序列二、673. 最长递增子序列的个数三、变式1、646. 最长数对链2、1218. 最长定差子序列3、1027. 最长等差数列4、354. 俄罗斯套娃信封问题5、1964. 找出到每个位置为止最长的有效障碍赛跑路线 最长递增子序列#xff1a;原序-递增数值问题 最长定… 文章目录 一、300. 最长递增子序列二、673. 最长递增子序列的个数三、变式1、646. 最长数对链2、1218. 最长定差子序列3、1027. 最长等差数列4、354. 俄罗斯套娃信封问题5、1964. 找出到每个位置为止最长的有效障碍赛跑路线 最长递增子序列原序-递增数值问题 最长定差子序列原序-定差数值问题 最长数对链非原序-递增区间问题 俄罗斯信封套娃非原序-递增二维数值问题
一、300. 最长递增子序列
LeetCode300. 最长递增子序列 一个很容易的解法就是定义 d p [ i ] dp[i] dp[i]表示以第 i 1 i1 i1个数字结尾的最长递增子序列长度要求出这个长度只需要往前遍历一次看看前面有没有比它小的字符这样就可以构成一个递增子序列。那么对于第 i 1 i1 i1个字符而言将它之前的所有数字遍历一遍可以求出最长递增子序列。 时间复杂度 O ( n 2 ) O(n^2) O(n2)
class Solution {
public:int lengthOfLIS(vectorint nums) {vectorint dp(nums.size(), 1);int ans 1;for(int i 1; i nums.size(); i){for(int j i - 1; j 0; -- j){if(nums[i] nums[j]){dp[i] max(dp[i], dp[j] 1);ans max(ans, dp[i]);}}}return ans;}
};不过我们知道要求出 d p [ i ] dp[i] dp[i]只需要找到前面比它小的数字即可。
我们可以动态维护一个最长递增序列这样序列是这样的 l i s t [ i ] list[i] list[i]表示当前长度为 i 1 i1 i1的递增子序列的末尾的最小数字。我们可以动态维护这样的数据结构。
当我们考虑 d p [ i ] dp[i] dp[i]时我们可以通过 l i s t list list来快速求出 d p [ i ] dp[i] dp[i]的值二分查找。因为 l i s t list list是按递增子序列长度排列的并且每一个长度都维护了一个最小值。对于第 i 1 i1 i1个数字看它的递增长度 l e n len len 来与 l i s t [ l e n ] list[len] list[len]对比维护 l i s t list list
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) class Solution {
public:int lengthOfLIS(vectorint nums) {vectorint lst;for(int i 0; i nums.size(); i){int left 0, right (int) lst.size() - 1, mid;while(left right){//二分查找查找小于nums[i]的最大值mid (right - left) / 2 left;if(lst[mid] nums[i]){right mid - 1;}else left mid 1;}if(left lst.size()) lst.emplace_back(nums[i]);if(lst[left] nums[i]) lst[left] nums[i];}return lst.size();}
};二、673. 最长递增子序列的个数
LeetCode673. 最长递增子序列的个数 这个题难度大很多我们无法直接使用二分查找因为我们维护的递增子序列是最小值即使记录每个位置现在的个数也无法进行状态转移呀 比如[1, 5 , 2 , 3]这里我们维护了[1, 5]作为长度为2的现在我们加入2现在长度为2变成了[1,2]但我们并不能说长度为2的有两个这样加入3的时候一共有两个长度为3的序列[1,2,3]。原因就在于我们维护的递增子序列每次都是最小的后面加入的更长并不一定前面更小的都能和他构成更长的
那我们先考虑直接暴力计算的方法吧
我们不构造直接二维循环。我们仍然使用 d p [ i ] dp[i] dp[i]表示第 i 1 i1 i1个数字为尾部的最长递增子序列我们使用 c n t [ i ] cnt[i] cnt[i]表示第 i 1 i1 i1个数字为尾部的最长递增子序列的个数。 时间复杂度 O ( n 2 ) O(n^2) O(n2)
class Solution {
public:int findNumberOfLIS(vectorint nums) {vectorint dp(nums.size(), 1);vectorint cnt(nums.size(), 1);int mx 1;int ans 0;for(int i 0; i nums.size(); i){for(int j i - 1; j 0; -- j){if(nums[i] nums[j]){if(dp[j] 1 dp[i]){dp[i] dp[j] 1;cnt[i] cnt[j];}else{if(dp[j] 1 dp[i]){cnt[i] cnt[j];}}}}if(dp[i] mx){ans cnt[i];}else{if(dp[i] mx) mx dp[i], ans cnt[i];}}return ans;}
};高阶思路 对于300. 最长递增子序列的解法二我们维护的一个标准的最小值。
如果我们能想到另外一点就太强了
我们每次去替换 l i s t [ i ] list[i] list[i]实际上都是当前值 v a l val val比 l i s t [ i ] list[i] list[i]小那么我们换一个想法我们不去替换它而是将 l i s t [ i ] list[i] list[i]扩展为一个数组想替换最小值变为它加在这个数组的末尾这样我们就能够保证每次加入一个 v a l val val都能保证 l i s t [ i ] list[i] list[i]是单调非增的。而且跟我们不看数组的所有元素只看最末尾的元素的话实际上和300. 最长递增子序列一样所以我们能够保证每次加入的是正确的位置。这样做我们就知道我们考虑任何一个数 v a l val val时它如果放在 l i s t [ i ] list[i] list[i]处我们能够知道它能构成多少个长度为 i 1 i1 i1的递增子序列这个数量这跟 l i s t [ i − 1 ] list[i-1] list[i−1]有关而且在 l i s t [ i − 1 ] list[i-1] list[i−1]的数都出现在 v a l val val之前所以一定是可以进行状态转移的。 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
class Solution {int binarySearch(int n, functionbool(int) f) {int l 0, r n;while (l r) {int mid (l r) / 2;if (f(mid)) {r mid;} else {l mid 1;}}return l;}public:int findNumberOfLIS(vectorint nums) {vectorvectorint d, cnt;for (int v : nums) {int i binarySearch(d.size(), [](int i) { return d[i].back() v; });int c 1;if (i 0) {int k binarySearch(d[i - 1].size(), [](int k) { return d[i - 1][k] v; });c cnt[i - 1].back() - cnt[i - 1][k];}if (i d.size()) {d.push_back({v});cnt.push_back({0, c});} else {d[i].push_back(v);cnt[i].push_back(cnt[i].back() c);}}return cnt.back().back();}
};以下问题我们只谈他们使用最长递增子序列的方式解决的方法。这里并不是说要你记住这个方法而是理解他们为什么能这样用扩展思维。
三、变式
1、646. 最长数对链
LeetCode646. 最长数对链
这个问题最快速和方便是使用贪心算法不过我们也可以线排序 然后像最长递增子序列一样使用时间复杂度为 O ( n 2 ) O(n^2) O(n2)的动态规划。
贪心算法的证明 对于任何一个数对链首先对于任何一个维度都是递增的其次它构成的链也是递增的。我们来考察数对链中的其中任何一个数对如果我们能找到满足要求的更小的数对任何一维更小或者两维都能小那么我可以将其替换。根据这个原因我们可以将第二维排序另一维按最小能满足条件的值来进行选择。 实际上将其映射到数轴上可以发现我们最好选择两端都更小的且满足要求的这样不会因为右端更大而导致有一些重叠不能选。这也是为什么我们每次都选择最小而不选择一端大一端更小的。 2、1218. 最长定差子序列
1218. 最长定差子序列 这个题也一样直接像最长递增子序列一样使用时间复杂度为 O ( n 2 ) O(n^2) O(n2)的动态规划。
当然为什么最长对数链需要排序而他们不要 因为他们求的是子序列顺序已经固定了。而最长对数链有两维必须满足其中一维满足要求才能用这种动态规划方式。
但是不得不说这个题和最长递增子序列的区别是什么
最长递增子序列的关系是增而这里的关系是差difference确定一个数val无法在最长递增子序列中确定它是哪一个而这里可以确定它的前驱是val - difference。这样就可以引入哈希查找了将 O ( n 2 ) O(n^2) O(n2)降为 O ( n ) O(n) O(n)
class Solution {
public:int longestSubsequence(vectorint arr, int difference) {unordered_mapint, int mp;//以mp[i]结尾的最长递增子序列int mx 1;for(int i 0; i arr.size(); i){if(mp.count(arr[i] - difference) 0){mp[arr[i]] 1;}else{mp[arr[i]] mp[arr[i] - difference] 1;}mx max(mx, mp[arr[i]]);}return mx;}
};由于数字就那么大使用数组进行存储比哈希表更快。但是我们需要注意一些问题 − 1 0 4 a r r [ i ] , d i f f e r e n c e 1 0 4 -10^4 arr[i], difference 10^4 −104arr[i],difference104那么将其映射到正数里是 [ 0 , 2 × 1 0 4 ] [0,2×10^4] [0,2×104]千万别认为是 [ 0 , 1 0 8 ] [0,10^8] [0,108]两边同时加上 1 0 4 10^4 104是两倍关系不是指数关系。注意 a r r [ i ] − d i f f e r e n c e arr[i] - difference arr[i]−difference的取值范围是 [ − 2 × 1 0 4 , 2 × 1 0 4 ] [-2×10^4,2×10^4] [−2×104,2×104]所以得开的数组范围是 [ 0 , 4 × 1 0 4 ] [0,4×10^4] [0,4×104]
class Solution {
public:int longestSubsequence(vectorint arr, int difference) {int mx 1;arrayint, 40000 1 mp {};for(int i 0; i arr.size(); i){mp[arr[i] 20000] mp[arr[i] - difference 20000] 1;mx max(mx, mp[arr[i] 20000]);}return mx;}
};3、1027. 最长等差数列
LeetCode1027. 最长等差数列 这一题和之前的区别在于等差的大小是不知道的我们不能拿着一个数就确定我们需要的他的最长等差长度因为这跟等差的大小有关因此我们定义 d p [ i ] [ d ] dp[i][d] dp[i][d]表示以i结尾的等差为d的最长长度我们只需要遍历d就能像最长定差子序列一样求解问题了。
不过我们需要注意两个问题
定义array时需要特别注意顺序二维越界不一定会出错容易混淆顺序等差有正的有负的因此等差的范围为 [ − 500 , 500 ] [-500,500] [−500,500]并且当一个数没有这样的等差值时它自己当做等差数列因此长度为1。
class Solution {
public:int longestArithSeqLength(vectorint nums) {arrayarrayint, 1001, 501 dp {};//注意定义的顺序不如直接int dp[501][1001];int mx 1;for(int i 0; i nums.size(); i){for(int d -500; d 500; d){//等差的值if(nums[i] - d 0 || nums[i] - d 500) dp[nums[i]][d 500] 1;//当一个数没有这样的等差值时它自己当做等差数列因此长度为1else dp[nums[i]][d 500] dp[nums[i] - d][d 500] 1;mx max(dp[nums[i]][d 500], mx);}}return mx;}
};4、354. 俄罗斯套娃信封问题
LeetCode354. 俄罗斯套娃信封问题 乍一看这个题目好像跟LeetCode646. 最长数对链一毛一样最长对数链使用贪心能够解决难道这道题也可以答案是不可以原因在于信封一端更小但另一端可能很大导致其他信封塞不下。
最长对数链之所以右端更小就更好的原因在于它不会影响比它大的数对的选择选择更大的可能这个更大的区间中间可以放多个选择右端最小就不会有这样的问题 即右端优先。但信封任何一端都没有这样的优先权两端是等价的。
这个题和数对链一样它们不是子序列的问题直接二重循环是不行的。我们必须知道本质能变成子序列问题是因为答案必然由“子序列”构成而不能是其他的顺序。
那我们如果使用二重循环那就需要保证问题的解是子序列我们需要从答案中考虑
答案保证了w和h是单增的那么我们在数组中尝试让w单增那么选择时 答案是否就是这个子序列了呢很难想到吧官解告诉我们并不是原因在于当w存在相等的值时我们仅仅看h的大小会有问题实际上这些信封都不能套起来因此我们需要保证w相同时不会导致只考虑h出现问题。这里有两种方式 ①保证w相同时h是降序这样单考虑h构成的子序列不会出现把相同的宽度套在一起的情况。②我们再来考虑一下w相同w的信封不被套起来。
信封套娃实际上可以转化为二维最长递增子序列的问题。 我们这样就发现了问题的本质 1使用从前往后遍历的方式来查看当前值和之前值能构成的答案时实际上就必须保证解是子序列。无论是维护答案还是二重循环。 2从答案中思考问题的结构答案必须保证升序。因此将二维中的一维升序转换后实际上答案必然就在转换后的子序列中原因是答案必然是其中一维升序这是非常神奇的点
使用二重循环的方法实际上将其中一维升序之后就变成了最长递增子序列的问题。不作第二维处理就剔除一下升序那维相同的情况即可。
使用二分查找的方法仅仅将其中一维升序不够因为第二维放的位置是跟大小有关系的无法做到通过另一维判断情况。那么为了保证一维相同时的情况不会被考虑我们得对相同时的情况的另一维做处理。 我们要刨除相同一维的影响直接使得另一维不可能构成答案应该怎么做 正确的做法是在保证一维升序的情况下另一维降序这样的话单独考虑这些宽度相同的信封时他们不可能在子序列的情况下构成嵌套关系。 这样的话就一定不会出现导致相同宽度的信封被认为嵌套。
方法一 二重循环 时间复杂度 O ( n 2 ) O(n^2) O(n2) 超时
不用二维降序多加一个判断就好
bool cmp(vectorint a, vectorint b){return a[0] b[0];
}
class Solution {
public:int maxEnvelopes(vectorvectorint envelopes) {sort(envelopes.begin(), envelopes.end(), cmp);vectorint dp(envelopes.size(), 1);int mx 1;for(int i 1; i envelopes.size(); i){for(int j i - 1; j 0; -- j){if(envelopes[i][0] ! envelopes[j][0] envelopes[i][1] envelopes[j][1]){dp[i] max(dp[i], dp[j] 1);mx max(mx, dp[i]);}}}return mx;}
};使用二维降序直接就变成了最长递增子序列的问题
bool cmp(vectorint a, vectorint b){if(a[0] b[0]) return a[1] b[1];return a[0] b[0];
}
class Solution {
public:int maxEnvelopes(vectorvectorint envelopes) {sort(envelopes.begin(), envelopes.end(), cmp);vectorint dp(envelopes.size(), 1);int mx 1;for(int i 1; i envelopes.size(); i){for(int j i - 1; j 0; -- j){if(envelopes[i][1] envelopes[j][1]){dp[i] max(dp[i], dp[j] 1);mx max(mx, dp[i]);}}}return mx;}
};方法二 启发式排序 二分查找 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
bool cmp(vectorint a, vectorint b){if(a[0] b[0]) return a[1] b[1];return a[0] b[0];
}
class Solution {
public:int maxEnvelopes(vectorvectorint envelopes) {sort(envelopes.begin(), envelopes.end(), cmp);int n envelopes.size();vectorint lst;for(int i 0; i n; i){auto it lower_bound(lst.begin(), lst.end(), envelopes[i][1]);//寻找大于等于的第一个位置,不要用upper因为等于也是不行的if(it lst.end()){lst.emplace_back(envelopes[i][1]);}else{*it min(*it, envelopes[i][1]);}}return (int) lst.size();}
};方法三 单维排序 二分查找 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)虽然运行过慢但实际上就是 O ( n l o g n ) O(nlogn) O(nlogn)慢的原因是判断的条件多了很多空间大了一些。 这种方法官解没有提供不是想拓展一下思路深度思考的别看了判断写的太长了条件有点多 还可以观察到一个有意思的事情由于相同w的信封是按顺序排列的那我们一定会按顺序进行考虑我们什么时候会出现错误的情况呢 我们来考虑在求 最长递增子序列的个数时 我们维护一个最长递增子序列 并维护每个位置有哪些数。对于相同宽度的信封 e 1 , e 2 , e 3 , e 4 e1,e2,e3,e4 e1,e2,e3,e4从小到大排序即 e 1 e 2 e 3 e 4 e1e2e3e4 e1e2e3e4对于当前维护的信封 m 1 , m 2 , m 3 , m 4 , m 5 m1,m2,m3,m4,m5 m1,m2,m3,m4,m5如果将 e i ei ei替换 m 1 m1 m1 ~ m 4 m4 m4中的任何一个信封不管 e i ei ei怎么替换最长长度都是对的我们可以会替换成 e 1 , e 2 , e 3 , e 4 , m 5 e1,e2,e3,e4,m5 e1,e2,e3,e4,m5这个时候我们随便举个例子 e 4 e4 e4的位置代表的是以 e 4 e4 e4结尾的能构成长度为4的套娃但实际上能行吗 如果有这样的情况 m 2 e 3 e 4 m 3 m 4 m2 e3 e4 m3 m4 m2e3e4m3m4我们说当 e 3 e3 e3替换掉 m 3 m3 m3之后 e 4 e4 e4被认为放到 m 4 m4 m4的位置这是对的嘛显然是不对的 e 4 e4 e4根本无法构成更长的所以出现错误。 如果我们同样来维护每个位置有哪些信封这个时候你必须用 e 4 e4 e4和 e 3 e3 e3的位置里的所有信封进行比较如果存在一个使得比 e 4 e4 e4更小实际上只需要比一次那么 e 4 e4 e4可以替换 m 4 m4 m4如果不存在那么 e 4 e4 e4需要被抛弃因为它的作用不及 e 3 e3 e3。 但如果是这样的我们考虑 m 1 e 3 m 2 m 3 e 4 m 4 m1 e3 m2 m3 e4 m4 m1e3m2m3e4m4这个时候又是什么情况 m 2 m2 m2一定被 e 3 e3 e3替换 e 4 e4 e4是否一定能替换 m 4 m4 m4答案是一定的因为即使没有 e 3 e3 e3的存在 e 4 e4 e4也一定能替换 m 4 m4 m4有了并不影响这样我们就可以写出一个新算法并不需要第二维排序了多加一个判断就行。空间复杂度稍微高了一点点 虽然我们知道有了个新方法但是别忘了官解最好是第二维降序这样就不会出现这样的问题了因为这样第一维相同第二维不可能构成答案了 bool cmp(vectorint a, vectorint b){/*if(a[0] b[0]) return a[1] b[1];*/return a[0] b[0];
}
class Solution {
public:int maxEnvelopes(vectorvectorint envelopes) {sort(envelopes.begin(), envelopes.end(), cmp);vectorvectorvectorint lst;for(int i 0; i envelopes.size(); i){int left 0, right (int) lst.size() - 1, mid;while(left right){mid (right - left) / 2 left;if(lst[mid].back()[1] envelopes[i][1]){left mid 1;}else{right mid - 1;}}//right left,left是需要放的地方if(right -1 || lst[right].back()[0] ! envelopes[i][0]){//与前一个位置的最后一个信封宽度不相同直接放就行if(left lst.size()){lst.push_back({envelopes[i]});}else {if(lst[left].back()[0] envelopes[i][0]){//考虑当前位置的最后一个是否和当前位置最后一个信封宽度相同相同用小的替代if(lst[left].back()[1] envelopes[i][1]){lst[left].back() envelopes[i];}}else lst[left].emplace_back(envelopes[i]);}}else{//与前一个位置的最后一个信封宽度相同if(lst[right].size() 2){//前一个位置的信封至少要有两个才行 有一个肯定不能放if(lst[right][(int) lst[right].size() - 2][1] envelopes[i][1])//有两个看看是否能放if(left lst.size()){lst.push_back({envelopes[i]});}else {if(lst[left].back()[0] envelopes[i][0]){if(lst[left].back()[1] envelopes[i][1]){lst[left].back() envelopes[i];}}else lst[left].emplace_back(envelopes[i]);}}}}return lst.size();}
};5、1964. 找出到每个位置为止最长的有效障碍赛跑路线
这个题实际上就是维护最长来使用二分查找的最长递增子序列的问题。唯一区别就是可以相同相当于最长非减子序列。
class Solution {
public:vectorint longestObstacleCourseAtEachPosition(vectorint obstacles) {vectorint lst;vectorint ans;int n obstacles.size();for(int i 0; i n; i){auto it upper_bound(lst.begin(), lst.end(), obstacles[i]);if(it lst.end()){lst.emplace_back(obstacles[i]);ans.emplace_back(lst.size());}else{*it min(*it, obstacles[i]);ans.emplace_back(it - lst.begin() 1);}}return ans;}
};
