LeetCode/摆动序列
2022/9/3 23:24:47
本文主要是介绍LeetCode/摆动序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
求数组最长摆动子序列长度
1. 动态规划
分两种状态进行转移
up[i]表示数组前i个数的最长上升摆动序列长度
down[i]表示数组前i个数的最长下降摆动序列长度
注意比较条件,以及导致状态转移的原因
class Solution { public: int wiggleMaxLength(vector<int>& nums) { int n = nums.size(); if (n < 2) return n; vector<int> up(n), down(n);//动态规划表 up[0] = down[0] = 1;//初始长度为1 for (int i = 1; i < n; i++) { if (nums[i] > nums[i - 1]) {//如果大于前一元素,开始上升 //前一元素处于波峰,降序比升序少一,从降序和升序皆可更新升序 //前一元素处于波谷,此时降序必然大于升序长度,从降序更新升序 up[i] = down[i - 1] + 1;//更新升序列 //前一元素处于波谷,降序不变 //前一元素处于波峰,大于前一个波谷,故降序依旧不变 down[i] = down[i - 1];//保持降序列 } else if (nums[i] < nums[i - 1]) {//如果小于前一元素,开始下降 up[i] = up[i - 1];//保持升序列 down[i] = up[i - 1] + 1;//更新降序列 } else {//如果等于前一元素,保持不变 up[i] = up[i - 1]; down[i] = down[i - 1]; } } return max(up[n - 1], down[n - 1]); } };
2. 动态规划一维优化
class Solution { public: int wiggleMaxLength(vector<int>& nums) { if (nums.size() < 2) return nums.size(); int up = 1;int down = 1;//初始长度为1 for (int i = 1; i < nums.size(); i++) { if (nums[i] > nums[i - 1]) //如果大于前一元素,开始上升 up = down + 1;//更新升序列 else if (nums[i] < nums[i - 1]) //如果小于前一元素,开始下降 down = up + 1;//更新降序列 } return max(up, down); } };
3. 贪心法
统计所有波峰波谷即可
class Solution { public: int wiggleMaxLength(vector<int>& nums) { int n = nums.size(); if (n < 2) return n; int prevdiff = nums[1] - nums[0];//上一个摆动趋势 int ret = prevdiff != 0 ? 2 : 1;//波峰和波谷的个数 for (int i = 2; i < n; i++) { int diff = nums[i] - nums[i - 1];//当前摆动趋势 //上一次向下摆或不摆,同时当前向上摆,说明后面存在一个波峰 //上一次向上摆或不摆,同时当前向下摆,说明后面存在波谷 if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) { ret++; prevdiff = diff;//更新上一个摆动趋势 } } return ret; } };
这篇关于LeetCode/摆动序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!