8000 refactor 63 · erlieStar/Leetcode@6835182 · GitHub
[go: up one dir, main page]
Skip to content

Commit 6835182

Browse files
fishercoder1534fishercoder1534
committed
refactor 63
1 parent 9146cdf commit 6835182

File tree

2 files changed

+79
-62
lines changed

2 files changed

+79
-62
lines changed

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

Lines changed: 35 additions & 62 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,9 @@
11
package com.fishercoder.solutions;
22

3-
import com.fishercoder.common.utils.CommonUtils;
3+
/**
4+
* 63. Unique Paths II
45
5-
/**63. Unique Paths II
6-
*
7-
Follow up for "Unique Paths":
6+
Follow up for "Unique Paths":
87
98
Now consider if some obstacles are added to the grids. How many unique paths would there be?
109
@@ -22,70 +21,44 @@
2221
2322
Note: m and n will be at most 100.*/
2423
public class _63 {
24+
public static class Solution1 {
2525
/**
26-
* Idea: grid[i][j] has to be set to zero if obstacleGrid[i][j] == 1,
27-
* otherwise, we can get dp[i][j] from its top and left dp.
26+
* Idea: grid[i][j] has to be set to zero if obstacleGrid[i][j] == 1, otherwise, we can get
27+
* dp[i][j] from its top and left dp.
2828
*/
2929
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
30-
if (obstacleGrid == null || obstacleGrid.length == 0) {
31-
return 0;
32-
}
30+
if (obstacleGrid == null || obstacleGrid.length == 0) {
31+
return 0;
32+
}
3333

34-
int height = obstacleGrid.length;
35-
int width = obstacleGrid[0].length;
36-
int[][] dp = new int[height][width];
37-
dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
38-
for (int i = 1; i < height; i++) {
39-
dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0];
40-
}
41-
for (int j = 1; j < width; j++) {
42-
dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j - 1];
43-
}
34+
int height = obstacleGrid.length;
35+
int width = obstacleGrid[0].length;
36+
int[][] dp = new int[height][width];
37+
dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
38+
for (int i = 1; i < height; i++) {
39+
dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0];
40+
}
41+
for (int j = 1; j < width; j++) {
42+
dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j - 1];
43+
}
4444

45-
for (int i = 1; i < height; i++) {
46-
for (int j = 1; j < width; j++) {
47-
if (obstacleGrid[i][j] == 1) {
48-
dp[i][j] = 0;
49-
} else {
50-
int paths = 0;
51-
if (obstacleGrid[i - 1][j] == 0) {
52-
paths += dp[i - 1][j];
53-
}
54-
if (obstacleGrid[i][j - 1] == 0) {
55-
paths += dp[i][j - 1];
56-
}
57-
dp[i][j] = paths;
58-
}
45+
for (int i = 1; i < height; i++) {
46+
for (int j = 1; j < width; j++) {
47+
if (obstacleGrid[i][j] == 1) {
48+
dp[i][j] = 0;
49+
} else {
50+
int paths = 0;
51+
if (obstacleGrid[i - 1][j] == 0) {
52+
paths += dp[i - 1][j];
53+
}
54+
if (obstacleGrid[i][j - 1] == 0) {
55+
paths += dp[i][j - 1];
5956
}
57+
dp[i][j] = paths;
58+
}
6059
}
61-
CommonUtils.printMatrix(dp);
62-
return dp[height - 1][width - 1];
63-
}
64-
65-
public static void main(String... strings) {
66-
_63 test = new _63();
67-
// int[][] obstacleGrid = new int[3][3];
68-
// obstacleGrid[0][0] = 0;
69-
// obstacleGrid[0][1] = 0;
70-
// obstacleGrid[0][2] = 0;
71-
// obstacleGrid[1][0] = 0;
72-
// obstacleGrid[1][1] = 1;
73-
// obstacleGrid[1][2] = 0;
74-
// obstacleGrid[2][0] = 0;
75-
// obstacleGrid[2][1] = 0;
76-
// obstacleGrid[2][2] = 0;
77-
78-
// int[][] obstacleGrid = new int[1][2];
79-
// obstacleGrid[0][0] = 1;
80-
// obstacleGrid[0][1] = 0;
81-
82-
int[][] obstacleGrid = new int[2][2];
83-
obstacleGrid[0][0] = 0;
84-
obstacleGrid[0][1] = 0;
85-
obstacleGrid[1][0] = 0;
86-
obstacleGrid[1][1] = 1;
87-
88-
CommonUtils.printMatrix(obstacleGrid);
89-
System.out.println(test.uniquePathsWithObstacles(obstacleGrid));
60+
}
61+
return dp[height - 1][width - 1];
9062
}
63+
}
9164
}

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

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._63;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
public class _63Test {
10+
private static _63.Solution1 solution1;
11+
private static int[][] obstacleGrid;
12+
13+
@BeforeClass
14+
public static void setup() {
15+
solution1 = new _63.Solution1();
16+
}
17+
18+
@Test
19+
public void test1() {
20+
obstacleGrid = new int[][] {
21+
{0, 0},
22+
{0, 1},
23+
};
24+
assertEquals(0, solution1.uniquePathsWithObstacles(obstacleGrid));
25+
}
26+
27+
@Test
28+
public void test2() {
29+
obstacleGrid = new int[][] {
30+
{0, 0, 0},
31+
{0, 1, 0},
32+
{0, 0, 0},
33+
};
34+
assertEquals(2, solution1.uniquePathsWithObstacles(obstacleGrid));
35+
}
36+
37+
@Test
38+
public void test3() {
39+
int[][] obstacleGrid = new int[][] {
40+
{1, 0}
41+
};
42+
assertEquals(0, solution1.uniquePathsWithObstacles(obstacleGrid));
43+
}
44+
}

0 commit comments

Comments
 (0)
0