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

Commit9b9472c

Browse files
edit 200
1 parentb6fd947 commit9b9472c

File tree

5 files changed

+172
-160
lines changed

5 files changed

+172
-160
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -408,7 +408,7 @@ Your ideas/fixes/algorithms are more than welcome!
408408
|203|[Remove Linked List Elements](https://leetcode.com/problems/remove-linked-list-elements/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_203.java)| O(n)|O(1) | Easy
409409
|202|[Happy Number](https://leetcode.com/problems/happy-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_202.java)| O(k)|O(k) | Easy
410410
|201|[Bitwise AND of Numbers Range](https://leetcode.com/problems/bitwise-and-of-numbers-range/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_201.java)| O(min(m,n))|O(1) | Medium | Bit Manipulation
411-
|200|[Number of Islands](https://leetcode.com/problems/number-of-islands/)|[Union Find](../master/src/main/java/com/fishercoder/solutions/_200UnionFind.java)[DFS](../master/MEDIUM/src/medium/_200DFS.java)| O(m*n)|O(m*n) | Medium| Union Find, DFS
411+
|200|[Number of Islands](https://leetcode.com/problems/number-of-islands/)|[Solution](../master/MEDIUM/src/medium/_200.java)| O(m*n)|O(m*n) | Medium| Union Find, DFS
412412
|199|[Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_199.java)| O(n)|O(n)| Medium | BFS
413413
|198|[House Robber](https://leetcode.com/problems/house-robber/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_198.java)| O(n)|O(n)| Easy | DP
414414
|191|[Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_191.java)| O(n)|O(1)| Easy | Bit Manipulation
Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,116 @@
1+
packagecom.fishercoder.solutions;
2+
3+
/**
4+
* 200. Number of Islands
5+
* Given a 2d grid map of '1's (land) and '0's (water),
6+
* count the number of islands.
7+
* An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
8+
* You may assume all four edges of the grid are all surrounded by water.
9+
10+
Example 1:
11+
12+
11110
13+
11010
14+
11000
15+
00000
16+
Answer: 1
17+
18+
Example 2:
19+
20+
11000
21+
11000
22+
00100
23+
00011
24+
Answer: 3
25+
26+
*/
27+
publicclass_200 {
28+
29+
publicstaticclassDFSSolution {
30+
31+
publicintnumIslands(char[][]grid) {
32+
if (grid ==null ||grid.length ==0)return0;
33+
intcount =0;
34+
intm =grid.length,n =grid[0].length;
35+
for (inti =0;i <m;i++) {
36+
for (intj =0;j <n;j++) {
37+
if (grid[i][j] =='1') {
38+
count++;
39+
dfs(grid,i,j,m,n);
40+
}
41+
}
42+
}
43+
returncount;
44+
}
45+
46+
voiddfs(char[][]grid,inti,intj,intm,intn) {
47+
if (i <0 ||i >=m ||j <0 ||j >=n ||grid[i][j] =='0')return;
48+
grid[i][j] ='0';
49+
dfs(grid,i +1,j,m,n);
50+
dfs(grid,i,j +1,m,n);
51+
dfs(grid,i -1,j,m,n);
52+
dfs(grid,i,j -1,m,n);
53+
}
54+
}
55+
56+
publicstaticclassUnionFindSolution {
57+
58+
classUnionFind{
59+
intcount;
60+
intm,n;
61+
int[]ids;
62+
63+
publicUnionFind(char[][]grid){
64+
m =grid.length;
65+
n =grid[0].length;
66+
ids =newint[m*n];
67+
for(inti =0;i <m;i++){
68+
for(intj =0;j <n;j++){
69+
if(grid[i][j] =='1') {
70+
count++;
71+
ids[i*n+j] =i*n+j;
72+
}
73+
}
74+
}
75+
}
76+
77+
publicvoidunion(inti,intj){
78+
intx =find(ids,i);
79+
inty =find(ids,j);
80+
if(x !=y) {/**note: this is when x != y,
81+
only in this case, we should union these two nodes, which makes sense naturally.*/
82+
count--;
83+
ids[x] =y;//ids[y] = x; //also works
84+
}
85+
}
86+
87+
publicintfind(int[]ids,inti){
88+
if(ids[i] ==i)returni;
89+
returnfind(ids,ids[i]);
90+
}
91+
}
92+
93+
publicintnumIslands(char[][]grid) {
94+
if(grid ==null ||grid.length ==0 ||grid[0].length ==0)return0;
95+
int[]dirs =newint[]{0,1,0,-1,0};
96+
UnionFinduf =newUnionFind(grid);
97+
intm =grid.length,n =grid[0].length;
98+
for(inti =0;i <m;i++){
99+
for(intj =0;j <n;j++){
100+
if(grid[i][j] =='1'){
101+
for(intk =0;k <4;k++){
102+
intx =i+dirs[k];
103+
inty =j+dirs[k+1];
104+
if(x >=0 &&x <m &&y >=0 &&y <n &&grid[x][y] =='1'){
105+
intid1 =i*n+j;
106+
intid2 =x*n+y;
107+
uf.union(id1,id2);
108+
}
109+
}
110+
}
111+
}
112+
}
113+
returnuf.count;
114+
}
115+
}
116+
}

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

Lines changed: 0 additions & 78 deletions
This file was deleted.

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

Lines changed: 0 additions & 81 deletions
This file was deleted.
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.solutions._200;
4+
importorg.junit.BeforeClass;
5+
importorg.junit.Test;
6+
7+
importstaticorg.junit.Assert.assertEquals;
8+
9+
publicclass_200Test {
10+
privatestatic_200.DFSSolutiondfsSolution;
11+
privatestatic_200.UnionFindSolutionunionFindSolution;
12+
privatestaticchar[][]grid;
13+
14+
@BeforeClass
15+
publicstaticvoidsetup(){
16+
dfsSolution =new_200.DFSSolution();
17+
unionFindSolution =new_200.UnionFindSolution();
18+
}
19+
20+
@Test
21+
publicvoidtest1(){
22+
grid =newchar[][]{
23+
{'1','1','1'},
24+
{'0','1','0'},
25+
{'1','1','1'},
26+
};
27+
assertEquals(1,dfsSolution.numIslands(grid));
28+
assertEquals(1,unionFindSolution.numIslands(grid));
29+
}
30+
31+
@Test
32+
publicvoidtest2(){
33+
grid =newchar[][]{
34+
{'1','1','1','1','0'},
35+
{'1','1','0','1','0'},
36+
{'1','1','0','0','0'},
37+
{'0','0','0','0','0'},
38+
};
39+
assertEquals(0,dfsSolution.numIslands(grid));
40+
assertEquals(0,unionFindSolution.numIslands(grid));
41+
}
42+
43+
@Test
44+
publicvoidtest3(){
45+
grid =newchar[][]{
46+
{'1','1','0','0','0'},
47+
{'1','1','0','0','0'},
48+
{'0','0','1','0','0'},
49+
{'0','0','0','1','1'},
50+
};
51+
assertEquals(3,dfsSolution.numIslands(grid));
52+
assertEquals(3,unionFindSolution.numIslands(grid));
53+
}
54+
55+
}

0 commit comments

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