当前位置:网站首页>最长摆动序列[贪心练习]
最长摆动序列[贪心练习]
2022-07-05 20:42:00 【REN_林森】
前言
贪心/动态规划/单调栈,都是考察逻辑能力的一类高级题目,这些题需要分析,需要较好的变通能力。
一、最长摆动序列
二、贪心算法
1、贪心需要满足的条件
最优子结构:规模较大的问题的解由规模较小的子问题的解组成,规模较大的问题的解只由其中一个规模较小的子问题的解决定;
无后效性:后面阶段的求解不会修改前面阶段已经计算好的结果;
贪心选择性质:从局部最优解可以得到全局最优解。
注:其中对无后效性的把握尤为重要。贪心算法就是做出当前状态下的最优选择认为就可以解决问题。
2、思路分析
该题,只需要顺序找到峰和谷就行了,以高峰低谷作为摆动的节点,其体系那贪最值问题。
3、code
package everyday.greed;
public class WiggleMaxLength {
/* target:找最长摆动子序列。 把非峰/谷元素删掉即可,但是这里只需要统计最长摆动序列的长度,而不是最长摆动序列的元素,所以只计算峰/谷节点数,相当于变相删了其他非峰/谷节点。 */
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) return nums.length;
// 核心:只要最高峰/最低谷的元素,即最大最小值,摆动起来。
int curDiff = 0, preDiff = 0, ans = 1;
for (int i = 0; i < nums.length - 1; i++) {
curDiff = nums[i + 1] - nums[i];
// 计算峰 || 计算谷
if (curDiff > 0 && preDiff <= 0 || curDiff < 0 && preDiff >= 0) {
++ans;
preDiff = curDiff;
}
}
return ans;
}
}
总结
1)贪心练习。
参考文献
[1] LeetCode 最长摆动序列
边栏推荐
- 2022 Beijing eye health products exhibition, eye care products exhibition, China eye Expo held in November
- 【愚公系列】2022年7月 Go教学课程 004-Go代码注释
- 中国管理科学研究院凝聚行业专家,傅强荣获智库专家“十佳青年”称号
- Duchefa low melting point agarose PPC Chinese and English instructions
- NPDP如何续证?操作指南来了!
- mysql全面解析json/数组
- AI 从代码中自动生成注释文档
- Analyze the knowledge transfer and sharing spirit of maker Education
- 鸿蒙系统控制LED的实现方法之经典
- matplotlib绘图润色(如何形成高质量的图,例如设如何置字体等)
猜你喜欢
如何让化工企业的ERP库存账目更准确
Wanglaoji pharmaceutical's public welfare activity of "caring for the most lovely people under the scorching sun" was launched in Nanjing
Specification of protein quantitative kit for abbkine BCA method
鸿蒙os第四次学习
Classic implementation of the basic method of intelligent home of Internet of things
Duchefa丨MS培养基含维生素说明书
Make Jar, Not War
小程序事件绑定
Chemical properties and application instructions of prosci Lag3 antibody
小程序全局配置
随机推荐
Abnova丨培养细胞总 RNA 纯化试剂盒中英文说明书
Abbkine trakine F-actin Staining Kit (green fluorescence) scheme
常用的视图容器类组件
Welcome to the game and win rich bonuses: Code Golf Challenge officially launched
Common view container class components
Duchefa cytokinin dihydrozeatin (DHZ) instructions
Ros2 topic [01]: installing ros2 on win10
Simple understanding of interpolation search
Hongmeng OS' fourth learning
ProSci LAG-3 重组蛋白说明书
Pytorch 1.12 was released, officially supporting Apple M1 chip GPU acceleration and repairing many bugs
Abnova丨血液总核酸纯化试剂盒预装相关说明书
教你自己训练的pytorch模型转caffe(三)
Leetcode (347) - top k high frequency elements
Duchefa丨S0188盐酸大观霉素五水合物中英文说明书
Use of thread pool
Is it safe to open a stock account by mobile phone? My home is relatively remote. Is there a better way to open an account?
Duchefa丨MS培养基含维生素说明书
Fundamentals - configuration file analysis
珍爱网微服务底层框架演进从开源组件封装到自研