网站开发文档编写,网站建设投资预算,企业网站建设平台的功能,wordpress mysql数据库备份目录 1. 题目#xff1a;2. 我的代码#xff1a;小结#xff1a; 1. 题目#xff1a; 如果连续数字之间的差严格地在正数和负数之间交替#xff0c;则数字序列称为 摆动序列 。第一个差#xff08;如果存在的话#xff09;可能是正数或负数。仅有一个元素或者含两个不等… 目录 1. 题目2. 我的代码小结 1. 题目 如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 。第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如 [1, 7, 4, 9, 2, 5] 是一个 摆动序列 因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。 子序列 可以通过从原始序列中删除一些也可以不删除元素来获得剩下的元素保持其原始顺序。
给你一个整数数组 nums 返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1 输入nums [1,7,4,9,2,5] 输出6 解释整个序列均为摆动序列各元素之间的差值为 (6, -3, 5, -7, 3) 。 示例 2 输入nums [1,17,5,10,13,15,10,5,16,8] 输出7 解释这个序列包含几个长度为 7 摆动序列。 其中一个是 [1, 17, 10, 13, 10, 16, 8] 各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。 示例 3 输入nums [1,2,3,4,5,6,7,8,9] 输出2 2. 我的代码
class Solution:def wiggleMaxLength(self, nums: List[int]) - int:# -- 贪心算法 --# 双指针p_fast 1p_slow 0# 快慢指针result 0while p_fast len(nums) - 1:p_fast 1if nums[p_fast - 1] nums[p_fast] and nums[p_fast - 1] nums[p_slow]:k 1result 1p_slow p_fast - 1elif nums[p_fast - 1] nums[p_fast] and nums[p_fast - 1] nums[p_slow]:k -1result 1p_slow p_fast - 1if len(nums) 2:if nums[0] ! nums[len(nums) - 1]:endPoint 2else:if result 0:endPoint 1else:endPoint 2else:if nums[0] ! nums[len(nums) - 1]:endPoint 2else:endPoint 1return result endPoint这里使用贪心算法局部的极值就是要求得的摆动点。首先因为要返回一个值即可所以不需要实际地去将列表做删减只需要统计整个过程中的摆动点的个数即可变为数学问题就是求极值点的个数。什么是极值点来着用数学的定义就是在小区间内这个点最大就是极大值这个点最小就是极小值。
因此我们设置快慢指针分别表示要判断的点的右边的点和左边的点。那么中间要判断的点就是快指针的后一位为什么呢。假设[1, 2, 3, 1]这样的序列。慢指针在[1]快指针在[3]这时要判断的点是[2]因为[2]并不比[1]和[3]都大所以2不是极值点。因为后面要变大的点一定比[1]大所以可以保留慢指针在这个位置要判断的值和快指针一起向前走即可。
再加上两个端点处的摆动点即可如果整个序列只有一个元素则是一个摆动点如果序列元素是2个但是两个值相同则摆动点还是一个如果两个值不相同则摆动点是2个…
端点判断代码如下有点长但是时间复杂度不高
if len(nums) 2:if nums[0] ! nums[len(nums) - 1]:endPoint 2else:if result 0:endPoint 1else:endPoint 2
else:if nums[0] ! nums[len(nums) - 1]:endPoint 2else:endPoint 1小结 关注我给大家分享更多有趣的知识以下是个人公众号提供 ||代码兼职|| ||代码问题求解|| 添加我的公众号即可
