Skip to content

Commit a7390b3

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0839.Similar String Groups
1 parent 4962c02 commit a7390b3

File tree

21 files changed

+556
-43
lines changed

21 files changed

+556
-43
lines changed

‎lcof2/剑指 Offer II 105. 岛屿的最大面积/README.md

Lines changed: 31 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,6 @@
4242

4343
<p>注意：本题与主站 695&nbsp;题相同：&nbsp;<a href="https://leetcode-cn.com/problems/max-area-of-island/">https://leetcode-cn.com/problems/max-area-of-island/</a></p>
4444

45-
4645
## 解法
4746

4847
<!-- 这里可写通用的实现逻辑 -->
@@ -105,7 +104,7 @@ def find(x):
105104

106105
# 合并a和b所在的两个集合
107106
p[find(a)] = find(b)
108-
d[find(a)] = dinstance
107+
d[find(a)] = distance
109108
```
110109

111110
<!-- tabs:start -->
@@ -127,7 +126,7 @@ class Solution:
127126
for x, y in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
128127
res += dfs(grid, i + x, j + y, m, n)
129128
return res
130-
129+
131130
m, n = len(grid), len(grid[0])
132131
res = 0
133132
for i in range(m):
@@ -145,12 +144,12 @@ class Solution:
145144
m, n = len(grid), len(grid[0])
146145
p = list(range(m * n))
147146
size = [1] * (m * n)
148-
147+
149148
def find(x):
150149
if p[x] != x:
151150
p[x] = find(p[x])
152151
return p[x]
153-
152+
154153
for i in range(m):
155154
for j in range(n):
156155
if grid[i][j] == 1:
@@ -272,29 +271,36 @@ DFS：
272271

273272
```ts
274273
function maxAreaOfIsland(grid: number[][]): number {
275-
let m = grid.length, n = grid[0].length;
276-
let res = 0;
277-
for (let i = 0; i < m; ++i) {
278-
for (let j = 0; j < n; ++j) {
279-
if (grid[i][j] == 1) {
280-
res = Math.max(dfs(grid, i, j), res);
281-
}
282-
}
274+
let m = grid.length,
275+
n = grid[0].length;
276+
let res = 0;
277+
for (let i = 0; i < m; ++i) {
278+
for (let j = 0; j < n; ++j) {
279+
if (grid[i][j] == 1) {
280+
res = Math.max(dfs(grid, i, j), res);
281+
}
283282
}
284-
return res;
285-
};
283+
}
284+
return res;
285+
}
286286

287287
function dfs(grid: number[][], i: number, j: number): number {
288-
let m = grid.length, n = grid[0].length;
289-
if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] == 0) {
290-
return 0;
291-
}
292-
grid[i][j] = 0;
293-
let res = 1;
294-
for (let [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
295-
res += dfs(grid, i + dx, j + dy);
296-
}
297-
return res;
288+
let m = grid.length,
289+
n = grid[0].length;
290+
if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] == 0) {
291+
return 0;
292+
}
293+
grid[i][j] = 0;
294+
let res = 1;
295+
for (let [dx, dy] of [
296+
[0, 1],
297+
[0, -1],
298+
[1, 0],
299+
[-1, 0],
300+
]) {
301+
res += dfs(grid, i + dx, j + dy);
302+
}
303+
return res;
298304
}
299305
```
300306

‎lcof2/剑指 Offer II 116. 朋友圈/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -111,7 +111,7 @@ def find(x):
111111

112112
# 合并a和b所在的两个集合
113113
p[find(a)] = find(b)
114-
d[find(a)] = dinstance
114+
d[find(a)] = distance
115115
```
116116

117117
<!-- tabs:start -->

‎lcof2/剑指 Offer II 118. 多余的边/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -108,7 +108,7 @@ def find(x):
108108

109109
# 合并a和b所在的两个集合
110110
p[find(a)] = find(b)
111-
d[find(a)] = dinstance
111+
d[find(a)] = distance
112112
```
113113

114114
对于本题，先遍历所有的边，如果边的两个节点已经属于同个集合，说明两个节点已经相连，若再将这条件加入集合中，就会出现环，因此可以直接返回这条边。

‎solution/0200-0299/0261.Graph Valid Tree/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -80,7 +80,7 @@ def find(x):
8080

8181
# 合并a和b所在的两个集合
8282
p[find(a)] = find(b)
83-
d[find(a)] = dinstance
83+
d[find(a)] = distance
8484
```
8585

8686
<!-- tabs:start -->

‎solution/0300-0399/0323.Number of Connected Components in an Undirected Graph/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -95,7 +95,7 @@ def find(x):
9595

9696
# 合并a和b所在的两个集合
9797
p[find(a)] = find(b)
98-
d[find(a)] = dinstance
98+
d[find(a)] = distance
9999
```
100100

101101
<!-- tabs:start -->

‎solution/0500-0599/0547.Number of Provinces/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -110,7 +110,7 @@ def find(x):
110110

111111
# 合并a和b所在的两个集合
112112
p[find(a)] = find(b)
113-
d[find(a)] = dinstance
113+
d[find(a)] = distance
114114
```
115115

116116
<!-- tabs:start -->

‎solution/0600-0699/0684.Redundant Connection/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -104,7 +104,7 @@ def find(x):
104104

105105
# 合并a和b所在的两个集合
106106
p[find(a)] = find(b)
107-
d[find(a)] = dinstance
107+
d[find(a)] = distance
108108
```
109109

110110
对于本题，先遍历所有的边，如果边的两个节点已经属于同个集合，说明两个节点已经相连，若再将这条件加入集合中，就会出现环，因此可以直接返回这条边。

‎solution/0600-0699/0695.Max Area of Island/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -100,7 +100,7 @@ def find(x):
100100

101101
# 合并a和b所在的两个集合
102102
p[find(a)] = find(b)
103-
d[find(a)] = dinstance
103+
d[find(a)] = distance
104104
```
105105

106106
<!-- tabs:start -->

‎solution/0700-0799/0737.Sentence Similarity II/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -87,7 +87,7 @@ def find(x):
8787

8888
# 合并a和b所在的两个集合
8989
p[find(a)] = find(b)
90-
d[find(a)] = dinstance
90+
d[find(a)] = distance
9191
```
9292

9393
对于本题，将相似对的所有单词转换为下标，然后套用并查集模板，将相似对合并。

‎solution/0700-0799/0765.Couples Holding Hands/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -103,7 +103,7 @@ def find(x):
103103

104104
# 合并a和b所在的两个集合
105105
p[find(a)] = find(b)
106-
d[find(a)] = dinstance
106+
d[find(a)] = distance
107107
```
108108

109109
<!-- tabs:start -->

0 commit comments

Comments
 (0)