10000 refactor 62 · erlieStar/Leetcode@9146cdf · GitHub
[go: up one dir, main page]
Skip to content

Commit 9146cdf

Browse files
fishercoder1534fishercoder1534
committed
refactor 62
1 parent cdb9da0 commit 9146cdf

File tree

2 files changed

+43
-51
lines changed

2 files changed

+43
-51
lines changed

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

Lines changed: 22 additions & 51 deletions
Original file line numberDiff line numberDiff line change
@@ -1,63 +1,34 @@
11
package com.fishercoder.solutions;
22

3-
import com.fishercoder.common.utils.CommonUtils;
4-
5-
/**Unique Paths
3+
/**
4+
* 62. Unique Paths
65
76
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
87
The robot can only move either down or right at any point in time. The robot is trying to reach
98
the bottom-right corner of the grid (marked 'Finish' in the diagram below).
109
11-
How many possible unique paths are there?*/
10+
How many possible unique paths are there?
11+
*/
1212
public class _62 {
13-
14-
/**Another typical DP question, use a 2d array:
15-
* the first row and the first column need to be initialized to be 1 since there's only one way to reach every
16-
* position in the first row and the first column: either from left or top.*/
17-
public int uniquePaths(int m, int n) {
18-
int[][] dp = new int[m][n];
19-
for (int i = 0; i < m; i++) {
20-
dp[i][0] = 1;
21-
}
22-
for (int i = 0; i < n; i++) {
23-
dp[0][i] = 1;
24-
}
25-
26-
for (int i = 1; i < m; i++) {
27-
for (int j = 1; j < n; j++) {
28-
int ways = 0;
29-
if (i - 1 >= 0) {
30-
ways += dp[i - 1][j];
31-
}
32-
if (j - 1 >= 0) {
33-
ways += dp[i][j - 1];
34-
}
35-
dp[i][j] = ways;
36-
}
37-
}
38-
CommonUtils.printMatrix(dp);
39-
return dp[m - 1][n - 1];
40-
}
4113

42-
//and we can actually put the two initialization for loop into the one
43-
public int uniquePaths_merged_for_loop(int m, int n) {
44-
int[][] dp = new int[m][n];
45-
for (int i = 0; i < m; i++) {
46-
for (int j = 0; j < n; j++) {
47-
if (i == 0 || j == 0) {
48-
dp[i][j] = 1;
49-
} else {
50-
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
51-
}
52-
}
14+
public static class Solution1 {
15+
/**
16+
* Another typical DP question, use a 2d array: the first row and the first column need to be
17+
* initialized to be 1 since there's only one way to reach every position in the first row and
18+
* the first column: either from left or top.
19+
*/
20+
public int uniquePaths(int m, int n) {
21+
int[][] dp = new int[m][n];
22+
for (int i = 0; i < m; i++) {
23+
for (int j = 0; j < n; j++) {
24+
if (i == 0 || j == 0) {
25+
dp[i][j] = 1;
26+
} else {
27+
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
28+
}
5329
}
54-
return dp[m - 1][n - 1];
55-
}
56-
57-
public static void main(String... strings) {
58-
_62 test = new _62();
59-
int m = 1;
60-
int n = 2;
61-
System.out.println(test.uniquePaths(m, n));
30+
}
31+
return dp[m - 1][n - 1];
6232
}
33+
}
6334
}

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

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._62;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static junit.framework.Assert.assertEquals;
8+
9+
public class _62Test {
10+
private static _62.Solution1 solution1;
11+
12+
@BeforeClass
13+
public static void setup() {
14+
solution1 = new _62.Solution1();
15+
}
16+
17+
@Test
18+
public void test1() {
19+
assertEquals(1, solution1.uniquePaths(1, 2));
20+
}
21+
}

0 commit comments

Comments
 (0)
0