频道栏目
首页 > 考试 > 其他 > 正文

编程开发Wiggle Subsequence解析

2018-05-05 10:25:17         来源:python编程  
收藏   我要投稿

编程开发Wiggle Subsequence解析

震荡序列:序列中每连续两个数字间的差值在正数与负数间严格交替,即(f(xi)f(xi+1))(f(xi+1)f(xi+2))<0" role="presentation">(f(xi)?f(xi+1))(f(xi+1)?f(xi+2))<0

给定一个序列,返回序列中最长震荡序列的长度。这个震荡序列可以通过在原序列中删除若干(包括0)元素得到。

Examples:

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Notice:
Do it in O(n) time.

解题思路

  把给出序列看作一个函数的函数值,可以得到简单图像如下:

  可以把图像划分为若干段,每段为单调上升或单调下降,且包含若干个数据点,则显然最长震荡序列为在每段取一个点得到的序列。问题转化为求划分得到的段的数目,遍历比较大小确定符号即可。

程序代码
class Solution:
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 1:
            return len(nums)
        count = 1
        sign = -1 #not equal to 0 or 1 is ok
        for i in range(0, len(nums) - 1):
            if nums[i] != nums[i + 1]:
                up = nums[i] < nums[i + 1]
                if sign != up:
                    sign = up
                    count += 1
        return count
上一篇:A Spy in the Metro
下一篇:编程开发sticks问题解析
相关文章
图文推荐
热门新闻

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站