当前位置:网站首页>LeetCode brush # 376 # Medium - swing sequence
LeetCode brush # 376 # Medium - swing sequence
2022-07-31 07:09:00 【Arrows with water dragon turtles】
Discussion on the idea of swing sequence and source code
The topic of swing sequence is as shown in the figure below. This problem belongs to the topic of array class and dynamic programming type. It mainly examines the use of dynamic programming method and the understanding of array structure.The author of the title of this article thinks of two methods, namely the greedy method and the dynamic programming method. The greedy method is written in Java, and the dynamic programming method is written in Python. Of course, this may not be the optimal solution.come up with a faster algorithm.
I think this topic can be solved using the greedy methodTo solve, first initialize the parameters and calculate the length of the array, then start traversing the loop to determine whether each element is greater than the previous element, if so, add 1 to the downtrend parameter and assign it to the uptrend parameter; if it is less than the value of the previous element, thenAdd 1 to the uptrend parameter and assign it to the downtrend parameter until the end of the cycle and judge the larger value of the uptrend parameter and the downtrend parameter as the return result and return.Then according to this idea our Java code is as follows:
#Fire-breathing dragon and water arrow turtleclass Solution {public int wiggleMaxLength(int[] nums) {int downNum = 1;int upNum = 1;int numLen = nums.length;for (int ir = 1; ir < numLen; ir++) {if (nums[ir] > nums[ir - 1])upNum = downNum + 1;else if (nums[ir] < nums[ir - 1])downNum = upNum + 1;}if(numLen==0){return 0;}else{return Math.max(downNum, upNum);}}}
Obviously, our greedy method works well,It can also be solved using dynamic programming methods.First calculate the length of the array to determine whether the length is less than 2, and if so, return the length result directly.Then initialize the uptrend and downtrend parameters to 1, and start traversing the loop to determine whether each element is greater than the previous element. If so, add 1 to the downtrend parameter and assign it to the uptrend parameter; if not, add the uptrend parameter to the uptrend parameter.After 1, it is assigned to the down parameter until the loop traversal ends and the larger value of the up trend parameter and the down trend parameter is judged and the result is returned.So according to this idea, it can be solved, the following is the Python code:
#Fire-breathing dragon and water arrow turtleclass Solution:def wiggleMaxLength(self, nums: List[int]) -> int:numLen = len(nums)if(numLen < 2):return numLenupNum = 1downNum = 1for jr in range(1,numLen):if nums[jr] > nums[jr - 1]:upNum = downNum + 1elif nums[jr] < nums[jr - 1]:downNum = upNum + 1return max(upNum, downNum)
From the results, the Java version of the greedy method is efficient, and the speed of the Python version of the dynamic programming method is also OK, but there should be more methods to further speed up, I hope friends can give me more advice, thank you very much.
边栏推荐
猜你喜欢
随机推荐
浅析瀑布流布局原理及实现方式
成员内部类使用方式(工作)
NFS共享存储服务
Database Principles Homework 3 — JMU
Oracle入门 13 - Linux文件目录类命令
群晖NAS配置阿里云盘同步
Oracle入门 03 - Linux / Unix 系统基础知识
OneManager搭建
选择排序法
Basic usage of Koa framework
安装和使用uView
Oracle 日期函数相关
2022.7.29 数组
小实战项目之——吃货联盟订餐系统
TypeScript基本类型
vmware搭建redis集群遇到问题
DDL+DML+DQL
tidyverse笔记——tidyr包
svn冲突产生原因
Oracle入门 12 - Linux 磁盘分区及LVM实战