题目描述(中等难度)

130*. Surrounded Regions - 图1

有一点点像围棋,把被 X 围起来的 O 变成 X,边界的 O 一定不会被围起来。如果 O 和边界的 O 连通起来,那么这些 O 就都算作不被围起来,比如下边的例子。

  1. X X X X X
  2. O O O X X
  3. X X X O X
  4. X O X X X

上边的例子就只需要变化 1O

  1. X X X X X
  2. O O O X X
  3. X X X X X
  4. X O X X X

解法一

把相邻的O 看作是连通的图,然后从每一个 O 开始做 DFS

如果遍历完成后没有到达边界的 O ,我们就把当前 O 改成 X

如果遍历过程中到达了边界的 O ,直接结束 DFS,当前的 O 就不用操作。

然后继续考虑下一个 O,继续做一次 DFS

  1. public void solve(char[][] board) {
  2. int rows = board.length;
  3. if (rows == 0) {
  4. return;
  5. }
  6. int cols = board[0].length;
  7. //考虑除去边界以外的所有 O
  8. for (int i = 1; i < rows - 1; i++) {
  9. for (int j = 1; j < cols - 1; j++) {
  10. if (board[i][j] == 'O') {
  11. //visited 用于记录 DFS 过程中已经访问过的节点
  12. HashSet<String> visited = new HashSet<>();
  13. //如果没有到达边界,就把当前 O 置为 X
  14. if (!solveHelper(i, j, board, visited)) {
  15. board[i][j] = 'X';
  16. }
  17. }
  18. }
  19. }
  20. }
  21. private boolean solveHelper(int row, int col, char[][] board, HashSet<String> visited) {
  22. //是否访问过
  23. if (visited.contains(row + "@" + col)) {
  24. return false;
  25. }
  26. visited.add(row + "@" + col);
  27. //到达了 X 直接返回 false
  28. if (board[row][col] == 'X') {
  29. return false;
  30. }
  31. if (row == 0 || row == board.length - 1 || col == 0 || col == board[0].length - 1) {
  32. return true;
  33. }
  34. //分别尝试四个方向
  35. if (solveHelper(row - 1, col, board, visited)
  36. || solveHelper(row, col - 1, board, visited)
  37. || solveHelper(row + 1, col, board, visited)
  38. || solveHelper(row, col + 1, board, visited)) {
  39. return true;
  40. } else {
  41. return false;
  42. }
  43. }

遗憾的是,到最后两个 test 的时候超时了。

130*. Surrounded Regions - 图2

优化的的话,我尝试了在每次 DFS 过程中,返回 true 之前,把当前的 rowcol 记录下来,然后第二次遇到这些点的时候,就直接跳过 。

  1. public void solve(char[][] board) {
  2. int rows = board.length;
  3. if (rows == 0) {
  4. return;
  5. }
  6. //记录可以连通到边界的 O
  7. HashSet<String> memoization = new HashSet<>();
  8. int cols = board[0].length;
  9. for (int i = 1; i < rows - 1; i++) {
  10. for (int j = 1; j < cols - 1; j++) {
  11. if (board[i][j] == 'O') {
  12. //如果当前位置的 O 被记录过了,直接跳过
  13. if (memoization.contains(i + "@" + j)) {
  14. continue;
  15. }
  16. HashSet<String> visited = new HashSet<>();
  17. if (!solveHelper(i, j, board, visited, memoization)) {
  18. board[i][j] = 'X';
  19. }
  20. }
  21. }
  22. }
  23. }
  24. private boolean solveHelper(int row, int col, char[][] board, HashSet<String> visited,
  25. HashSet<String> memoization) {
  26. if (visited.contains(row + "@" + col)) {
  27. return false;
  28. }
  29. visited.add(row + "@" + col);
  30. if (board[row][col] == 'X') {
  31. return false;
  32. }
  33. //当前位置可以连通到边界,返回 true
  34. if (memoization.contains(row + "@" +col)) {
  35. return true;
  36. }
  37. if (row == 0 || row == board.length - 1 || col == 0 || col == board[0].length - 1) {
  38. //当前位置可以连通道边界,记录下来
  39. memoization.add(row + "@" + col);
  40. return true;
  41. }
  42. if (solveHelper(row - 1, col, board, visited, memoization)
  43. || solveHelper(row, col - 1, board, visited, memoization)
  44. || solveHelper(row + 1, col, board, visited, memoization)
  45. || solveHelper(row, col + 1, board, visited, memoization)) {
  46. //当前位置可以连通道边界,记录下来
  47. memoization.add(row + "@" + col);
  48. return true;
  49. } else {
  50. return false;
  51. }
  52. }

