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

Commit36183c8

Browse files
refactor 656
1 parentebaf443 commit36183c8

File tree

2 files changed

+33
-32
lines changed

2 files changed

+33
-32
lines changed
Lines changed: 30 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11
packagecom.fishercoder.solutions;
22

3-
43
importjava.util.ArrayList;
54
importjava.util.Arrays;
65
importjava.util.List;
@@ -35,38 +34,40 @@
3534
*/
3635

3736
publicclass_656 {
37+
publicstaticclassSolution1 {
3838

39-
/**
40-
* Time: O(n*B)
41-
* Reference: https://leetcode.com/articles/coin-path/#approach-3-using-dynamic-programming-accepted
42-
*/
43-
publicList<Integer>cheapestJump(int[]A,intB) {
44-
int[]next =newint[A.length];
45-
long[]dp =newlong[A.length];
46-
Arrays.fill(next, -1);
47-
List<Integer>res =newArrayList();
48-
for (inti =A.length -2;i >=0;i--) {
49-
longminCost =Integer.MAX_VALUE;
50-
for (intj =i +1;j <=i +B &&j <A.length;j++) {
51-
if (A[j] >=0) {
52-
longcost =A[i] +dp[j];
53-
if (cost <minCost) {
54-
minCost =cost;
55-
next[i] =j;
39+
/**
40+
* Time: O(n*B)
41+
* Reference: https://leetcode.com/articles/coin-path/#approach-3-using-dynamic-programming-accepted
42+
*/
43+
publicList<Integer>cheapestJump(int[]A,intB) {
44+
int[]next =newint[A.length];
45+
long[]dp =newlong[A.length];
46+
Arrays.fill(next, -1);
47+
List<Integer>res =newArrayList();
48+
for (inti =A.length -2;i >=0;i--) {
49+
longminCost =Integer.MAX_VALUE;
50+
for (intj =i +1;j <=i +B &&j <A.length;j++) {
51+
if (A[j] >=0) {
52+
longcost =A[i] +dp[j];
53+
if (cost <minCost) {
54+
minCost =cost;
55+
next[i] =j;
56+
}
5657
}
5758
}
59+
dp[i] =minCost;
5860
}
59-
dp[i] =minCost;
60-
}
61-
inti;
62-
for (i =0;i <A.length &&next[i] >0;i =next[i]) {
63-
res.add(i+1);
64-
}
65-
if (i ==A.length -1 &&A[i] >=0) {
66-
res.add(A.length);
67-
}else {
68-
returnnewArrayList<>();
61+
inti;
62+
for (i =0;i <A.length &&next[i] >0;i =next[i]) {
63+
res.add(i +1);
64+
}
65+
if(i==A.length -1 &&A[i] >=0) {
66+
res.add(A.length);
67+
}else {
68+
returnnewArrayList<>();
69+
}
70+
returnres;
6971
}
70-
returnres;
7172
}
7273
}

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -14,19 +14,19 @@
1414
* Created by fishercoder on 5/25/17.
1515
*/
1616
publicclass_656Test {
17-
privatestatic_656test;
17+
privatestatic_656.Solution1solution1;
1818
privatestaticint[]A;
1919
privatestaticList<Integer>expected;
2020

2121
@BeforeClass
2222
publicstaticvoidsetup() {
23-
test =new_656();
23+
solution1 =new_656.Solution1();
2424
}
2525

2626
@Test
2727
publicvoidtest1() {
2828
A =newint[]{1,2,4, -1,2};
2929
expected =newArrayList<>(Arrays.asList(1,3,5));
30-
assertEquals(expected,test.cheapestJump(A,2));
30+
assertEquals(expected,solution1.cheapestJump(A,2));
3131
}
3232
}

0 commit comments

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