8000 add 376 · deepakavs/Leetcode@5577a68 · GitHub
[go: up one dir, main page]
Skip to content

Commit 5577a68

Browse files
fishercoder1534fishercoder1534
committed
add 376
1 parent 249bf6b commit 5577a68

File tree

3 files changed

+111
-0
lines changed

3 files changed

+111
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -191,6 +191,7 @@ Your ideas/fixes/algorithms are more than welcome!
191191
|382|[Linked List Random Node](https://leetcode.com/problems/linked-list-random-node/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_382.java)| O(1)|O(n) | Medium| Reservoir Sampling
192192
|379|[Design Phone Directory](https://leetcode.com/problems/design-phone-directory/)|[Solution](../master/src/main/java/com/fishercoder/solutions/DesignPhoneDirectory.java)| O(1)|O(n) | Medium|
193193
|377|[Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/)|[Solution](../master/src/main/java/com/fishercoder/solutions/CombinationSumIV.java)| O(?)|O(?) | Medium|
194+
|376|[Wiggle Subsequence](https://leetcode.com/problems/wiggle-subsequence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_376.java)| O(n)|O(1) | Medium| DP, Greedy
194195
|375|[Guess Number Higher or Lower II](https://leetcode.com/problems/guess-number-higher-or-lower-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_375.java)| O(n^2)|O(n^2) | Medium| DP
195196
|374|[Guess Number Higher or Lower](https://leetcode.com/problems/guess-number-higher-or-lower/)|[Solution](../master/src/main/java/com/fishercoder/solutions/GuessNumberHigherorLower.java)| O(logn)|O(1) | Easy| Binary Search
196197
|373|[Find K Pairs with Smallest Sums](https://leetcode.com/problems/find-k-pairs-with-smallest-sums/)|[Solution](../master/src/main/java/com/fishercoder/solutions/FindKPairsWithSmallestSums.java)| O(?)|O(?) | Medium| Heap

‎src/main/java/com/fishercoder/solutions/_376.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package com.fishercoder.solutions;
2+
3+
/**
4+
* 376. Wiggle Subsequence
5+
*
6+
* A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly
7+
* alternate between positive and negative.
8+
* The first difference (if one exists) may be either positive or negative.
9+
* A sequence with fewer than two elements is trivially a wiggle sequence.
10+
11+
For example, [1,7,4,9,2,5] is a wiggle sequence because the differences
12+
(6,-3,5,-7,3) are alternately positive and negative.
13+
In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences,
14+
the first because its first two differences are positive and the second because its last difference is zero.
15+
16+
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence.
17+
A subsequence is obtained by deleting some number of elements (eventually, also zero)
18+
from the original sequence, leaving the remaining elements in their original order.
19+
20+
Examples:
21+
Input: [1,7,4,9,2,5]
22+
Output: 6
23+
The entire sequence is a wiggle sequence.
24+
25+
Input: [1,17,5,10,13,15,10,5,16,8]
26+
Output: 7
27+
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
28+
29+
Input: [1,2,3,4,5,6,7,8,9]
30+
Output: 2
31+
32+
Follow up:
33+
Can you do it in O(n) time?
34+
*/
35+
public class _376 {
36+
37+
/**credit: https://leetcode.com/articles/wiggle-subsequence/#approach-5-greedy-approach-accepted*/
38+
public int wiggleMaxLength(int[] nums) {
39+
if (nums.length < 2) return nums.length;
40+
int prevDiff = nums[1] - nums[0];
41+
int count = (prevDiff != 0) ? 2 : 1;
42+
for (int i = 2; i < nums.length; i++) {
43+
int diff = nums[i] - nums[i-1];
44+
/**ATTN: prevDiff could be zero. e.g. [3,3,3,2,5]
45+
* but diff needs to exactly greater than zero*/
46+
if ((prevDiff <= 0 && diff > 0) || (prevDiff >= 0) && diff < 0) {
47+
count++;
48+
prevDiff = diff;
49+
}
50+
}
51+
return count;
52+
}
53+
54+
}

‎src/test/java/com/fishercoder/_376Test.java

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._376;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
/**
10+
* Created by stevesun on 6/11/17.
11+
*/
12+
public class _376Test {
13+
private static _376 test;
14+
private static int[] nums;
15+
16+
@BeforeClass
17+
public static void setup(){
18+
test = new _376();
19+
}
20+
21+
@Test
22+
public void test1(){
23+
nums = new int[]{1,7,4,9,2,5};
24+
assertEquals(6, test.wiggleMaxLength(nums));
25+
}
26+
27+
@Test
28+
public void test2(){
29+
nums = new int[]{1,17,5,10,13,15,10,5,16,8};
30+
assertEquals(7, test.wiggleMaxLength(nums));
31+
}
32+
33+
@Test
34+
public void test3(){
35+
nums = new int[]{1,2,3,4,5,6,7,8,9};
36+
assertEquals(2, test.wiggleMaxLength(nums));
37+
}
38+
39+
@Test
40+
public void test4(){
41+
nums = new int[]{33,53,12,64,50,41,45,21,97,35,47,92,39,0,93,55,40,46,69,42,6,95,51,68,72,9,32,84,34,64,6,2,26,98,3,43,30,60,3,68,82,9,97,19,27,98,99,4,30,96,37,9,78,43,64,4,65,30,84,90,87,64,18,50,60,1,40,32,48,50,76,100,57,29,63,53,46,57,93,98,42,80,82,9,41,55,69,84,82,79,30,79,18,97,67,23,52,38,74,15};
42+
assertEquals(67, test.wiggleMaxLength(nums));
43+
}
44+
45+
@Test
46+
public void test5(){
47+
nums = new int[]{3,3,3,2,5};
48+
assertEquals(3, test.wiggleMaxLength(nums));
49+
}
50+
51+
@Test
52+
public void test6(){
53+
nums = new int[]{372,492,288,399,81,2,320,94,416,469,427,117,265,357,399,456,496,337,355,219,475,295,457,350,490,470,281,127,131,36,430,412,442,174,128,253,1,56,306,295,340,73,253,130,259,223,14,79,409,384,209,151,317,441,156,275,140,224,128,250,290,191,161,472,477,125,470,230,321,5,311,23,27,248,138,284,215,356,320,194,434,136,221,273,450,440,28,179,36,386,482,203,24,8,391,21,500,484,135,348,292,396,145,443,406,61,212,480,455,78,309,318,84,474,209,225,177,356,227,263,181,476,478,151,494,395,23,114,395,429,450,247,245,150,354,230,100,172,454,155,189,33,290,187,443,123,59,358,241,141,39,196,491,381,157,157,134,431,295,20,123,118,207,199,317,188,267,335,315,308,115,321,56,52,253,492,97,374,398,272,74,206,109,172,471,55,452,452,329,367,372,252,99,62,122,287,320,325,307,481,316,378,87,97,457,21,312,249,354,286,196,43,170,500,265,253,19,480,438,113,473,247,257,33,395,456,246,310,469,408,112,385,53,449,117,122,210,286,149,20,364,372,71,26,155,292,16,72,384,160,79,241,346,230,15,427,96,95,59,151,325,490,223,131,81,294,18,70,171,339,14,40,463,421,355,123,408,357,202,235,390,344,198,98,361,434,174,216,197,274,231,85,494,57,136,258,134,441,477,456,318,155,138,461,65,426,162,90,342,284,374,204,464,9,280,391,491,231,298,284,82,417,355,356,207,367,262,244,283,489,477,143,495,472,372,447,322,399,239,450,168,202,89,333,276,199,416,490,494,488,137,327,113,189,430,320,197,120,71,262,31,295,218,74,238,169,489,308,300,260,397,308,328,267,419,84,357,486,289,312,230,64,468,227,268,28,243,267,254,153,407,399,346,385,77,297,273,484,366,482,491,368,221,423,107,272,98,309,426,181,320,77,185,382,478,398,476,22,328,450,299,211,285,62,344,484,395,466,291,487,301,407,28,295,36,429,99,462,240,124,261,387,30,362,161,156,184,188,99,377,392,442,300,98,285,312,312,365,415,367,105,81,378,413,43,326,490,320,266,390,53,327,75,332,454,29,370,392,360,1,335,355,344,120,417,455,93,60,256,451,188,161,388,338,238,26,275,340,109,185};
54+
assertEquals(334, test.wiggleMaxLength(nums));
55+
}
56+
}

0 commit comments

Comments
 (0)
0