f*********m
发帖数: 726 | 1 考古发现一大牛贴了这个题目：
找最大的1的cluster size，比如：
00111
01001
00000
11101
这里最大的1的cluster size是5，就是前两行那些1的个数，
两个cell可以组成cluster if
1。两个cell都是1
2。两个cell相邻，对角也算
大牛说用bfs，用数组模拟栈，O(n) n是矩阵大小。我不理解。
是不是说先pre-processing原矩阵，对每一个元素标出和其连接的元素，这样每个元素
都在一个graph中，然后以每一个元素为出发点，用bfs或者dfs遍历其所在的graph同时
记录此graph包含元素个数？
请指教。 |
d*********g
发帖数: 154 | 2
我感觉应该是你说的这样。遍历过的元素就标记为visited（或者直接把遍历过的1改成
0或者2，如果允许改动原矩阵的话）。这样每个元素最多访问2遍。不知道我说的对不
对。
【在 f*********m 的大作中提到】
: 考古发现一大牛贴了这个题目：
: 找最大的1的cluster size，比如：
: 00111
: 01001
: 00000
: 11101
: 这里最大的1的cluster size是5，就是前两行那些1的个数，
: 两个cell可以组成cluster if
: 1。两个cell都是1
: 2。两个cell相邻，对角也算
|
t****a
发帖数: 1212 | 3 只要构建好表示各个1-1边的图的数据结构（链接表？），这题目就很容易搞定了
1. 构建图的数据结构，时间上是O(n * m)
2. 寻找连通分量，计算量 O(k) k=1的个数 |
W*********y
发帖数: 481 | 4 bfs不是要用queue么?dfs才是stack把
【在 f*********m 的大作中提到】
: 考古发现一大牛贴了这个题目：
: 找最大的1的cluster size，比如：
: 00111
: 01001
: 00000
: 11101
: 这里最大的1的cluster size是5，就是前两行那些1的个数，
: 两个cell可以组成cluster if
: 1。两个cell都是1
: 2。两个cell相邻，对角也算
|
c********t
发帖数: 5706 | 5 DFS, 不用preprocess, 但要一个二维visited boolean数组
遍历原二维数组，visited跳过，没有visited, 并等于1的进行DFS遍历，找8个方向的1
，遍历过的visited=true，计算cluster size, 并保存最大的size作为结果返回。O（n)
【在 f*********m 的大作中提到】
: 考古发现一大牛贴了这个题目：
: 找最大的1的cluster size，比如：
: 00111
: 01001
: 00000
: 11101
: 这里最大的1的cluster size是5，就是前两行那些1的个数，
: 两个cell可以组成cluster if
: 1。两个cell都是1
: 2。两个cell相邻，对角也算
|
k****r
发帖数: 807 | 6 同意；但是觉得DFS, BFS都可以吧？访问过的标记即可。
话说冷骑士还没收官？
的1
（n)
【在 c********t 的大作中提到】
: DFS, 不用preprocess, 但要一个二维visited boolean数组
: 遍历原二维数组，visited跳过，没有visited, 并等于1的进行DFS遍历，找8个方向的1
: ，遍历过的visited=true，计算cluster size, 并保存最大的size作为结果返回。O（n)
|
c********t
发帖数: 5706 | 7 嗯，对，DFS, BFS都可以，如果写backtracking+recusion,DFS容易些。
没收官。收了一个电锯，一个面具。
【在 k****r 的大作中提到】
: 同意；但是觉得DFS, BFS都可以吧？访问过的标记即可。
: 话说冷骑士还没收官？
:
: 的1
: （n)
|
k****r
发帖数: 807 | 8 觉得你和CAIWU是一个水平的，应该offer不远了才对，一起加油吧
【在 c********t 的大作中提到】
: 嗯，对，DFS, BFS都可以，如果写backtracking+recusion,DFS容易些。
: 没收官。收了一个电锯，一个面具。
|
c********t
发帖数: 5706 | 9 ads组就是把我拒了，把他招了，唉！
多谢，一起加油！
【在 k****r 的大作中提到】
: 觉得你和CAIWU是一个水平的，应该offer不远了才对，一起加油吧
|
C***U
发帖数: 2406 | 10 您太看得起我了！哈哈
【在 c********t 的大作中提到】
: ads组就是把我拒了，把他招了，唉！
: 多谢，一起加油！
|
