Skip to content

Commit 2793ac5

Browse files
fishercoder1534fishercoder1534
committed
add a solution for 376
1 parent e475ab6 commit 2793ac5

File tree

2 files changed

+96
-70
lines changed

2 files changed

+96
-70
lines changed

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

+27-1
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,32 @@
33
public class _376 {
44

55
public static class Solution1 {
6+
/**
7+
* credit: https://leetcode.com/problems/wiggle-subsequence/discuss/84843/Easy-understanding-DP-solution-with-O(n)-Java-version
8+
*/
9+
public int wiggleMaxLength(int[] nums) {
10+
int len = nums.length;
11+
int[] up = new int[len];
12+
int[] down = new int[len];
13+
up[0] = 1;
14+
down[0] = 1;
15+
for (int i = 1; i < len; i++) {
16+
if (nums[i] > nums[i - 1]) {
17+
up[i] = down[i - 1] + 1;
18+
down[i] = down[i - 1];
19+
} else if (nums[i] < nums[i - 1]) {
20+
down[i] = up[i - 1] + 1;
21+
up[i] = up[i - 1];
22+
} else {
23+
up[i] = up[i - 1];
24+
down[i] = down[i - 1];
25+
}
26+
}
27+
return Math.max(down[len - 1], up[len - 1]);
28+
}
29+
}
30+
31+
public static class Solution2 {
632
public int wiggleMaxLength(int[] nums) {
733
if (nums.length < 2) {
834
return nums.length;
@@ -12,7 +38,7 @@ public int wiggleMaxLength(int[] nums) {
1238
for (int i = 2; i < nums.length; i++) {
1339
int diff = nums[i] - nums[i - 1];
1440
/**ATTN: prevDiff could be zero. e.g. [3,3,3,2,5]
15-
* but diff needs to exactly greater than zero*/
41+
* but diff needs to be exactly greater than zero*/
1642
if ((prevDiff <= 0 && diff > 0) || (prevDiff >= 0) && diff < 0) {
1743
count++;
1844
prevDiff = diff;

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

+69-69
Original file line numberDiff line numberDiff line change
@@ -7,80 +7,80 @@
77
import static org.junit.Assert.assertEquals;
88

99
public class _376Test {
10-
private static _376.Solution1 solution1;
11-
private static int[] nums;
10+
private static _376.Solution1 solution1;
11+
private static int[] nums;
1212

13-
@BeforeClass
14-
public static void setup() {
15-
solution1 = new _376.Solution1();
16-
}
13+
@BeforeClass
14+
public static void setup() {
15+
solution1 = new _376.Solution1();
16+
}
1717

18-
@Test
19-
public void test1() {
20-
nums = new int[] {1, 7, 4, 9, 2, 5};
21-
assertEquals(6, solution1.wiggleMaxLength(nums));
22-
}
18+
@Test
19+
public void test1() {
20+
nums = new int[]{1, 7, 4, 9, 2, 5};
21+
assertEquals(6, solution1.wiggleMaxLength(nums));
22+
}
2323

24-
@Test
25-
public void test2() {
26-
nums = new int[] {1, 17, 5, 10, 13, 15, 10, 5, 16, 8};
27-
assertEquals(7, solution1.wiggleMaxLength(nums));
28-
}
24+
@Test
25+
public void test2() {
26+
nums = new int[]{1, 17, 5, 10, 13, 15, 10, 5, 16, 8};
27+
assertEquals(7, solution1.wiggleMaxLength(nums));
28+
}
2929

30-
@Test
31-
public void test3() {
32-
nums = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
33-
assertEquals(2, solution1.wiggleMaxLength(nums));
34-
}
30+
@Test
31+
public void test3() {
32+
nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
33+
assertEquals(2, solution1.wiggleMaxLength(nums));
34+
}
3535

36-
@Test
37-
public void test4() {
38-
nums =
39-
new int[] {33, 53, 12, 64, 50, 41, 45, 21, 97, 35, 47, 92, 39, 0, 93, 55, 40, 46, 69, 42, 6,
40-
95, 51, 68, 72, 9, 32, 84, 34, 64, 6, 2, 26, 98, 3, 43, 30, 60, 3, 68, 82, 9, 97, 19,
41-
27, 98, 99, 4, 30, 96, 37, 9, 78, 43, 64, 4, 65, 30, 84, 90, 87, 64, 18, 50, 60, 1, 40,
42-
32, 48, 50, 76, 100, 57, 29, 63, 53, 46, 57, 93, 98, 42, 80, 82, 9, 41, 55, 69, 84, 82,
43-
79, 30, 79, 18, 97, 67, 23, 52, 38, 74, 15};
44-
assertEquals(67, solution1.wiggleMaxLength(nums));
45-
}
36+
@Test
37+
public void test4() {
38+
nums =
39+
new int[]{33, 53, 12, 64, 50, 41, 45, 21, 97, 35, 47, 92, 39, 0, 93, 55, 40, 46, 69, 42, 6,
40+
95, 51, 68, 72, 9, 32, 84, 34, 64, 6, 2, 26, 98, 3, 43, 30, 60, 3, 68, 82, 9, 97, 19,
41+
27, 98, 99, 4, 30, 96, 37, 9, 78, 43, 64, 4, 65, 30, 84, 90, 87, 64, 18, 50, 60, 1, 40,
42+
32, 48, 50, 76, 100, 57, 29, 63, 53, 46, 57, 93, 98, 42, 80, 82, 9, 41, 55, 69, 84, 82,
43+
79, 30, 79, 18, 97, 67, 23, 52, 38, 74, 15};
44+
assertEquals(67, solution1.wiggleMaxLength(nums));
45+
}
4646

47-
@Test
48-
public void test5() {
49-
nums = new int[] {3, 3, 3, 2, 5};
50-
assertEquals(3, solution1.wiggleMaxLength(nums));
51-
}
47+
@Test
48+
public void test5() {
49+
nums = new int[]{3, 3, 3, 2, 5};
50+
assertEquals(3, solution1.wiggleMaxLength(nums));
51+
}
5252

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

0 commit comments

Comments
 (0)