但没什么效果,依旧还是超时。

之前还考虑过能不能在遍历过程中,返回 false 之前,直接把 O 改成 X。最后发现是不可以的,比如下边的例子。

130*. Surrounded Regions - 图3

如果我们从橙色的 ODFS,然后沿着箭头方向,到达最后一个 O 的时候,它的左边上边右边都是 X ,根据代码它就返回 false,此外它下边是访问过的节点也会返回 false,所以四个方向都返回 false,如果把它改成 X明显是不对的。

解法二

解法一是从当前节点做 DFS ,然后看它是否能到达边界的 O。那么我们能不能把思路逆转过来呢?

从边界的 ODFS,然后把遇到的 O 都标记一下,这些 O 就是可以连通到边界的。然后把边界的所有的 O 都做一次 DFS ,把 DFS 过程的中的 O 做一下标记。最后我们只需要遍历节点,把没有标记过的 O 改成 X 就可以了。

标记的话,我们可以用一个 visited 二维数组,把访问过的置为 true

  1. public void solve(char[][] board) {
  2. int rows = board.length;
  3. if (rows == 0) {
  4. return;
  5. }
  6. int cols = board[0].length;
  7. boolean[][] visited = new boolean[rows][cols];
  8. for (int i = 0; i < cols; i++) {
  9. //最上边一行的所有 O 做 DFS
  10. if (board[0][i] == 'O') {
  11. dfs(0, i, board, visited);
  12. }
  13. //最下边一行的所有 O 做 DFS
  14. if (board[board.length - 1][i] == 'O') {
  15. dfs(board.length - 1, i, board, visited);
  16. }
  17. }
  18. for (int i = 1; i < rows - 1; i++) {
  19. //最左边一列的所有 O 做 DFS
  20. if (board[i][0] == 'O') {
  21. dfs(i, 0, board, visited);
  22. }
  23. //最右边一列的所有 O 做 DFS
  24. if (board[i][board[0].length - 1] == 'O') {
  25. dfs(i, board[0].length - 1, board, visited);
  26. }
  27. }
  28. //把所有没有标记过的 O 改为 X
  29. for (int i = 0; i < rows; i++) {
  30. for (int j = 0; j < cols; j++) {
  31. //省略了对 X 的判断,把 X 变成 X 不影响结果
  32. if (!visited[i][j]) {
  33. board[i][j] = 'X';
  34. }
  35. }
  36. }
  37. }
  38. private void dfs(int i, int j, char[][] board, boolean[][] visited) {
  39. if (i < 0 || j < 0 || i == board.length || j == board[0].length) {
  40. return;
  41. }
  42. if (visited[i][j]) {
  43. return;
  44. }
  45. if (board[i][j] == 'O') {
  46. visited[i][j] = true;
  47. dfs(i + 1, j, board, visited);
  48. dfs(i, j + 1, board, visited);
  49. dfs(i, j - 1, board, visited);
  50. dfs(i - 1, j, board, visited);
  51. }
  52. }

然后这个解法 AC 了,但空间复杂度可以优化一下,这个思想很多题用过了,比如 79 题

这里的 visited 的二维数组我们可以不需要。我们可以先把连通的 O 改成 *,或者其他的字符。最后遍历整个 board,遇到 * 就把它还原到 O 。遇到 O,因为它没有被修改成*,也就意味着它没有连到边界,就把它改成 X

  1. public void solve(char[][] board) {
  2. int rows = board.length;
  3. if (rows == 0) {
  4. return;
  5. }
  6. int cols = board[0].length;
  7. for (int i = 0; i < cols; i++) {
  8. //最上边一行的所有 O 做 DFS
  9. if (board[0][i] == 'O') {
  10. dfs(0, i, board);
  11. }
  12. //最下边一行的所有 O 做 DFS
  13. if (board[board.length - 1][i] == 'O') {
  14. dfs(board.length - 1, i, board);
  15. }
  16. }
  17. for (int i = 1; i < rows - 1; i++) {
  18. //最左边一列的所有 O 做 DFS
  19. if (board[i][0] == 'O') {
  20. dfs(i, 0, board);
  21. }
  22. //最右边一列的所有 O 做 DFS
  23. if (board[i][board[0].length - 1] == 'O') {
  24. dfs(i, board[0].length - 1, board);
  25. }
  26. }
  27. //把所有没有标记过的 O 改为 X,标记过的还原
  28. for (int i = 0; i < rows; i++) {
  29. for (int j = 0; j < cols; j++) {
  30. if (board[i][j] == '*') {
  31. board[i][j] = 'O';
  32. }else if(board[i][j] == 'O'){
  33. board[i][j] = 'X';
  34. }
  35. }
  36. }
  37. }
  38. private void dfs(int i, int j, char[][] board) {
  39. if (i < 0 || j < 0 || i == board.length || j == board[0].length) {
  40. return;
  41. }
  42. if (board[i][j] == '*') {
  43. return;
  44. }
  45. if (board[i][j] == 'O') {
  46. board[i][j] = '*';
  47. dfs(i + 1, j, board);
  48. dfs(i, j + 1, board);
  49. dfs(i, j - 1, board);
  50. dfs(i - 1, j, board);
  51. }
  52. }

