在由 1 x 1 方格組成的 N x N 網格 grid 中，每個 1 x 1 方塊由 /、\ 或空格構成。這些字符會将方塊劃分為一些共邊的區域。

（請注意，反斜杠字符是轉義的，因此 \ 用 "\\" 表示。）。

返回區域的數目。

示例 1：輸入：

[

" /",

"/ "

]

輸出：2

解釋：2x2 網格如下：

示例 2：輸入：

[

" /",

" "

]

輸出：1

解釋：2x2 網格如下：

示例 3：輸入：

[

"\\/",

"/\\"

]

輸出：4

解釋：（回想一下，因為 \ 字符是轉義的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）

2x2 網格如下：

示例 4：輸入：

[

"/\\",

"\\/"

]

輸出：5

解釋：（回想一下，因為 \ 字符是轉義的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）

2x2 網格如下：

示例 5：輸入：

[

"//",

"/ "

]

輸出：3

解釋：2x2 網格如下：

提示：1 <= grid.length == grid[0].length <= 30

grid[i][j] 是 '/'、'\'、或 ' '。

1、并查集；時間複雜度O(n^2log(n))，空間複雜度O(n^2)

func regionsBySlashes(grid []string) int { n := len(grid) fa = Init(n * n * 4) for i := 0; i < n; i { for j := 0; j < n; j { index := 4 * (i*n j) // 擴大4倍，每個格子拆分為4個：0、1、2、3（順時針） if grid[i][j] == '/' { union(index, index 3) // 合并0、3 union(index 1, index 2) // 合并1、2 } else if grid[i][j] == '\\' { union(index, index 1) // 合并0、1 union(index 2, index 3) // 合并2、3 } else { union(index, index 1) // 合并0、1、2、3 union(index 1, index 2) union(index 2, index 3) } if j < n-1 { union(index 1, index 7) // 向右合并 } if i < n-1 { union(index 2, index 4*n) // 向下合并 } } } return getCount() } var fa []int var count int // 初始化 func Init(n int) []int { arr := make([]int, n) for i := 0; i < n; i { arr[i] = i } count = n return arr } // 查詢 func find(x int) int { if fa[x] == x { return x } // 路徑壓縮 fa[x] = find(fa[x]) return fa[x] } // 合并 func union(i, j int) { x, y := find(i), find(j) if x != y { fa[x] = y count-- } } func query(i, j int) bool { return find(i) == find(j) } func getCount() int { return count }

2、深度優先搜索；時間複雜度O(n^2)，空間複雜度O(n^2)

func regionsBySlashes(grid []string) int { n := len(grid) arr := make([][]int, 3*n) for i := 0; i < 3*n; i { arr[i] = make([]int, 3*n) } for i := 0; i < n; i { // 放大處理 for j := 0; j < n; j { if grid[i][j] == '/' { // 9宮格 arr[i*3 2][j*3] = 1 arr[i*3 1][j*3 1] = 1 arr[i*3][j*3 2] = 1 } else if grid[i][j] == '\\' { arr[i*3 2][j*3 2] = 1 arr[i*3 1][j*3 1] = 1 arr[i*3][j*3] = 1 } } } res := 0 for i := 0; i < 3*n; i { for j := 0; j < 3*n; j { if arr[i][j] == 0 { dfs(arr, i, j) res } } } return res } func dfs(arr [][]int, i, j int) { if 0 <= i && i < len(arr) && 0 <= j && j < len(arr[0]) && arr[i][j] == 0 { arr[i][j] = 1 dfs(arr, i 1, j) dfs(arr, i-1, j) dfs(arr, i, j-1) dfs(arr, i, j 1) } }

Medium題目，簡單一些思路就是進行放大處理，把單個字符轉換為9宮格，然後題目就變成 leetcode 200.島嶼數量

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!