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

Commitf7cc5e1

Browse files
add articles (#5127)
* add number-of-distinct-islands.md article* add parallel-courses.md article* add the-maze.md article* add the-maze-ii.md article
1 parente7b11aa commitf7cc5e1

File tree

4 files changed

+1607
-0
lines changed

4 files changed

+1607
-0
lines changed
Lines changed: 391 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,391 @@
1+
##1. Brute Force
2+
3+
::tabs-start
4+
5+
```python
6+
classSolution:
7+
defnumDistinctIslands(self,grid: List[List[int]]) ->int:
8+
9+
defcurrent_island_is_unique():
10+
for other_islandin unique_islands:
11+
iflen(other_island)!=len(current_island):
12+
continue
13+
for cell_1, cell_2inzip(current_island, other_island):
14+
if cell_1!= cell_2:
15+
break
16+
else:
17+
returnFalse
18+
returnTrue
19+
20+
# Do a DFS to find all cells in the current island.
21+
defdfs(row,col):
22+
if row<0or col<0or row>=len(grid)or col>=len(grid[0]):
23+
return
24+
if (row, col)in seenornot grid[row][col]:
25+
return
26+
seen.add((row, col))
27+
current_island.append((row- row_origin, col- col_origin))
28+
dfs(row+1, col)
29+
dfs(row-1, col)
30+
dfs(row, col+1)
31+
dfs(row, col-1)
32+
33+
# Repeatedly start DFS's as long as there are islands remaining.
34+
seen=set()
35+
unique_islands= []
36+
for rowinrange(len(grid)):
37+
for colinrange(len(grid[0])):
38+
current_island= []
39+
row_origin= row
40+
col_origin= col
41+
dfs(row, col)
42+
ifnot current_islandornot current_island_is_unique():
43+
continue
44+
unique_islands.append(current_island)
45+
print(unique_islands)
46+
returnlen(unique_islands)
47+
```
48+
49+
```java
50+
classSolution {
51+
52+
privateList<List<int[]>> uniqueIslands=newArrayList<>();// All known unique islands.
53+
privateList<int[]> currentIsland=newArrayList<>();// Current Island
54+
privateint[][] grid;// Input grid
55+
privateboolean[][] seen;// Cells that have been explored.
56+
57+
publicintnumDistinctIslands(int[][]grid) {
58+
this.grid= grid;
59+
this.seen=newboolean[grid.length][grid[0].length];
60+
for (int row=0; row< grid.length; row++) {
61+
for (int col=0; col< grid[0].length; col++) {
62+
dfs(row, col);
63+
if (currentIsland.isEmpty()) {
64+
continue;
65+
}
66+
// Translate the island we just found to the top left.
67+
int minCol= grid[0].length-1;
68+
for (int i=0; i< currentIsland.size(); i++) {
69+
minCol=Math.min(minCol, currentIsland.get(i)[1]);
70+
}
71+
for (int[] cell: currentIsland) {
72+
cell[0]-= row;
73+
cell[1]-= minCol;
74+
}
75+
// If this island is unique, add it to the list.
76+
if (currentIslandUnique()) {
77+
uniqueIslands.add(currentIsland);
78+
}
79+
currentIsland=newArrayList<>();
80+
}
81+
}
82+
return uniqueIslands.size();
83+
}
84+
85+
privatevoiddfs(introw,intcol) {
86+
if (row<0|| col<0|| row>= grid.length|| col>= grid[0].length)return;
87+
if (seen[row][col]|| grid[row][col]==0)return;
88+
seen[row][col]=true;
89+
currentIsland.add(newint[]{row, col});
90+
dfs(row+1, col);
91+
dfs(row-1, col);
92+
dfs(row, col+1);
93+
dfs(row, col-1);
94+
}
95+
96+
privatebooleancurrentIslandUnique() {
97+
for (List<int[]> otherIsland: uniqueIslands) {
98+
if (currentIsland.size()!= otherIsland.size()) {
99+
continue;
100+
}
101+
if (equalIslands(currentIsland, otherIsland)) {
102+
returnfalse;
103+
}
104+
}
105+
returntrue;
106+
}
107+
108+
privatebooleanequalIslands(List<int[]>island1,List<int[]>island2) {
109+
for (int i=0; i< island1.size(); i++) {
110+
if (island1.get(i)[0]!= island2.get(i)[0]|| island1.get(i)[1]!= island2.get(i)[1]) {
111+
returnfalse;
112+
}
113+
}
114+
returntrue;
115+
}
116+
}
117+
```
118+
119+
::tabs-end
120+
121+
###Time & Space Complexity
122+
123+
- Time complexity: $O(M^2 \cdot N^2)$
124+
- Space complexity: $O(N \cdot M)$
125+
126+
> Where $M$ is the number of rows, and $N$ is the number of columns
127+
128+
---
129+
130+
##2. Hash By Local Coordinates
131+
132+
::tabs-start
133+
134+
```python
135+
classSolution:
136+
defnumDistinctIslands(self,grid: List[List[int]]) ->int:
137+
# Do a DFS to find all cells in the current island.
138+
defdfs(row,col):
139+
if row<0or col<0or row>=len(grid)or col>=len(grid[0]):
140+
return
141+
if (row, col)in seenornot grid[row][col]:
142+
return
143+
seen.add((row, col))
144+
current_island.add((row- row_origin, col- col_origin))
145+
dfs(row+1, col)
146+
dfs(row-1, col)
147+
dfs(row, col+1)
148+
dfs(row, col-1)
149+
150+
# Repeatedly start DFS's as long as there are islands remaining.
151+
seen=set()
152+
unique_islands=set()
153+
for rowinrange(len(grid)):
154+
for colinrange(len(grid[0])):
155+
current_island=set()
156+
row_origin= row
157+
col_origin= col
158+
dfs(row, col)
159+
if current_island:
160+
unique_islands.add(frozenset(current_island))
161+
162+
returnlen(unique_islands)
163+
```
164+
165+
```java
166+
classSolution {
167+
168+
privateint[][] grid;
169+
privateboolean[][] seen;
170+
privateSet<Pair<Integer,Integer>> currentIsland;
171+
privateint currRowOrigin;
172+
privateint currColOrigin;
173+
174+
privatevoiddfs(introw,intcol) {
175+
if (row<0|| row>= grid.length|| col<0|| col>= grid[0].length) {
176+
return;
177+
}
178+
if (grid[row][col]==0|| seen[row][col]) {
179+
return;
180+
}
181+
seen[row][col]=true;
182+
currentIsland.add(newPair<>(row- currRowOrigin, col- currColOrigin));
183+
dfs(row+1, col);
184+
dfs(row-1, col);
185+
dfs(row, col+1);
186+
dfs(row, col-1);
187+
}
188+
189+
publicintnumDistinctIslands(int[][]grid) {
190+
this.grid= grid;
191+
this.seen=newboolean[grid.length][grid[0].length];
192+
Set<Set<Pair<Integer,Integer>>> islands=newHashSet<>();
193+
for (int row=0; row< grid.length; row++) {
194+
for (int col=0; col< grid[0].length; col++) {
195+
this.currentIsland=newHashSet<>();
196+
this.currRowOrigin= row;
197+
this.currColOrigin= col;
198+
dfs(row, col);
199+
if (!currentIsland.isEmpty()) {
200+
islands.add(currentIsland);
201+
}
202+
}
203+
}
204+
return islands.size();
205+
}
206+
}
207+
```
208+
209+
::tabs-end
210+
211+
###Time & Space Complexity
212+
213+
- Time complexity: $O(M \cdot N)$
214+
- Space complexity: $O(M \cdot N)$
215+
216+
> Where $M$ is the number of rows, and $N$ is the number of columns
217+
218+
---
219+
220+
##3. Hash By Path Signature
221+
222+
::tabs-start
223+
224+
```python
225+
classSolution:
226+
defnumDistinctIslands(self,grid: List[List[int]]) ->int:
227+
# Do a DFS to find all cells in the current island.
228+
defdfs(row,col,direction):
229+
if row<0or col<0or row>=len(grid)or col>=len(grid[0]):
230+
return
231+
if (row, col)in seenornot grid[row][col]:
232+
return
233+
seen.add((row, col))
234+
path_signature.append(direction)
235+
dfs(row+1, col,"D")
236+
dfs(row-1, col,"U")
237+
dfs(row, col+1,"R")
238+
dfs(row, col-1,"L")
239+
path_signature.append("0")
240+
241+
# Repeatedly start DFS's as long as there are islands remaining.
242+
seen=set()
243+
unique_islands=set()
244+
for rowinrange(len(grid)):
245+
for colinrange(len(grid[0])):
246+
path_signature= []
247+
dfs(row, col,"0")
248+
if path_signature:
249+
unique_islands.add(tuple(path_signature))
250+
251+
returnlen(unique_islands)
252+
```
253+
254+
```java
255+
classSolution {
256+
257+
privateint[][] grid;
258+
privateboolean[][] visited;
259+
privateStringBuffer currentIsland;
260+
261+
publicintnumDistinctIslands(int[][]grid) {
262+
this.grid= grid;
263+
this.visited=newboolean[grid.length][grid[0].length];
264+
Set<String> islands=newHashSet<>();
265+
for (int row=0; row< grid.length; row++) {
266+
for (int col=0; col< grid[0].length; col++) {
267+
currentIsland=newStringBuffer();
268+
dfs(row, col,'0');
269+
if (currentIsland.length()==0) {
270+
continue;
271+
}
272+
islands.add(currentIsland.toString());
273+
}
274+
}
275+
return islands.size();
276+
}
277+
278+
privatevoiddfs(introw,intcol,chardir) {
279+
if (row<0|| col<0|| row>= grid.length|| col>= grid[0].length) {
280+
return;
281+
}
282+
if (visited[row][col]|| grid[row][col]==0) {
283+
return;
284+
}
285+
visited[row][col]=true;
286+
currentIsland.append(dir);
287+
dfs(row+1, col,'D');
288+
dfs(row-1, col,'U');
289+
dfs(row, col+1,'R');
290+
dfs(row, col-1,'L');
291+
currentIsland.append('0');
292+
}
293+
}
294+
```
295+
296+
```cpp
297+
classSolution {
298+
private:
299+
vector<vector<int>>* grid;
300+
vector<vector<bool>> visited;
301+
string currentIsland;
302+
303+
void dfs(int row, int col, char dir) {
304+
if (row < 0 || col < 0 || row >= grid->size() || col >= (*grid)[0].size()) {
305+
return;
306+
}
307+
if (visited[row][col] || (*grid)[row][col] == 0) {
308+
return;
309+
}
310+
visited[row][col] = true;
311+
currentIsland += dir;
312+
dfs(row + 1, col, 'D');
313+
dfs(row - 1, col, 'U');
314+
dfs(row, col + 1, 'R');
315+
dfs(row, col - 1, 'L');
316+
currentIsland += '0';
317+
}
318+
319+
public:
320+
int numDistinctIslands(vector<vector<int>>& grid) {
321+
this->grid = &grid;
322+
visited = vector<vector<bool>>(grid.size(), vector<bool>(grid[0].size(), false));
323+
unordered_set<string> islands;
324+
325+
for (int row = 0; row < grid.size(); row++) {
326+
for (int col = 0; col < grid[0].size(); col++) {
327+
currentIsland = "";
328+
dfs(row, col, '0');
329+
if (currentIsland.empty()) {
330+
continue;
331+
}
332+
islands.insert(currentIsland);
333+
}
334+
}
335+
return islands.size();
336+
}
337+
};
338+
```
339+
340+
```javascript
341+
class Solution {
342+
/**
343+
* @param {number[][]} grid
344+
* @return {number}
345+
*/
346+
numDistinctIslands(grid) {
347+
this.grid = grid;
348+
this.visited = Array.from({ length: grid.length }, () =>
349+
Array(grid[0].length).fill(false)
350+
);
351+
const islands = new Set();
352+
353+
for (let row = 0; row < grid.length; row++) {
354+
for (let col = 0; col < grid[0].length; col++) {
355+
this.currentIsland = [];
356+
this.dfs(row, col, '0');
357+
if (this.currentIsland.length === 0) {
358+
continue;
359+
}
360+
islands.add(this.currentIsland.join(''));
361+
}
362+
}
363+
return islands.size;
364+
}
365+
366+
dfs(row, col, dir) {
367+
if (row < 0 || col < 0 || row >= this.grid.length || col >= this.grid[0].length) {
368+
return;
369+
}
370+
if (this.visited[row][col] || this.grid[row][col] === 0) {
371+
return;
372+
}
373+
this.visited[row][col] = true;
374+
this.currentIsland.push(dir);
375+
this.dfs(row + 1, col, 'D');
376+
this.dfs(row - 1, col, 'U');
377+
this.dfs(row, col + 1, 'R');
378+
this.dfs(row, col - 1, 'L');
379+
this.currentIsland.push('0');
380+
}
381+
}
382+
```
383+
384+
::tabs-end
385+
386+
###Time & Space Complexity
387+
388+
- Time complexity: $O(M \cdot N)$
389+
- Space complexity: $O(M \cdot N)$
390+
391+
> Where $M$ is the number of rows,and $N$ is the number of columns

0 commit comments

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