但是在逛 Disscuss 的时候发现有人提出来说,DFS 的解法可能导致栈溢出。

这个 解法 下的第一个评论,我把原文贴过来。

This is a DFS solution, but it may causes a stack overflow issue.

When you use DFS, it is tricky to use:

  1. if(i>1)
  2. check(vec,i-1,j,row,col);
  3. if(j>1)
  4. check(vec,i,j-1,row,col);

because it is more common to write like this:

  1. if(i>=1)
  2. check(vec,i-1,j,row,col);
  3. if(j>=1)
  4. check(vec,i,j-1,row,col);

Then I’ll explain it.

There is a test case like this:

  1. OOOOOOOOOO
  2. XXXXXXXXXO
  3. OOOOOOOOOO
  4. OXXXXXXXXX
  5. OOOOOOOOOO
  6. XXXXXXXXXO
  7. OOOOOOOOOO
  8. OXXXXXXXXX
  9. OOOOOOOOOO
  10. XXXXXXXXXO

To make it clear, I draw a 10x10 board, but it is actually a 250x250 board like this one.

When dfs function visit board[0][0], it ought to visit every grid marked ‘O’, thus lead to stack overflow(runtime error).

After you change “if(j>=1)” to “if(j>1)”, the DFS function won’t check board[i][0] (0<=i<=row-1), and then not all the grids marked ‘O’ will be visited when you dfs(board[0][0]). Your code won’t cause stack overflow in this test case, but if we change the test case a little, it won’t work well.

Consider a test case like this:

  1. OOOOOOOOOOOX
  2. XXXXXXXXXXOX
  3. XOOOOOOOOOOX
  4. XOXXXXXXXXXX
  5. XOOOOOOOOOOX
  6. XXXXXXXXXXOX
  7. XOOOOOOOOOOX
  8. XOXXXXXXXXXX
  9. XOOOOOOOOOOX
  10. XXXXXXXXXXOX

I draw a 10x12 board, but it may be as large as the 250x250 board.

I believe that your code will get “runtime error” in this test case when tested in Leetcode system.

他的意思就是说,比如下边的例子类型,假如是 250 × 250 大小的话,因为我们做的是 DFS,一直压栈的话就会造成溢出。

  1. OOOOOOOOOOOX
  2. XXXXXXXXXXOX
  3. XOOOOOOOOOOX
  4. XOXXXXXXXXXX
  5. XOOOOOOOOOOX
  6. XXXXXXXXXXOX
  7. XOOOOOOOOOOX
  8. XOXXXXXXXXXX
  9. XOOOOOOOOOOX
  10. XXXXXXXXXXOX

但是我的代码已经通过了呀,一个可能的原因就是 leetcode 升级了,因为这是 2015 年的评论,现在是 2019 年,压栈的大小足够大了,只要有递归出口,就不用担心压栈放不下了。我就好奇的想测一下 leetcode 的压栈到底有多大。写了一个简单的递归代码。

  1. public void solve(char[][] board) {
  2. dfs(2677574);
  3. }
  4. private int dfs(int count) {
  5. if (count == 0) {
  6. return 1;
  7. }
  8. return dfs(count - 1);
  9. }

然后一开始传一个较大的数字,然后利用二分法,开始不停试探那个溢出的临界点是多少。经过多次尝试,发现 2677574 的话就会造成溢出。2677573 就不会造成溢出。本以为这样就结束了,然后准备截图总结的时候发现。取 2677574 竟然不溢出了,2677573 反而溢出了。

130*. Surrounded Regions - 图4

130*. Surrounded Regions - 图5

同一个数字,一会儿溢出一会儿不溢出,那就没办法得出结论了。那可能栈的大小和它服务器当前的承载的能力有关了,不过一般情况的栈的大小肯定足够解决题目了。

那么退一步讲,如果它的栈的限定很小,这里的 DFS 行不通,我们有什么解决方案吗?

这里我想到两种,一种就是用栈去模拟递归,这里的栈当然就是对象了,存在堆里,就不用担心函数栈溢出了。

