l******2
发帖数: 41 | 1 2D matrix with 0s and 1s. Try to find out how many countries in this matrix?
For example:
[[1,1,1,0]
[1,1,0,0]
[0,0,0,1]]
return 3, because one for 1s, one for 0s, and one for the last one.
another example:
[[1,1,1,1]
[0,0,0,0]
[1,0,0,1]]
return 4
LZ想到的是用DFS 和 boolean[][] visited, 大家还有什么好方法吗？
另外，看到一道面经提示用 unit and find，不知道是不是可以帮忙看看怎么写？不是
很熟
count islands in a m*n grid （一个联通的值为1的区域被视为一个island）
例：
0011010
0010010
1000110
0000001
4 islands found in above grid | p*****2
发帖数: 21240 | 2 可以染色 o（1） space
matrix?
【在 l******2 的大作中提到】
: 2D matrix with 0s and 1s. Try to find out how many countries in this matrix?
: For example:
: [[1,1,1,0]
: [1,1,0,0]
: [0,0,0,1]]
: return 3, because one for 1s, one for 0s, and one for the last one.
: another example:
: [[1,1,1,1]
: [0,0,0,0]
: [1,0,0,1]]
| c*******7
发帖数: 438 | 3 扫一遍，每访问一个元素，check左和上有没有相同的值，没有的
话count++。 | m*****k
发帖数: 731 | 4 similar to leecode find surrounded region a,
i = 0,
while( find first number>=0){
{
i--;
mark it as i and mark all area it can reach(same value as its original) ,
using stack for this.
}
return math.abs(i); | c*****m
发帖数: 271 | 5 应该check左，左上，上，右上
【在 c*******7 的大作中提到】
: 扫一遍，每访问一个元素，check左和上有没有相同的值，没有的
: 话count++。
| p*****2
发帖数: 21240 | 6
可以斜着走吗？
【在 c*****m 的大作中提到】
: 应该check左，左上，上，右上
| c*******7
发帖数: 438 | | s******d
发帖数: 9806 | 8 how about this case:
1110
0000
When you search the element (2,1), you have no idea it is in the same group
of element (1,4).
【在 c*****m 的大作中提到】
: 应该check左，左上，上，右上
| y****e
发帖数: 25 | 9 用Union－Find数据结构http://algs4.cs.princeton.edu/15uf/ and http://algs4.cs.princeton.edu/43mst/UF.java.html)可以解决这个问题。
将相同数字的邻居用Union操作连接。最后调用一下count()函数就可以了。
时间复杂度非常接近O(N^2)。空间复杂度为O(N^2)。
发包子的话，可以提供代码 :)
matrix?
【在 l******2 的大作中提到】
: 2D matrix with 0s and 1s. Try to find out how many countries in this matrix?
: For example:
: [[1,1,1,0]
: [1,1,0,0]
: [0,0,0,1]]
: return 3, because one for 1s, one for 0s, and one for the last one.
: another example:
: [[1,1,1,1]
: [0,0,0,0]
: [1,0,0,1]]
| c*******7
发帖数: 438 | 10 好吧，我图样图森破了
group
【在 s******d 的大作中提到】
: how about this case:
: 1110
: 0000
: When you search the element (2,1), you have no idea it is in the same group
: of element (1,4).
| | | s****a
发帖数: 794 | 11 染色最差也就是O(n^2)吧 扫一遍不也是这样么 | c****8
发帖数: 76 | 12 我觉得用ZigZag的遍历方式，然后每次Check左、上就行。觉得应该可以。
【在 c*******7 的大作中提到】
: 好吧，我图样图森破了
:
: group
| k******e
发帖数: 145 | 13 bfs加标记加counter？
matrix?
【在 l******2 的大作中提到】
: 2D matrix with 0s and 1s. Try to find out how many countries in this matrix?
: For example:
: [[1,1,1,0]
: [1,1,0,0]
: [0,0,0,1]]
: return 3, because one for 1s, one for 0s, and one for the last one.
: another example:
: [[1,1,1,1]
: [0,0,0,0]
: [1,0,0,1]]
| c***r
发帖数: 280 | 14 发包子了，给代码吧 :-)))
还是不知道怎么count
【在 y****e 的大作中提到】
: 用Union－Find数据结构http://algs4.cs.princeton.edu/15uf/ and http://algs4.cs.princeton.edu/43mst/UF.java.html)可以解决这个问题。
: 将相同数字的邻居用Union操作连接。最后调用一下count()函数就可以了。
: 时间复杂度非常接近O(N^2)。空间复杂度为O(N^2)。
: 发包子的话，可以提供代码 :)
:
: matrix?
| c***r
发帖数: 280 | 15 发包子了，给代码吧：-）））
还是不知道该怎么count
【在 y****e 的大作中提到】
: 用Union－Find数据结构http://algs4.cs.princeton.edu/15uf/ and http://algs4.cs.princeton.edu/43mst/UF.java.html)可以解决这个问题。
: 将相同数字的邻居用Union操作连接。最后调用一下count()函数就可以了。
: 时间复杂度非常接近O(N^2)。空间复杂度为O(N^2)。
: 发包子的话，可以提供代码 :)
:
: matrix?
| u*****l
发帖数: 444 | 16 这个典型的percolation的题目。
Sedgewick的Algorithm课的第一周作业就是讲这个的。
用一个数组代表构造树结构。 | b*********e
发帖数: 26 | 17 worst case不会只有n^2
e.g.
10101
10101
10101
10101
00000
【在 c****8 的大作中提到】
: 我觉得用ZigZag的遍历方式，然后每次Check左、上就行。觉得应该可以。
| h**********c
发帖数: 4120 | 18 vantican is another case
0000
0111
0101
0111 |
|
