w*****1
发帖数: 6807 | 1 看名字好像是来自东欧的哥儿们面的，本来HR说好的国人大哥不知道去哪儿了。。。
题目当时说的我就不是特别明白，大概是下面这个意思。
给一个任意大小的matrix A，大小mxn可以非常大，里面元素是0或者1。给个起始坐标[
i][j]。
实现如下过程，如果A[i][j]的邻居（九宫格包括自己）有元素是0，则都改为1。
然后基于已经填好1的区域，向外扩张（每步只能扩张到已填好(都是1)区域的邻居），
如果扩张遇到有0元素都改为1。停止条件是全都到了矩阵边界，或者填好区域的邻居全
是1。
形象一点说，有点像扫雷游戏。0改1可以想象成插小旗，只是雷你都事先都知道了。
当时面试也就剩半个小时了，好像不是leetcode里的题（也可能是，我刷的不是很仔细
），最近又回头搞论文去了，HR说这次面试问的是CS基础题。。。
做了半天想写个recursion算法，也写不出来。快没时间了，面试哥们说这题recursion
没法做，我只能又胡扯了些别的想法。。。又问了问复杂度就算完事了，应该是稳稳的
挂了。
回来贡献一下，看看大牛们的想法，如果能提供代码就更好了，我回头想想这题还是挺
复杂的。 |
k****r
发帖数: 807 | 2 这题就是leetcode的变种题吧。
leetcode是把被1包围的和外界连通的0都变成1；
题意是邻居有0才变1吗？还是本身是0就变1；邻居有0继续扩展？
如果是前者，当最后到了邻居没有0了，本身变1 吗？
如果是后者就简单了：
recursive？
public void changeToOne(int[][] matrix, i, j) {
if (i <0 || i > matrix.lengh || j < 0 || j > matrix[0].length || matrix[
i][j] == 1) return;
if ()
matrix[i][j] = 1;
changeToOne(int[][] matrix, i - 1, j);
changeToOne(int[][] matrix, i, j - 1);
changeToOne(int[][] matrix, i + 1, j);
changeToOne(int[][] matrix, i, j + 1);
} |
j**********3
发帖数: 3211 | |
b***e
发帖数: 1419 | 4 找包含i,j点的最小矩形, 其边上都是1. O(n)可解. 这里n是矩阵的元素个数.
recursion
【在 w*****1 的大作中提到】
: 看名字好像是来自东欧的哥儿们面的，本来HR说好的国人大哥不知道去哪儿了。。。
: 题目当时说的我就不是特别明白，大概是下面这个意思。
: 给一个任意大小的matrix A，大小mxn可以非常大，里面元素是0或者1。给个起始坐标[
: i][j]。
: 实现如下过程，如果A[i][j]的邻居（九宫格包括自己）有元素是0，则都改为1。
: 然后基于已经填好1的区域，向外扩张（每步只能扩张到已填好(都是1)区域的邻居），
: 如果扩张遇到有0元素都改为1。停止条件是全都到了矩阵边界，或者填好区域的邻居全
: 是1。
: 形象一点说，有点像扫雷游戏。0改1可以想象成插小旗，只是雷你都事先都知道了。
: 当时面试也就剩半个小时了，好像不是leetcode里的题（也可能是，我刷的不是很仔细
|
u***n
发帖数: 21026 | |
s********a
发帖数: 1447 | |
w*****1
发帖数: 6807 | 7 我觉得最可能是这个，根本没准备
【在 s********a 的大作中提到】
: 这个bfs把
|
w*****1
发帖数: 6807 | 8 随便，没有限制语言，会的都行
【在 j**********3 的大作中提到】
: C++ or JAVA?
|
w*****1
发帖数: 6807 | 9 矩阵大小未知，他说可以非常大，所有不能从[0][0]开始找
【在 b***e 的大作中提到】
: 找包含i,j点的最小矩形, 其边上都是1. O(n)可解. 这里n是矩阵的元素个数.
:
: recursion
|
w*****1
发帖数: 6807 | 10 你看，这题确实是很难理解吧
是根据现在的元素，比如[i][j]，以他为中心的外面一个圈（也包括[i][j]），如果有
0的话，都要改成1。那么全部都是1的区域会越来越大，一直扩张，直到以这个区域为
中心的外面一个圈全是1，那么就停下来，或者都到矩阵边界了，也停下来。
不知道你说的leetcode题是哪一道，如果写下名字那更好。这面试哥们说recursive不
是正确的方向，好像意思就是基本做不出来，要考虑别的算法，而且矩阵也不是nxn，
是任意mxn
matrix[
【在 k****r 的大作中提到】
: 这题就是leetcode的变种题吧。
: leetcode是把被1包围的和外界连通的0都变成1；
: 题意是邻居有0才变1吗？还是本身是0就变1；邻居有0继续扩展？
: 如果是前者，当最后到了邻居没有0了，本身变1 吗？
: 如果是后者就简单了：
: recursive？
: public void changeToOne(int[][] matrix, i, j) {
: if (i <0 || i > matrix.lengh || j < 0 || j > matrix[0].length || matrix[
: i][j] == 1) return;
: if ()
|
|
|
b***e
发帖数: 1419 | 11 最终只有矩形能够让这个扩张停下来。所以要找包含起始点的最小矩形。用bfs模拟当
然可以找到解。我觉得有更有效的方法。
【在 w*****1 的大作中提到】
: 你看，这题确实是很难理解吧
: 是根据现在的元素，比如[i][j]，以他为中心的外面一个圈（也包括[i][j]），如果有
: 0的话，都要改成1。那么全部都是1的区域会越来越大，一直扩张，直到以这个区域为
: 中心的外面一个圈全是1，那么就停下来，或者都到矩阵边界了，也停下来。
: 不知道你说的leetcode题是哪一道，如果写下名字那更好。这面试哥们说recursive不
: 是正确的方向，好像意思就是基本做不出来，要考虑别的算法，而且矩阵也不是nxn，
: 是任意mxn
:
: matrix[
|
w*****1
发帖数: 6807 | 12 是啊，应该是这哥们原来工作碰过这个个问题，自己搞了半天发现个好的方法。
关键是现在是电话面试，出这种题有意思么。。。
就算用bfs，半个小时写出来估计也不是那么容易啊，而且还有很多corner要你去考虑
。。。
这哥们是诚心要黑我了。。。
【在 b***e 的大作中提到】
: 最终只有矩形能够让这个扩张停下来。所以要找包含起始点的最小矩形。用bfs模拟当
: 然可以找到解。我觉得有更有效的方法。
|
b***e
发帖数: 1419 | 13 这就是故意黑。
【在 w*****1 的大作中提到】
: 是啊，应该是这哥们原来工作碰过这个个问题，自己搞了半天发现个好的方法。
: 关键是现在是电话面试，出这种题有意思么。。。
: 就算用bfs，半个小时写出来估计也不是那么容易啊，而且还有很多corner要你去考虑
: 。。。
: 这哥们是诚心要黑我了。。。
|
p******d
发帖数: 63 | 14 假设(i,j)是起始坐标:
先横着扫一遍，找到最大的x1i的全为1的列;
再竖着扫一遍，类似找到y1和y2;
(x1,x2,y1,y2)就是最小的包含(i,j)的长方形. |
l******s
发帖数: 3045 | 15 其实就是围棋算气，毛子这是。。。
标[
【在 w*****1 的大作中提到】
: 看名字好像是来自东欧的哥儿们面的，本来HR说好的国人大哥不知道去哪儿了。。。
: 题目当时说的我就不是特别明白，大概是下面这个意思。
: 给一个任意大小的matrix A，大小mxn可以非常大，里面元素是0或者1。给个起始坐标[
: i][j]。
: 实现如下过程，如果A[i][j]的邻居（九宫格包括自己）有元素是0，则都改为1。
: 然后基于已经填好1的区域，向外扩张（每步只能扩张到已填好(都是1)区域的邻居），
: 如果扩张遇到有0元素都改为1。停止条件是全都到了矩阵边界，或者填好区域的邻居全
: 是1。
: 形象一点说，有点像扫雷游戏。0改1可以想象成插小旗，只是雷你都事先都知道了。
: 当时面试也就剩半个小时了，好像不是leetcode里的题（也可能是，我刷的不是很仔细
|
b*****p
发帖数: 9649 | 16 微软的online test也问到了这题的变形，问的是围棋的一手棋是不是自填一口气的自
杀 |
w*****1
发帖数: 6807 | 17 仔细想了想，这个做法不行，不是这毛子哥的题目要求。他不需要矩阵中所有一行或一
列都是1，只要求其中一部分都是1，但要cover住(i,j)。
要不然我还真以为他这个题目原来如此简单，说那么复杂干嘛。
后面大哥说的围棋算气还真是说对了，题目就是这个意思。
【在 p******d 的大作中提到】
: 假设(i,j)是起始坐标:
: 先横着扫一遍，找到最大的x1i的全为1的列;
: 再竖着扫一遍，类似找到y1和y2;
: (x1,x2,y1,y2)就是最小的包含(i,j)的长方形.
|
w*****1
发帖数: 6807 | 18 大哥厉害，想了想还真是这么回事，谢谢提点。毛子什么时候对围棋感兴趣了。。。
我回去google下算法代码，真是坑爹啊！！！
【在 l******s 的大作中提到】
: 其实就是围棋算气，毛子这是。。。
:
: 标[
|
