8000 添加 problem 130 · DontFearAlgorithms/LeetCode-Go@8fa5236 · GitHub
[go: up one dir, main page]
Skip to content
8000

Commit 8fa5236

Browse files
halfrosthalfrost
committed
添加 problem 130
1 parent e29ed86 commit 8fa5236

File tree

4 files changed

+206
-32
lines changed

4 files changed

+206
-32
lines changed

‎Algorithms/0130. Surrounded Regions/130. Surrounded Regions.go

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package leetcode
2+
3+
// 解法一 并查集
4+
func solve(board [][]byte) {
5+
if len(board) == 0 {
6+
return
7+
}
8+
m, n := len(board[0]), len(board)
9+
uf := UnionFind{}
10+
uf.init(n*m + 1) // 特意多一个特殊点用来标记
11+
12+
for i := 0; i < n; i++ {
13+
for j := 0; j < m; j++ {
14+
if (i == 0 || i == n-1 || j == 0 || j == m-1) && board[i][j] == 'O' { //棋盘边缘上的 'O' 点
15+
uf.union(i*m+j, n*m)
16+
} else if board[i][j] == 'O' { //棋盘非边缘上的内部的 'O' 点
17+
if board[i-1][j] == 'O' {
18+
uf.union(i*m+j, (i-1)*m+j)
19+
}
20+
if board[i+1][j] == 'O' {
21+
uf.union(i*m+j, (i+1)*m+j)
22+
}
23+
if board[i][j-1] == 'O' {
24+
uf.union(i*m+j, i*m+j-1)
25+
}
26+
if board[i][j+1] == 'O' {
27+
uf.union(i*m+j, i*m+j+1)
28+
}
29+
30+
}
31+
}
32+
}
33+
for i := 0; i < n; i++ {
34+
for j := 0; j < m; j++ {
35+
if uf.find(i*m+j) != uf.find(n*m) {
36+
board[i][j] = 'X'
37+
}
38+
}
39+
}
40+
}
41+
42+
// 解法二 DFS
43+
func solve1(board [][]byte) {
44+
for i := range board {
45+
for j := range board[i] {
46+
if i == 0 || i == len(board)-1 || j == 0 || j == len(board[i])-1 {
47+
if board[i][j] == 'O' {
48+
dfs130(i, j, board)
49+
}
50+
}
51+
}
52+
}
53+
54+
for i := range board {
55+
for j := range board[i] {
56+
if board[i][j] == '*' {
57+
board[i][j] = 'O'
58+
} else if board[i][j] == 'O' {
59+
board[i][j] = 'X'
60+
}
61+
}
62+
}
63+
}
64+
65+
func dfs130(i, j int, board [][]byte) {
66+
if i < 0 || i > len(board)-1 || j < 0 || j > len(board[i])-1 {
67+
return
68+
}
69+
if board[i][j] == 'O' {
70+
board[i][j] = '*'
71+
for k := 0; k < 4; k++ {
72+
dfs130(i+dir[k][0], j+dir[k][1], board)
73+
}
74+
}
75+
}

