当前位置:网站首页>Longest swing sequence [greedy practice]
Longest swing sequence [greedy practice]
2022-07-05 21:05:00 【REN_ Linsen】
Greedy practice
Preface
greedy / Dynamic programming / Monotonic stack , They are all high-level topics that examine logical ability , These questions need to be analyzed , Need better versatility .
One 、 Longest swing sequence
Two 、 Greedy Algorithm
1、 The conditions that greed needs to meet
Optimal substructure : The solution of the larger problem consists of the solution of the smaller subproblem , The solution of the larger problem is determined only by the solution of one of the smaller subproblems ;
No aftereffect : The solution in the later stage will not modify the results calculated in the previous stage ;
Greedy choice nature : The global optimal solution can be obtained from the local optimal solution .
notes : Among them, it is particularly important to grasp the non aftereffect . Greedy algorithm is to make the best choice in the current state and think that it can solve the problem .
2、 Thought analysis
This question , Just find the peaks and valleys in sequence , Take the peak and trough as the nodes of swing , The greedy value problem of its system .
3、code
package everyday.greed;
public class WiggleMaxLength {
/* target: Find the longest wiggler sequence . Take feifeng / Delete the valley element , But here we only need to count the length of the longest swing sequence , Not the element of the longest swing sequence , So only calculate the peak / Valley node points , It is equivalent to deleting other non peaks in disguise / Valley node . */
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) return nums.length;
// The core : As long as the peak / The lowest element , That is, the maximum and minimum value , Swing up .
int curDiff = 0, preDiff = 0, ans = 1;
for (int i = 0; i < nums.length - 1; i++) {
curDiff = nums[i + 1] - nums[i];
// Calculate peak || Calculate Valley
if (curDiff > 0 && preDiff <= 0 || curDiff < 0 && preDiff >= 0) {
++ans;
preDiff = curDiff;
}
}
return ans;
}
}
summary
1) Greedy practice .
reference
边栏推荐
- LeetCode: Distinct Subsequences [115]
- Cutting edge technology for cultivating robot education creativity
- Influence of oscilloscope probe on measurement bandwidth
- 教你自己训练的pytorch模型转caffe(三)
- 珍爱网微服务底层框架演进从开源组件封装到自研
- ClickHouse 复制粘贴多行sql语句报错
- CareerCup它1.8 串移包括问题
- MySQL deep paging optimization with tens of millions of data, and online failure is rejected!
- Pytoch practice -- MNIST dataset handwritten digit recognition
- 树莓派4B上ncnn转换出来的模型调用时总是崩溃(Segment Fault)的原因
猜你喜欢
显示屏DIN 4102-1 Class B1防火测试要求
Analyze the knowledge transfer and sharing spirit of maker Education
[case] Application of positioning - Taobao rotation map
When steam education enters personalized information technology courses
Écrire une interface basée sur flask
Wood board ISO 5660-1 heat release rate mapping test
Which is the best online collaboration product? Microsoft loop, notion, flowus
Pytorch实战——MNIST数据集手写数字识别
XML modeling
Talk about my fate with some programming languages
随机推荐
Duchefa cytokinin dihydrozeatin (DHZ) instructions
股票开户选择哪家证券公司比较好哪家平台更安全
Is it necessary for bazel to learn
Influence of oscilloscope probe on signal source impedance
Dictionary tree simple introductory question (actually blue question?)
Open source SPL eliminates tens of thousands of database intermediate tables
R语言【数据管理】
Prior knowledge of machine learning in probability theory (Part 1)
MYSQL IFNULL使用功能
Utils/index TS tool function
Clear app data and get Icon
postgres 建立连接并删除记录
[case] Application of element display and hiding -- element mask
SYSTEMd resolved enable debug log
Introduction to TS, constructor and its this, inheritance, abstract class and interface
MySQL deep paging optimization with tens of millions of data, and online failure is rejected!
AITM 2-0003 水平燃烧试验
Maker education infiltrating the transformation of maker spirit and culture
Traps in the explode function in PHP
ViewRootImpl和WindowManagerService笔记