Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit515724f

Browse files
add a solution for 55
1 parent437ff63 commit515724f

File tree

2 files changed

+36
-3
lines changed

2 files changed

+36
-3
lines changed

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

Lines changed: 23 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -52,7 +52,7 @@ public static class Solution3 {
5252
* Top-down DP.
5353
* Credit: https://leetcode.com/problems/jump-game/solution/ approach 2
5454
* <p>
55-
* Specifically, for this problem, my very own Solution1 and the above Solution2 run much faster than this DP solution.
55+
* Specifically, for this problem, my very own Solution1 and the above Solution2 run much faster than this DP solution, likely due to this is top-down, there's stack overhead.
5656
* But just use this problem to practice DP.
5757
* <p>
5858
* The reason it's called top-down is that it's filling the dp array from the right to the left if you set break points and step through this.
@@ -79,4 +79,26 @@ private boolean canJumpFrom(int index, int[] nums, int[] dp) {
7979
returnfalse;
8080
}
8181
}
82+
83+
publicstaticclassSolution4 {
84+
/**
85+
* This is bottom-up DP.
86+
*/
87+
publicbooleancanJump(int[]nums) {
88+
int[]dp =newint[nums.length];
89+
//0 means unknown, 1 means reachable, 2 means unreachable
90+
dp[nums.length -1] =1;
91+
for (inti =nums.length -2;i >=0;i--) {
92+
intfurthestReach =Math.min(nums[i] +i,nums.length -1);
93+
for (intj =i +1;j <=furthestReach;j++) {
94+
if (dp[j] ==1) {
95+
dp[i] =1;
96+
break;
97+
}
98+
}
99+
}
100+
returndp[0] ==1;
101+
}
102+
103+
}
82104
}

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

Lines changed: 13 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -10,13 +10,15 @@ public class _55Test {
1010
privatestatic_55.Solution1solution1;
1111
privatestatic_55.Solution2solution2;
1212
privatestatic_55.Solution3solution3;
13+
privatestatic_55.Solution4solution4;
1314
privatestaticint[]nums;
1415

1516
@BeforeClass
1617
publicstaticvoidsetup() {
1718
solution1 =new_55.Solution1();
1819
solution2 =new_55.Solution2();
1920
solution3 =new_55.Solution3();
21+
solution4 =new_55.Solution4();
2022
}
2123

2224
@Test
@@ -25,6 +27,7 @@ public void test1() {
2527
assertEquals(false,solution1.canJump(nums));
2628
assertEquals(false,solution2.canJump(nums));
2729
assertEquals(false,solution3.canJump(nums));
30+
assertEquals(false,solution4.canJump(nums));
2831
}
2932

3033
@Test
@@ -33,6 +36,7 @@ public void test2() {
3336
assertEquals(true,solution1.canJump(nums));
3437
assertEquals(true,solution2.canJump(nums));
3538
assertEquals(true,solution3.canJump(nums));
39+
assertEquals(true,solution4.canJump(nums));
3640
}
3741

3842
@Test
@@ -41,6 +45,7 @@ public void test3() {
4145
assertEquals(true,solution1.canJump(nums));
4246
assertEquals(true,solution2.canJump(nums));
4347
assertEquals(true,solution3.canJump(nums));
48+
assertEquals(true,solution4.canJump(nums));
4449
}
4550

4651
@Test
@@ -49,6 +54,7 @@ public void test4() {
4954
assertEquals(true,solution1.canJump(nums));
5055
assertEquals(true,solution2.canJump(nums));
5156
assertEquals(true,solution3.canJump(nums));
57+
assertEquals(true,solution4.canJump(nums));
5258
}
5359

5460
@Test
@@ -57,6 +63,7 @@ public void test5() {
5763
assertEquals(true,solution1.canJump(nums));
5864
assertEquals(true,solution2.canJump(nums));
5965
assertEquals(true,solution3.canJump(nums));
66+
assertEquals(true,solution4.canJump(nums));
6067
}
6168

6269
@Test
@@ -65,6 +72,7 @@ public void test6() {
6572
assertEquals(true,solution1.canJump(nums));
6673
assertEquals(true,solution2.canJump(nums));
6774
assertEquals(true,solution3.canJump(nums));
75+
assertEquals(true,solution4.canJump(nums));
6876
}
6977

7078
@Test
@@ -73,6 +81,7 @@ public void test7() {
7381
assertEquals(false,solution1.canJump(nums));
7482
assertEquals(false,solution2.canJump(nums));
7583
assertEquals(false,solution3.canJump(nums));
84+
assertEquals(false,solution4.canJump(nums));
7685
}
7786

7887
@Test
@@ -81,14 +90,16 @@ public void test8() {
8190
assertEquals(true,solution1.canJump(nums));
8291
assertEquals(true,solution2.canJump(nums));
8392
assertEquals(true,solution3.canJump(nums));
93+
assertEquals(true,solution4.canJump(nums));
8494
}
8595

8696
@Test
8797
publicvoidtest9() {
8898
nums =newint[]{3,2,1,0,4};
89-
// assertEquals(false, solution1.canJump(nums));
90-
// assertEquals(false, solution2.canJump(nums));
99+
assertEquals(false,solution1.canJump(nums));
100+
assertEquals(false,solution2.canJump(nums));
91101
assertEquals(false,solution3.canJump(nums));
102+
assertEquals(false,solution4.canJump(nums));
92103
}
93104

94105

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp