wordpress 404设置,怎么做网站文章优化,网站后台登录域名,网页美术设计主要学什么376. 摆动序列
题目#xff1a;
连续数字#xff08;前减后#xff09;的差严格在正负之间交替#xff0c;差值不能有0为摆动序列。
[1,7,4,9,2,5] 是一个摆动序列#xff0c;因为差值 (6,-3,5,-7,3) 是正负交替出现的
给定一个整数序列#xff0c;返回作为摆动序列…376. 摆动序列
题目
连续数字前减后的差严格在正负之间交替差值不能有0为摆动序列。
[1,7,4,9,2,5] 是一个摆动序列因为差值 (6,-3,5,-7,3) 是正负交替出现的
给定一个整数序列返回作为摆动序列的最长子序列的“长度”。 通过从原始序列中删除一些也可以不删除元素来获得子序列剩下的元素保持其原始顺序。
如果只有两个元素比如[1,2]或者[2,1]也是摆动序列[1,1]不知道是不是。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]输出: 7解释: 这个序列包含几个长度为 7 摆动序列其中一个可为[1,17,10,13,10,16,8]。
思路 局部最优删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值。比如5 10 13 15删掉1013剩下5 15
整体最优整个序列有最多的局部峰值从而达到最长摆动序列。
推出最长摆动序列后要求它的最大长度就是求就是局部峰值的数量。
程序做法
假如遍历到 i 计算 前一个的差值 prediffnums[i] - nums[i-1] 和 现在的差值 curdiffnums[i1] - nums[i] 如果 prediff 0 curdiff 0 或者 prediff 0 curdiff 0 此时就有波动就需要统计。比如17-5-15统计两个波动1-17-5统计两个波动。
但还有三种情况需要再判断
1.情况一上下的坡中有平坡 比如上图这个时候2-2-2-2不是摆动序列上图的实际摆动序列数量只有3个可以统一删除左边或者右边3个这里按删掉左边3个来删掉后摆动序列数量3波动1-22-1两个。 变成 (preDiff 0 curDiff 0) || (preDiff 0 curDiff 0) 记录一次波动上图相当于preDiff 0 curDiff 0记录了一次preDiff 0 curDiff 0记录了一次总共两次波动其他的proDiffcurDiff0不记录相当于删去。
2.情况二数组首尾两端
我的理解是数组只有两个的情况
比如[2,5]这个时候不能统计它的波动因为preDiff 0 curDiff 0) || (preDiff 0 curDiff 0 只能判断有3个数字的但当只有两个比如[25],题目也判断成摆动数组题目要 求子序列数组判断为摆动数组后的长度因为被判定为摆动数组这里的子序列长度是2
所以这种情况怎么处理可以直接只有两的时候比如[25]判定成2也可以不增加特殊条件默认result波动记录加个1为什么result1呢因为相当于[25]被扩展成了[255]
满足了之前条件一更新的的preDiff 0 curDiff 0的这个条件然后result加了个1
总之就是原来result波动记录1可以计算数组只有两的情况满足题目只有两个的数组为摆动数组长度为2的要求。所以为了简洁省特殊条件这样整的麻烦吗... 经过以上分析代码如下
// 版本一
class Solution {
public:int wiggleMaxLength(vectorint nums) {if (nums.size() 1) return nums.size();int curDiff 0; // 当前一对差值int preDiff 0; // 前一对差值int result 1; // 记录峰值个数序列默认序列最右边有一个峰值for (int i 0; i nums.size() - 1; i) {curDiff nums[i 1] - nums[i];// 出现峰值if ((preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)) {result;}preDiff curDiff;}return result;}
};
疑问1
但是网站解析上又说数组首尾两端好像不止包含数组只有两个的情况还包含数组不单只有两个的情况的左右两端的计算这个我不太明白。
3.情况三单调坡度有平坡 如上版本一的代码在单调坡度有平坡的情况记录了三个波动确认为摆动实际上只有2个摆动为什么会出现这样的情况呢实时更新了 prediff。
即preDiff curDiff;在记录波动即if外面
为什么实时更新就会出现这样情况呢
因为实时更新如上图prediff0 curdiff0导致原来判断情况1上下的坡中有平坡的条件错判了情况3单调坡度有平坡的情况了
怎么解决
不再实时更新而是当这个坡度 摆动变化的时候才更新 prediff 这样单调坡度的时候就不会出现误判情况3单调坡度有平坡的情况了
所以为什么这样一改就可以了呢坡度有变化又是什么意思
坡度有变化指满足(preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)的条件result波动记录的时候没改前会记录上图2-2-2的这个节点改了后不会记录这个点因为从第一个1到2的时候2往后走就不更新了一直是prediff0的状态这个时候到中间那个2-2-2就不会更新因为没更新prediff0,curdiff0不满足条件不更新。
总代码
// 版本二
class Solution {
public:int wiggleMaxLength(vectorint nums) {if (nums.size() 1) return nums.size();int curDiff 0; // 当前一对差值int preDiff 0; // 前一对差值int result 1; // 记录峰值个数序列默认序列最右边有一个峰值for (int i 0; i nums.size() - 1; i) {curDiff nums[i 1] - nums[i];// 出现峰值if ((preDiff 0 curDiff 0) || (preDiff 0 curDiff 0)) {result;preDiff curDiff; // 注意这里只在摆动变化的时候更新prediff}//上一行是和版本一的差别从外面挪里面了}return result;}
};
总结下就是序列要满足最长摆动序列的条件的话就需要求最多的波动点峰值而波动点的总值就是序列的子序列and最长摆动序列的长度值。然后有三个不同的条件影响单调中平坡上下的坡中平坡以及强制要求情况数组首尾两端。
整完后和我想的不一样3h10min
