网站建设服务收费,网站多语言模块,wordpress网站是什么,网站建设规划面试技巧300. 最长递增子序列 300. 最长递增子序列
题目解析#xff1a;
给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#… 300. 最长递增子序列 300. 最长递增子序列
题目解析
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 解题思路、 1. 状态表⽰ 对于线性 dp 我们可以⽤「经验 题⽬要求」来定义状态表⽰ i. 以某个位置为结尾巴拉巴拉 ii. 以某个位置为起点巴拉巴拉。 这⾥我们选择⽐较常⽤的⽅式以某个位置为结尾结合题⽬要求定义⼀个状态表⽰ dp[i] 表⽰以 i 位置元素为结尾的「所有⼦序列」中最⻓递增⼦序列的⻓度。 2. 状态转移⽅程 对于 dp[i] 我们可以根据「⼦序列的构成⽅式」进⾏分类讨论 i. ⼦序列⻓度为 1 只能⾃⼰玩了此时 dp[i] 1 ii. ⼦序列⻓度⼤于 1 nums[i] 可以跟在前⾯任何⼀个数后⾯形成⼦序列。 设前⾯的某⼀个数的下标为 j 其中 0 j i - 1 。 只要 nums[j] nums[i] i 位置元素跟在 j 元素后⾯就可以形成递增序列⻓度 为 dp[j] 1 。 因此我们仅需找到满⾜要求的最⼤的 dp[j] 1 即可。 综上 dp[i] max(dp[j] 1, dp[i]) 其中 0 j i - 1 nums[j] nums[i] 。 3. 初始化 所有的元素「单独」都能构成⼀个递增⼦序列因此可以将 dp 表内所有元素初始化为 1 。 由于⽤到前⾯的状态因此我们循环的时候从第⼆个位置开始即可。 4. 填表顺序 显⽽易⻅填表顺序「从左往右」。 5. 返回值 由于不知道最⻓递增⼦序列以谁结尾因此返回 dp 表⾥⾯的「最⼤值」。 解题代码
class Solution {
public:int lengthOfLIS(vectorint nums) {int nnums.size();vectorintdp(n,1);for(int i1;in;i){for(int j 0;ji;j){if(nums[j]nums[i])dp[i]max(dp[i],dp[j]1);}}int ret0;for(int i0;in;i)retmax(ret,dp[i]);return ret;}
}; 376. 摆动序列 376. 摆动序列
题目描述
如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 。第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如 [1, 7, 4, 9, 2, 5] 是一个 摆动序列 因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。 相反[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些也可以不删除元素来获得剩下的元素保持其原始顺序。
给你一个整数数组 nums 返回 nums 中作为 摆动序列 的 最长子序列的长度 。 解题思路 1. 状态表⽰ 对于线性 dp 我们可以⽤「经验 题⽬要求」来定义状态表⽰ i. 以某个位置为结尾巴拉巴拉 ii. 以某个位置为起点巴拉巴拉。 这⾥我们选择⽐较常⽤的⽅式以某个位置为结尾结合题⽬要求定义⼀个状态表⽰ dp[i] 表⽰「以 i 位置为结尾的最⻓摆动序列的⻓度」。 但是问题来了如果状态表⽰这样定义的话以 i 位置为结尾的最⻓摆动序列的⻓度我们没法 从之前的状态推导出来。因为我们不知道前⼀个最⻓摆动序列的结尾处是递增的还是递减的。因 此我们需要状态表⽰能表⽰多⼀点的信息要能让我们知道这⼀个最⻓摆动序列的结尾是递增的 还是递减的。 解决的⽅式很简单搞两个 dp 表就好了。 f[i] 表⽰以 i 位置元素为结尾的所有的⼦序列中最后⼀个位置呈现「上升趋势」的最⻓摆 动序列的⻓度 g[i] 表⽰以 i 位置元素为结尾的所有的⼦序列中最后⼀个位置呈现「下降趋势」的最⻓摆 动序列的⻓度。 2. 状态转移⽅程 由于⼦序列的构成⽐较特殊 i 位置为结尾的⼦序列前⼀个位置可以是 [0, i - 1] 的任意 位置因此设 j 为 [0, i - 1] 区间内的某⼀个位置。 对于 f[i] 我们可以根据「⼦序列的构成⽅式」进⾏分类讨论 i. ⼦序列⻓度为 1 只能⾃⼰玩了此时 f[i] 1 ii. ⼦序列⻓度⼤于 1 因为结尾要呈现上升趋势因此需要 nums[j] nums[i] 。在满 ⾜这个条件下 j 结尾需要呈现下降状态最⻓的摆动序列就是 g[j] 1 。 因此我们要找出所有满⾜条件下的最⼤的 g[j] 1 。 综上 f[i] max(g[j] 1, f[i]) 注意使⽤ g[j] 时需要判断。 对于 g[i] 我们可以根据「⼦序列的构成⽅式」进⾏分类讨论 i. ⼦序列⻓度为 1 只能⾃⼰玩了此时 g[i] 1 ii. ⼦序列⻓度⼤于 1 因为结尾要呈现下降趋势因此需要 nums[j] nums[i] 。在满 ⾜这个条件下 j 结尾需要呈现上升状态因此最⻓的摆动序列就是 f[j] 1 。 因此我们要找出所有满⾜条件下的最⼤的 f[j] 1 。 综上 g[i] max(f[j] 1, g[i]) 注意使⽤ f[j] 时需要判断。 3. 初始化 所有的元素「单独」都能构成⼀个摆动序列因此可以将 dp 表内所有元素初始化为 1 。 4. 填表顺序 毫⽆疑问是「从左往右」。 5. 返回值 应该返回「两个 dp 表⾥⾯的最⼤值」我们可以在填表的时候顺便更新⼀个「最⼤值」。 解题代码
class Solution {
public:int wiggleMaxLength(vectorint nums) {int nnums.size();if(n1)return 1;if(n2nums[0]!nums[1])return 2;vectorintf(n,1);vectorintg(n,1);for(int i1;in;i){for(int j0;ji;j){if(nums[i]nums[j])f[i]max(g[j]1,f[i]);if(nums[i]nums[j])g[i]max(f[j]1,g[i]);}}int ret0;for(int i0;in;i)retmax(ret,max(f[i],g[i]));return ret;}
};
