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 的大作中提到】 : 其实就是围棋算气,毛子这是。。。 : : 标[
|