‎Algorithms/0130. Surrounded Regions/130. Surrounded Regions_test.go

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question130 struct {
9+
para130
10+
ans130
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para130 struct {
16+
one [][]byte
17+
}
18+
19+
// ans 是答案
20+
// one 代表第一个答案
21+
type ans130 struct {
22+
one [][]byte
23+
}
24+
25+
func Test_Problem130(t *testing.T) {
26+
27+
qs := []question130{
28+
29+
question130{
30+
para130{[][]byte{}},
31+
ans130{[][]byte{}},
32+
},
33+
34+
question130{
35+
para130{[][]byte{[]byte{'X', 'X', 'X', 'X'}, []byte{'X', 'O', 'O', 'X'}, []byte{'X', 'X', 'O', 'X'}, []byte{'X', 'O', 'X', 'X'}}},
36+
ans130{[][]byte{[]byte{'X', 'X', 'X', 'X'}, []byte{'X', 'X', 'X', 'X'}, []byte{'X', 'X', 'X', 'X'}, []byte{'X', 'O', 'X', 'X'}}},
37+
},
38+
}
39+
40+
fmt.Printf("------------------------Leetcode Problem 130------------------------\n")
41+
42+
for _, q := range qs {
43+
_, p := q.ans130, q.para130
44+
fmt.Printf("【input】:%v ", p)
45+
solve1(p.one)
46+
fmt.Printf("【output】:%v \n", p)
47+
}
48+
fmt.Printf("\n\n\n")
49+
}

‎Algorithms/0130. Surrounded Regions/README.md

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
# [130. Surrounded Regions](https://leetcode.com/problems/surrounded-regions/)
2+
3+
4+
5+
## 题目:
6+
7+
Given a 2D board containing `'X'` and `'O'` (**the letter O**), capture all regions surrounded by `'X'`.
8+
9+
A region is captured by flipping all `'O'`s into `'X'`s in that surrounded region.
10+
11+
**Example:**
12+
13+
X X X X
14+
X O O X
15+
X X O X
16+
X O X X
17+
18+
After running your function, the board should be:
19+
20+
X X X X
21+
X X X X
22+
X X X X
23+
X O X X
24+
25+
**Explanation:**
26+
27+
Surrounded regions shouldn’t be on the border, which means that any `'O'` on the border of the board are not flipped to `'X'`. Any `'O'` that is not on the border and it is not connected to an `'O'` on the border will be flipped to `'X'`. Two cells are connected if they are adjacent cells connected horizontally or vertically.
28+
29+
## 题目大意
30+
31+
给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
32+
33+
34+
## 解题思路
35+
36+
37+
- 给出一张二维地图，要求把地图上非边缘上的 'O' 都用 'X' 覆盖掉。
38+
- 这一题有多种解法。第一种解法是并查集。先将边缘上的 'O' 全部都和一个特殊的点进行 `union()` 。然后再把地图中间的 'O' 都进行 `union()`，最后把和特殊点不是同一个集合的点都标记成 'X'。第二种解法是 DFS 或者 BFS，可以先将边缘上的 'O' 先标记成另外一个字符，然后在递归遍历过程中，把剩下的 'O' 都标记成 'X'。
39+

‎Algorithms/0547. Friend Circles/547. Friend Circles.go

Lines changed: 43 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -2,60 +2,71 @@ package leetcode
22

33
// 解法一 并查集
44

5-
// UninonSet defind
6-
type UninonSet struct {
7-
roots []int
5+
// UnionFind defind
6+
type UnionFind struct {
7+
parent, rank []int
8+
count int
89
}
910

10-
func (us UninonSet) init() {
11-
for i := range us.roots {
12-
us.roots[i] = i
11+
func (uf *UnionFind) init(n int) {
12+
uf.count = n
13+
uf.parent = make([]int, n)
14+
uf.rank = make([]int, n)
15+
for i := range uf.parent {
16+
uf.parent[i] = i
1317
}
1418
}
1519

16-
func (us UninonSet) findRoot(i int) int {
17-
root := i
18-
for root != us.roots[root] {
19-
root = us.roots[root]
20+
func (uf *UnionFind) find(p int) int {
21+
root := p
22+
for root != uf.parent[root] {
23+
root = uf.parent[root]
2024
}
21-
for i != us.roots[i] {
22-
tmp := us.roots[i]
23-
us.roots[i] = root
24-
i = tmp
25+
// compress path
26+
for p != uf.parent[p] {
27+
tmp := uf.parent[p]
28+
uf.parent[p] = root
29+
p = tmp
2530
}
2631
return root
2732
}
2833

29-
func (us UninonSet) union(p, q int) {
30-
qroot := us.findRoot(q)
31-
proot := us.findRoot(p)
32-
us.roots[proot] = qroot
34+
func (uf *UnionFind) union(p, q int) {
35+
proot := uf.find(p)
36+
qroot := uf.find(q)
37+
if proot == qroot {
38+
return
39+
}
40+
if uf.rank[qroot] > uf.rank[proot] {
41+
uf.parent[proot] = qroot
42+
} else {
43+
uf.parent[qroot] = proot
44+
if uf.rank[proot] == uf.rank[qroot] {
45+
uf.rank[proot]++
46+
}
47+
}
48+
uf.count--
49+
}
50+
51+
func (uf *UnionFind) totalCount() int {
52+
return uf.count
3353
}
3454

3555
func findCircleNum(M [][]int) int {
36-
n, count := len(M), 0
56+
n := len(M)
3757
if n == 0 {
3858
return 0
3959
}
40-
us := UninonSet{}
41-
us.roots = make([]int, n+1)
42-
us.init()
60+
uf := UnionFind{}
61+
uf.init(n)
4362
for i := 0; i < n; i++ {
4463
for j := 0; j <= i; j++ {
4564
if M[i][j] == 1 {
46-
x, y := us.findRoot(i), us.findRoot(j)
47-
if x != y {
48-
us.union(x, y)
49-
}
65+
uf.union(i, j)
5066
}
5167
}
5268
}
53-
for i := 0; i < n; i++ {
54-
if us.roots[i] == i {
55-
count++
56-
}
57-
}
58-
return count
69+
return uf.count
5970
}
6071

6172
// 解法二 FloodFill DFS 暴力解法

0 commit comments

Comments
 (0)
0