8000 add 1034 · githubniraj/Leetcode@83d657a · GitHub
[go: up one dir, main page]
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
Appearance settings

Commit 83d657a

Browse files
fishercoder1534fishercoder1534
committed
add 1034
1 parent 5628481 commit 83d657a

File tree

3 files changed

+89
-0
lines changed
  • paginated_contents/algorithms/2nd_thousand
  • src
    • main/java/com/fishercoder/solutions/secondthousand
    • test/java/com/fishercoder/secondthousand< 8000 /span>

3 files changed

+89
-0
lines changed

‎paginated_contents/algorithms/2nd_thousand/README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -441,6 +441,7 @@
441441
| 1043 | [Partition Array for Maximum Sum](https://leetcode.com/problems/partition-array-for-maximum-sum/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1043.java) | | Medium | DP |
442442
| 1038 | [Binary Search Tree to Greater Sum Tree](https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1038.java) | | Medium | DFS, tree |
443443
| 1037 | [Valid Boomerang](https://leetcode.com/problems/valid-boomerang/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1037.java) | | Easy | Math |
444+
| 1034 | [Coloring A Border](https://leetcode.com/problems/coloring-a-border/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1034.java) | | Medium | DFS |
444445
| 1033 | [Moving Stones Until Consecutive](https://leetcode.com/problems/moving-stones-until-consecutive/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1033.java) | | Easy | Math |
445446
| 1030 | [Matrix Cells in Distance Order](https://leetcode.com/problems/matrix-cells-in-distance-order/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1030.java) | | Easy |
446447
| 1029 | [Two City Scheduling](https://leetcode.com/problems/two-city-scheduling/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1029.java) | | Easy |

‎src/main/java/com/fishercoder/solutions/secondthousand/_1034.java

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package com.fishercoder.solutions.secondthousand;
2+
3+
public class _1034 {
4+
public static class Solution1 {
5+
/**
6+
* My completely original solution.
7+
*/
8+
int[] dirs = new int[]{0, 1, 0, -1, 0};
9+
10+
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
11+
int m = grid.length;
12+
int n = grid[0].length;
13+
boolean[][] visited = new boolean[m][n];
14+
visited[row][col] = true;
15+
//copy the input as the final output so that we keep the input intact during dfs, otherwise, it'll lead to incorrect result like in test case 3
16+
int[][] result = new int[m][n];
17+
for (int i = 0; i < m; i++) {
18+
for (int j = 0; j < n; j++) {
19+
result[i][j] = grid[i][j];
20+
}
21+
}
22+
return dfs(grid, row, col, color, m, n, grid[row][col], visited, result);
23+
}
24+
25+
private int[][] dfs(int[][] grid, int row, int col, int color, int m, int n, int originalColor, boolean[][] visited, int[][] result) {
26+
if (row == 0 || col == 0 || row == m - 1 || col == n - 1 || neighborDiffColor(row, col, grid, originalColor, m, n)) {
27+
result[row][col] = color;
28+
}
29+
for (int i = 0; i < dirs.length - 1; i++) {
30+
int nextRow = dirs[i] + row;
31+
int nextCol = dirs[i + 1] + col;
32+
if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] == originalColor && !visited[nextRow][nextCol]) {
33+
visited[nextRow][nextCol] = true;
34+
dfs(grid, nextRow, nextCol, color, m, n, originalColor, visited, result);
35+
}
36+
}
37+
return result;
38+
}
39+
40+
private boolean neighborDiffColor(int row, int col, int[][] grid, int originalColor, int m, int n) {
41+
//if any of the four neighbors has a different color, we consider this cell as a boarding cell as well as it's a boarder to this connected component
42+
for (int i = 0; i < dirs.length - 1; i++) {
43+
int nextRow = row + dirs[i];
44+
int nextCol = col + dirs[i + 1];
45+
if (nextRow >= 0 && nextCol >= 0 && nextRow < m && nextCol < n && grid[nextRow][nextCol] != originalColor) {
46+
return true;
47+
}
48+
}
49+
return false;
50+
}
51+
}
52+
}

‎src/test/java/com/fishercoder/secondthousand/_1034Test.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package com.fishercoder.secondthousand;
2+
3+
import com.fishercoder.common.utils.CommonUtils;
4+
import com.fishercoder.solutions.secondthousand._1034;
5+
import org.junit.jupiter.api.BeforeEach;
6+
import org.junit.jupiter.api.Test;
7+
8+
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
9+
10+
public class _1034Test {
11+
private static _1034.Solution1 solution1;
12+
13+
@BeforeEach
14+
public void setup() {
15+
solution1 = new _1034.Solution1();
16+
}
17+
18+
@Test
19+
public void test1() {
20+
assertArrayEquals(CommonUtils.convertLeetCodeRegularRectangleArrayInputIntoJavaArray("[3,3],[3,2]"),
21+
solution1.colorBorder(CommonUtils.convertLeetCodeRegularRectangleArrayInputIntoJavaArray("[1,1],[1,2]"), 0, 0, 3));
22+
}
23+
24+
@Test
25+
public void test2() {
26+
assertArrayEquals(CommonUtils.convertLeetCodeRegularRectangleArrayInputIntoJavaArray("[1,2,1],[1,2,2],[2,2,1]"),
27+
solution1.colorBorder(CommonUtils.convertLeetCodeRegularRectangleArrayInputIntoJavaArray("[1,2,1],[1,2,2],[2,2,1]"), 1, 1, 2));
28+
}
29+
30+
@Test
31+
public void test3() {
32+
assertArrayEquals(CommonUtils.convertLeetCodeRegularRectangleArrayInputIntoJavaArray("[1,1,1,1,1,2],[1,2,1,1,1,2],[1,1,1,1,1,2]"),
33+
solution1.colorBorder(CommonUtils.convertLeetCodeRegularRectangleArrayInputIntoJavaArray("[1,2,1,2,1,2],[2,2,2,2,1,2],[1,2,2,2,1,2]"), 1, 3, 1));
34+
}
35+
36+
}

0 commit comments

Comments
 (0)
0