CNN制片人:通俄门全是瞎扯 我们就是为了收视率 (转载)# PDA - 掌中宝
w*1
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
没法做,我只能又胡扯了些别的想法。。。又问了问复杂度就算完事了,应该是稳稳的
挂了。
回来贡献一下,看看大牛们的想法,如果能提供代码就更好了,我回头想想这题还是挺
复杂的。
题目当时说的我就不是特别明白,大概是下面这个意思。
给一个任意大小的matrix A,大小mxn可以非常大,里面元素是0或者1。给个起始坐标[
i][j]。
实现如下过程,如果A[i][j]的邻居(九宫格包括自己)有元素是0,则都改为1。
然后基于已经填好1的区域,向外扩张(每步只能扩张到已填好(都是1)区域的邻居),
如果扩张遇到有0元素都改为1。停止条件是全都到了矩阵边界,或者填好区域的邻居全
是1。
形象一点说,有点像扫雷游戏。0改1可以想象成插小旗,只是雷你都事先都知道了。
当时面试也就剩半个小时了,好像不是leetcode里的题(也可能是,我刷的不是很仔细
),最近又回头搞论文去了,HR说这次面试问的是CS基础题。。。
做了半天想写个recursion算法,也写不出来。快没时间了,面试哥们说这题recursion
没法做,我只能又胡扯了些别的想法。。。又问了问复杂度就算完事了,应该是稳稳的
挂了。
回来贡献一下,看看大牛们的想法,如果能提供代码就更好了,我回头想想这题还是挺
复杂的。