另一种,利用一个队列,去实现 BFS,首先把四个边界的 O 加到队列中,然后按照正常的 BFS 和之前一样访问连通的 O 并且进行标记。最后再把没有标记的 O 改成 X 就可以了。

解法三

这里再介绍另外一种思想,参考 这里,就是并查集,其实本质上和上边的解法是一样的,只是抽象出了一种数据结构,在很多地方都有应用。

看下维基百科对 并查集 的定义。

计算机科学中,并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。有一个联合-查找算法union-find algorithm)定义了两个用于此数据结构的操作:

  • Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
  • Union:将两个子集合并成同一个集合。

由于支持这两种操作,一个不相交集也常被称为联合-查找数据结构(union-find data structure)或合并-查找集合(merge-find set)。其他的重要方法,MakeSet,用于创建单元素集合。有了这些方法,许多经典的划分问题可以被解决。

为了更加精确的定义这些方法,需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素,称为代表,以表示整个集合。接着,Find(x) 返回 x 所属集合的代表,而 Union 使用两个集合的代表作为参数。

网上很多讲并查集的文章了,这里推荐 一篇

知道了并查集,下边就很好解决了,因为你会发现,我们做的就是分类的问题,O 其实最终就是两大类,一种能连通到边界,一种不能连通到边界。

首先我们把每个节点各作为一类,用它的行数和列数生成一个 id 标识该类。

  1. int node(int i, int j) {
  2. return i * cols + j;
  3. }

然后遍历每个 O节点,和它上下左右的节点进行合并即可。

如果当前节点是边界的 O,就把它和 dummy 节点(一个在所有节点外的节点)合并。最后就会把所有连通到边界的 o 节点和 dummy 节点合为了一类。

最后我们只需要判断,每一个 o 节点是否和 dummy 节点是不是一类即可。

  1. public class Solution {
  2. int rows, cols;
  3. public void solve(char[][] board) {
  4. if(board == null || board.length == 0) return;
  5. rows = board.length;
  6. cols = board[0].length;
  7. //多申请一个空间
  8. UnionFind uf = new UnionFind(rows * cols + 1);
  9. //所有边界的 O 节点都和 dummy 节点合并
  10. int dummyNode = rows * cols;
  11. for(int i = 0; i < rows; i++) {
  12. for(int j = 0; j < cols; j++) {
  13. if(board[i][j] == 'O') {
  14. //当前节点在边界就和 dummy 合并
  15. if(i == 0 || i == rows-1 || j == 0 || j == cols-1) {
  16. uf.union( dummyNode,node(i,j));
  17. }
  18. else {
  19. //将上下左右的 O 节点和当前节点合并
  20. if(board[i-1][j] == 'O') uf.union(node(i,j), node(i-1,j));
  21. if(board[i+1][j] == 'O') uf.union(node(i,j), node(i+1,j));
  22. if(board[i][j-1] == 'O') uf.union(node(i,j), node(i, j-1));
  23. if( board[i][j+1] == 'O') uf.union(node(i,j), node(i, j+1));
  24. }
  25. }
  26. }
  27. }
  28. for(int i = 0; i < rows; i++) {
  29. for(int j = 0; j < cols; j++) {
  30. //判断是否和 dummy 节点是一类
  31. if(uf.isConnected(node(i,j), dummyNode)) {
  32. board[i][j] = 'O';
  33. }
  34. else {
  35. board[i][j] = 'X';
  36. }
  37. }
  38. }
  39. }
  40. int node(int i, int j) {
  41. return i * cols + j;
  42. }
  43. }
  44. class UnionFind {
  45. int [] parents;
  46. public UnionFind(int totalNodes) {
  47. parents = new int[totalNodes];
  48. for(int i = 0; i < totalNodes; i++) {
  49. parents[i] = i;
  50. }
  51. }
  52. void union(int node1, int node2) {
  53. int root1 = find(node1);
  54. int root2 = find(node2);
  55. if(root1 != root2) {
  56. parents[root2] = root1;
  57. }
  58. }
  59. int find(int node) {
  60. while(parents[node] != node) {
  61. parents[node] = parents[parents[node]];
  62. node = parents[node];
  63. }
  64. return node;
  65. }
  66. boolean isConnected(int node1, int node2) {
  67. return find(node1) == find(node2);
  68. }
  69. }

解法一到解法二仅仅是思路的一个逆转,速度却带来了质的提升。所以有时候走到了死胡同,可以试试往回走。

刷这么多题第一次应用到了并查集,并查集说简单点,就是每一类选一个代表,然后类中的其他元素最终都可以找到这个代表。然后遍历其他元素,将它合并到某个类中。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话,可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法,强烈推荐一个我之前学过的课程,可以点击 这里 查看详情