题目

在由 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)

leetcode困难题(leetcode959go由斜杠划分区域)(1)

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.岛屿数量

,