leetcode376. Wiggle Subsequence

CoffeX 發布于2019-08-16 17:10 / 3496人閱讀

摘要：題目要求扭動序列是指數組中的相鄰兩個元素的差保證嚴格的正負交替，如數組中相鄰兩個元素的差為，滿足扭動序列的要求。現在要求從一個數組中，找到長度最長的扭動子序列，并返回其長度。即前一個元素和當前元素構成下降序列，因此代碼如下

題目要求

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:

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

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

Input: [1,2,3,4,5,6,7,8,9]
Output: 2
Follow up:
Can you do it in O(n) time?

扭動序列是指數組中的相鄰兩個元素的差保證嚴格的正負交替，如[1,7,4,9,2,5]數組中相鄰兩個元素的差為6,-3,5,-7,3，滿足扭動序列的要求。現在要求從一個數組中，找到長度最長的扭動子序列，并返回其長度。

思路和代碼

這是一個可以通過動態規劃來解決的問題。動態規劃的特點就是，加入我知道第i個元素的結果，那么第i+1個元素的結果可以由其推到出來。這里假設我們知道，以第i個元素為止的最長子序列長度，包括上升序列up和下降序列down，則第i+1個元素的可能情況如下：

nums[i+1]>nums[i]: 即前一個元素和當前元素構成上升序列，因此up[i+1]=down[i]+1, down[i+1]=down[i]，這是指以第i個元素為結尾的上升序列應當基于第i-1個元素為結尾的下降序列，而以第i個元素為結尾的下降序列，等同于基于第i-1個元素為結尾的下降序列。

nums[i+1]>nums[i]: 即前一個元素和當前元素構成下降序列，因此down[i+1]=up[i]+1, up[i+1]=up[i]

nums[i+1]=nums[i]: down[i+1]=down[i], up[i+1]=up[i]

代碼如下：

    public int wiggleMaxLength(int[] nums) {
        if( nums.length == 0 ) return 0;
        int[] up = new int[nums.length];
        int[] down = new int[nums.length];
        up[0] = 1;
        down[0] = 1;
        for(int i = 1 ; i nums[i-1]) {
                up[i] = down[i-1] + 1;
                down[i] = down[i-1];
            }else if(nums[i] < nums[i-1]) {
                down[i] = up[i-1] + 1;
                up[i] = up[i-1];
            }else {
                down[i] = down[i-1];
                up[i] = up[i-1];
            }
        }
        return Math.max(up[nums.length-1], down[nums.length-1]);
    }

GPU云服務器云服務器 Wiggle Subsequence Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/74428.html

[LintCode/LeetCode] Wiggle Sort I & Wiggle Sor

摘要：每隔兩位交換一次，如，處理為。難點是會有相等的元素，而要求相鄰元素除了外，不能相等。那么就不能取排序后相鄰的元素交換，而要和后面的元素交換。例如犧牲空間的做法是，建立一個新數組，按照我們想要的規律放入元素，最后回原數組。 Wiggle Sort Problem Given an unsorted array nums, reorder it in-place such that num...

linkFly 2019-08-14 16:22 評論0 收藏0
[Leetcode] Wiggle Sort 搖擺排序

摘要：就能滿足題目要求。代碼先將數組排序將數組中一對一對交換交換法復雜度時間空間思路題目對搖擺排序的定義有兩部分如果是奇數，如果是偶數，所以我們只要遍歷一遍數組，把不符合的情況交換一下就行了。 Wiggle Sort Given an unsorted array nums, reorder it in-place such that nums[0] = nums[2] = nums[i ...

LancerComet 2019-08-14 12:35 評論0 收藏0
[LeetCode] 280. Wiggle Sort

Problem Given an unsorted array nums, reorder it in-place such that nums[0] = nums[2] nums[i-1]) swap(nums, i, i-1); } } } private void swap(int[] nums, int i, int j) { ...

archieyang 2019-08-16 14:00 評論0 收藏0
Wiggle Sort & II

摘要：如果沒復雜度的要求，先也可以，再交叉放入數字也可以。交叉的時候注意是按照，降序的。 Wiggle Sort 題目鏈接：https://leetcode.com/problems... 這道題允許等號，相對簡單，有兩種方法：1. sort然后交換奇數位和它下一位的元素，2. 不滿足條件的時候直接交換可以用遞推來說明一下這么做的正確性：假設到第i位之前都滿足題目要求的關系現在比較...

Moxmi 2019-08-14 17:18 評論0 收藏0
LeetCode[300] Longest Increasing Subsequence

摘要：再用二分法找當前值應該在排好序的數組中的插入位置。因為要找的是最長的序列，所以每次將排好序的數組中替換成已經排好序的，會能保證得到的結果是最長的。保證升序相等也要替換這個值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...

blankyao 2019-08-14 15:01 評論0 收藏0