请教number of islands一行一行读的情况

number of islands这道题有多种解法：dfs, bfs, union find.
这里有个问题，有些公司，比如Dropbox, 会问如果一行一行读怎么办？
Union find+一行一行读的解法想不明白，算islands的count算不对，求大神指点

我写了一份代码，可以通过LC 200：

1. import java.util.Arrays;
   
2. 
   
3. class Solution {
   
4.   private static final int INVALID = 0;
   
5. 
   
6.   public int numIslands(char[][] grid) {
   
7.     if (grid.length == 0) {
   
8.       return 0;
   
9.     }
   
10. 
    
11.     SimpleUnionFind uf = new SimpleUnionFind();
    
12.     int[] tags = new int[grid[0].length];
    
13.     int tagCounter = 0;
    
14. 
    
15.     // 逐行处理
    
16.     for (char[] row : grid) {
    
17.       for (int i = 0; i < row.length; ++i) {
    
18.         // Case 1. 当前格子为'0'，则标记为"无效"编号
    
19.         if (row[i] == '0') {
    
20.           tags[i] = INVALID;
    
21.           continue;
    
22.         }
    
23. 
    
24.         // Case 2. 当前格子为'1'，先获取左边和上方格子编号
    
25.         int leftTag = (i == 0 ? 0 : tags[i-1]);
    
26.         int upTag = tags[i];
    
27. 
    
28.         if (leftTag == INVALID) {
    
29.           if (upTag == INVALID) {
    
30.             // Case 2.1. 如果左边和上方格子都是无效编号，则分配一个新编号给当前格子
    
31.             uf.makeSet(tags[i] = ++tagCounter);
    
32.           } else {
    
33.             // Case 2.2. 继承上方编号
    
34.             // NO-OP
    
35.           }
    
36.         } else {
    
37.           if (upTag == INVALID) {
    
38.             // Case 2.3. 继承左边编号
    
39.             tags[i] = leftTag;
    
40.           } else {
    
41.             // Case 2.4. Union左边和上方的编号，并继承
    
42.             tags[i] = uf.union(tags[i-1], tags[i]);
    
43.           }
    
44.         }
    
45.       }
    
46.     }
    
47. 
    
48.     // 返回并查集中等价类数量
    
49.     return uf.numGroups(tagCounter);
    
50.   }
    
51. }
    
52. 
    
53. 
    
54. // 一个简易并查集，没有做路径折叠
    
55. class SimpleUnionFind {
    
56.   private int[] data = new int[256];
    
57. 
    
58.   private void resize() {
    
59.     data = Arrays.copyOf(data, data.length * 2);
    
60.   }
    
61. 
    
62.   public void makeSet(int value) {
    
63.     while (value >= data.length) {
    
64.       resize();
    
65.     }
    
66.     data[value] = value;
    
67.   }
    
68. 
    
69.   public int find(int value) {
    
70.     while (data[value] != value) {
    
71.       value = data[value];
    
72.     }
    
73.     return value;
    
74.   }
    
75. 
    
76.   public int union(int lhs, int rhs) {
    
77.     int root = find(lhs);
    
78.     data[find(rhs)] = root;
    
79.     return root;
    
80.   }
    
81. 
    
82.   public int numGroups(int limit) {
    
83.     int count = 0;
    
84.     for (int i = 1; i <= limit; ++i) {
    
85.       if (data[i] == i) {
    
86.         ++count;
    
87.       }
    
88.     }
    
89.     return count;
    
90.   }
    
91. }
    

复制代码

一行一行读什么意思，请贴代码

大概想了一下。。。欢迎讨论

一行一行从左向右读，那么一个格子的左边和上面一定已经被并入相应的island了，那么一个新的点会有三种情况：
1.左边上边都没有island，明显这个时候我们应该开一个新的island
2.相邻有一个island，那么我们把它并入这个island
3.有两个island，那么合并这两个island（如果需要），并且取更小的数字作为island编号（主要是为了下一个节点不要重蹈覆辙）

dingshilun 发表于 2018-1-22 08:09
大概想了一下。。。欢迎讨论

一行一行从左向右读，那么一个格子的左边和上面一定已经被并入相应的island ...

如果一行一行读, 是不是意味着无法读取当前位置"左上"的格子?

fisherhust 发表于 2018-1-22 08:22
如果一行一行读, 是不是意味着无法读取当前位置"左上"的格子?

如果可以向八个方向扩展那就简单了呀、不需要unionfind了

我觉得用union find，读完第一行后，后面每个格子只要union左边和上面的格子就行。这样就能保证所有临接的都合并过了。

fisherhust 发表于 2018-1-22 08:22
如果一行一行读, 是不是意味着无法读取当前位置"左上"的格子?

如果一行一行读，那么我们需要保存上一行的信息。这个信息可以是一个list of intervals of 1s. 或者干脆把整个上一行保存。

dingshilun 发表于 2018-1-22 08:09
大概想了一下。。。欢迎讨论

一行一行从左向右读，那么一个格子的左边和上面一定已经被并入相应的island ...

看起来是正解！不过估计这个算法实现起来会有些复杂。