怎样redeem Marriott的free night certificate? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

怎样redeem Marriott的free night certificate?

怎样redeem Marriott的free night certificate?# Money - 海外理财

n*r2019-05-29 07:05

1 楼

同学前两天去谷歌onsite，有一道题大意是这样的
给一个m*n的矩阵，每个点不是0就是1，所有值为1的点是连通的，给你一个点的坐标，
告诉你这个点的值是1，求一个最小的矩形，能把所有的1包括在内
同学给了一个n logm的算法，但是面试官并不满意，想问问各位还有更优的算法吗？

p*a2019-05-29 07:05

2 楼

l*22019-05-29 07:05

3 楼

感觉直接求x轴的最大最小值，y轴的最大最小值就可以？这样一来是O(m*n)的算法...

O*W2019-05-29 07:05

4 楼

按正常订积分房的方式，支付的时候系统会提示有房券可用

h*g2019-05-29 07:05

5 楼

从这个点出发，遍历所有的联通的1就可以找到x,y的最大最小值了吧。复杂度就是那块
1区域的面积吧。

x*92019-05-29 07:05

6 楼

我们降维来看。
在一个数组上，有一个连续的子数组是全1，剩余位置是全0。
那么二分equal_range是最好的算法。
那么，在二维矩阵中，用二分法O(nlgm) + O(mlgn)的算法，应该不算差。
不知道面试官有没有O(m + n)的算法。

g*d2019-05-29 07:05

7 楼

变了形的树的遍历？

R*e2019-05-29 07:05

8 楼

这个题目还有其他context吧
感觉时间复杂度可以是O(mlogk) k表示最后矩形的长度，
跟最后求的矩阵多大有关系而不完全跟原来的矩阵有关。
如果k相对于m和n来说很小的话，那么这个要好很多。

n*r2019-05-29 07:05

9 楼

我和我同学的思路和您是一样的，不过据他说，面试官对这个复杂度并不是很满意

【在 x*******9 的大作中提到】

: 我们降维来看。
: 在一个数组上，有一个连续的子数组是全1，剩余位置是全0。
: 那么二分equal_range是最好的算法。
: 那么，在二维矩阵中，用二分法O(nlgm) + O(mlgn)的算法，应该不算差。
: 不知道面试官有没有O(m + n)的算法。

l*32019-05-29 07:05

10 楼

没懂，如何降维？降维本身不是牵扯到O(m*n)的运算么？

【在 x*******9 的大作中提到】

l*32019-05-29 07:05

11 楼

而且为什么一定有一个子数组有一段连起来的1？
那个连通的1可以在矩阵里面曲里拐弯的绕吧，可能弯弯折折的根本没有很长的连续的1
比如
1 1 1
1
1 1 1 1 1 1
1 1
1 1 1 1 1 1 1
1 1
1 1 1 1 1
1 1
1 1 1 1 1 1

【在 x*******9 的大作中提到】

l*32019-05-29 07:05

12 楼

楼上的图没画好，因为空格问题。。。请自行脑补一下蛇的样子

f*y2019-05-29 07:05

13 楼

做bfs遍历，找到每个新的1都update最左最右最上最下。

从这个点出发，遍历所有的联通的1就可以找到x,y的最大最小值了吧。复杂度就是那块
1区域的面积吧。

【在 h*********g 的大作中提到】

: 从这个点出发，遍历所有的联通的1就可以找到x,y的最大最小值了吧。复杂度就是那块
: 1区域的面积吧。

b*e2019-05-29 07:05

14 楼

这题要找边，不要找肚子。从这个点向四个方向找边界点，然后顺着边界点摸索边界在
哪。肚子就是四面都有点的。边界就是非肚子。边界搜寻也要向外，忽略向内的点。最
坏应该是图形边界的长度。如果是凸图形就是O(m+n)了。

【在 n******r 的大作中提到】

: 同学前两天去谷歌onsite，有一道题大意是这样的
: 给一个m*n的矩阵，每个点不是0就是1，所有值为1的点是连通的，给你一个点的坐标，
: 告诉你这个点的值是1，求一个最小的矩形，能把所有的1包括在内
: 同学给了一个n logm的算法，但是面试官并不满意，想问问各位还有更优的算法吗？

s*a2019-05-29 07:05

15 楼

怎么保证‘’一个连续的子数组是全1‘’？可以不连续啊

：我们降维来看。
：

s*32019-05-29 07:05

16 楼

假设起始点是(x,y) n rows , m cols
分四个方向找边界
(0,y) 找右边界
(0.y) 找左边界
(x,0) 找上边界
(x,0) 找下边界
以右边界来说
i= 0, j = y
while in range
if[i][j] ==1
update 右边界, j++;
else
i++;
其他四个搜寻可以类推每个是o(n+m) total complexity o(4(n+m)) 看看这样行不行?

n*r2019-05-29 07:05

17 楼

如果不是凸图形呢？比如一个蛇形，复杂度是O（m*n）

【在 b***e 的大作中提到】

: 这题要找边，不要找肚子。从这个点向四个方向找边界点，然后顺着边界点摸索边界在
: 哪。肚子就是四面都有点的。边界就是非肚子。边界搜寻也要向外，忽略向内的点。最
: 坏应该是图形边界的长度。如果是凸图形就是O(m+n)了。

n*r2019-05-29 07:05

18 楼

j++那就不对了，也有可能是j--

【在 s****3 的大作中提到】

: 假设起始点是(x,y) n rows , m cols
: 分四个方向找边界
: (0,y) 找右边界
: (0.y) 找左边界
: (x,0) 找上边界
: (x,0) 找下边界
: 以右边界来说
: i= 0, j = y
: while in range
: if[i][j] ==1

n*r2019-05-29 07:05

19 楼

并不是要把降维，而是先把问题简单化，如果矩阵是一维的怎么办

【在 l*3 的大作中提到】

: 没懂，如何降维？降维本身不是牵扯到O(m*n)的运算么？

s*i2019-05-29 07:05

20 楼

他的意思是说，对每一行或者每一列分别二分查找，再把结果汇总起来。
不过这个解法忽略了一个已知条件，就是一开始会告诉你一个是1的点的坐标。
我的想法是这样的，从最开始的那个点开始，在一行内往左往右延伸，找到1的左右边
界，记录下来到(LEdge, REdge)。
然后分别往上和往下依次check另外的行，看LEdge和REdge对应的点是否是1. 如果是1
，将
那一
侧继续往外延伸，更新相应edge值。否则不变。
同样对各列操作，复杂度应该是O(m+n) + O(m+n) = O(m+n)

【在 s********a 的大作中提到】

: 怎么保证‘’一个连续的子数组是全1‘’？可以不连续啊
:
: ：我们降维来看。
: ：

r*g2019-05-29 07:05

21 楼

这个二分什么意思？一维数组又没有排序，即使只有0/1，即使有一段是连续1，如何找
到1？没法二分吧

【在 x*******9 的大作中提到】

b*e2019-05-29 07:05

22 楼

是的。最坏的情况是O(mn)。这个和quick sort的意思是一样的。只有在很扭曲的情况
下才会很差。如果一定要保证最坏复杂度，就只能两个算法一起走了。我认为这是出题
人想要的答案。

【在 n******r 的大作中提到】

: 如果不是凸图形呢？比如一个蛇形，复杂度是O（m*n）

n*r2019-05-29 07:05

23 楼

已知有一个点为1，所以就可以二分了

【在 r*******g 的大作中提到】

: 这个二分什么意思？一维数组又没有排序，即使只有0/1，即使有一段是连续1，如何找
: 到1？没法二分吧

l*32019-05-29 07:05

24 楼

这个答得好。

1

【在 s*******i 的大作中提到】

: 他的意思是说，对每一行或者每一列分别二分查找，再把结果汇总起来。
: 不过这个解法忽略了一个已知条件，就是一开始会告诉你一个是1的点的坐标。
: 我的想法是这样的，从最开始的那个点开始，在一行内往左往右延伸，找到1的左右边
: 界，记录下来到(LEdge, REdge)。
: 然后分别往上和往下依次check另外的行，看LEdge和REdge对应的点是否是1. 如果是1
: ，将
: 那一
: 侧继续往外延伸，更新相应edge值。否则不变。
: 同样对各列操作，复杂度应该是O(m+n) + O(m+n) = O(m+n)

a*a2019-05-29 07:05

25 楼

http://www.geeksforgeeks.org/find-the-row-with-maximum-number-1

E*g2019-05-29 07:05

26 楼

好像有一个问题，因为每一行上的1不一定是联通的，如果只是检查Redge或者Ledge相
应的位置来确定是不是要在这一行延伸的话，会miss掉一些行。比如下面这个例子
000111100
110000110
011001100
001111000
如果是从第一行开始，那么第一次得到左边届 Ledge 是3，再往下check的时候，会
miss掉第二行和第三行左边的1

1

【在 s*******i 的大作中提到】

b*w2019-05-29 07:05

27 楼

这个能work吗？edge不一定是一直向外延伸的，可能先往里走然后再往外走。

1

【在 s*******i 的大作中提到】

s*i2019-05-29 07:05

28 楼

yes, you are right...
如果遇到类似正弦波那样的pattern就会出错。

【在 E******g 的大作中提到】

: 好像有一个问题，因为每一行上的1不一定是联通的，如果只是检查Redge或者Ledge相
: 应的位置来确定是不是要在这一行延伸的话，会miss掉一些行。比如下面这个例子
: 000111100
: 110000110
: 011001100
: 001111000
: 如果是从第一行开始，那么第一次得到左边届 Ledge 是3，再往下check的时候，会
: miss掉第二行和第三行左边的1
:
: 1

a*n2019-05-29 07:05

29 楼

以上次发现的是1的点为起点，用同样的方法反向扫一遍就可以了。

【在 s*******i 的大作中提到】

: yes, you are right...
: 如果遇到类似正弦波那样的pattern就会出错。

s*i2019-05-29 07:05

30 楼

可以以上次的边际点为起点，在剩下的区域里面再扫，不过再扫一次不行。想象一个频
率很高的正弦波，需要来回扫好几次。这样的话复杂度就会高了，不确定是不是一个
good answer.

【在 a*******n 的大作中提到】

: 以上次发现的是1的点为起点，用同样的方法反向扫一遍就可以了。

r*g2019-05-29 07:05

31 楼

还是不明白，假设很多的0，中间在某个位置出现了一个1，如何找到这个1？
这个除了线性搜索，还可以二分？到底是在说binary search, divide and conquer，
还是说二分法？
thanks.

【在 n******r 的大作中提到】

: 已知有一个点为1，所以就可以二分了

r*g2019-05-29 07:05

32 楼

我猜，你想说的是，已经知道那个1的位置，想找出这个1的左边界和右边界，对吧。
但是除了这个连续的1，还有其他的1啊
而其他的1的位置是未知的，没有规律的。

【在 n******r 的大作中提到】

: 已知有一个点为1，所以就可以二分了

n*r2019-05-29 07:05

33 楼

如果给你一个一维数组，其中有一段是1，其他都是0，给你一个点，已知这个点是1，
让你找边界
上升到二位，一样的情况

【在 r*******g 的大作中提到】

: 我猜，你想说的是，已经知道那个1的位置，想找出这个1的左边界和右边界，对吧。
: 但是除了这个连续的1，还有其他的1啊
: 而其他的1的位置是未知的，没有规律的。

r*g2019-05-29 07:05

34 楼

ok
你说的情况是有一段是1，这里二维因为1是连接在一起所以也是一段。所以是想通过这
个说明复杂度差不多也是logN
Thanks

【在 n******r 的大作中提到】

: 如果给你一个一维数组，其中有一段是1，其他都是0，给你一个点，已知这个点是1，
: 让你找边界
: 上升到二位，一样的情况

r*g2019-05-29 07:05

35 楼

不过这并不代表最后得到的解法会是O(nlgm) + O(mlgn)。因为虽然所有的1连成一起，
每一行其实可能出现多段连续的1，需要仔细想想。

c*e2019-05-29 07:05

36 楼

听起来合理
如果1成块状，那么会比较优化
如果1成线状，那么图形边界的长度，和1的个数就差不多了

【在 b***e 的大作中提到】

r*g2019-05-29 07:05

37 楼

其实就是DFS+线性搜索吧
如果是稀疏矩阵，我们把所有1遍历完也是O(N)，如果1很密，那么就要找边，争取做到
O(N)。
怎么找边呢，从已知点出发，做一次DFS，停止条件是当前节点的x在原点左边并且无法
再扩张，或者到了尽头，或者没法再扩张x就回到原点。同时再针对大于原点x的做一次
扩展。这样得到3个点，两个终止点和一个原点。找出矩形面积。
然后沿着这个矩形的边继续搜索，如果矩形还能扩张，那么必然存在一点是1并且可以
通过dfs向外扩展，矩形边上有的1只能向内扩展，这些全部不计算。对矩形的每条边，
只需要考察上面的1能否向一个方向扩展即可。每次扩展都是dfs。
比如说对左边边上的节点，只需要一直向左扩展，一旦x不是向左而是向右就停止。
其实第一次的扩展也可以这样，这样程序好写一些。
所以最后的复杂度是O(N)*k，这个k就很玄妙，似乎定不下来。

l*s2019-05-29 07:05

38 楼

感觉还是二分，不过是以矩形四边一个框的形式二分而不是每个边的形式。每个边的查
法的劣势在于会有过多的在另一向量上的浪费查询。四边一起查的方式虽然在理论上计
算time complexity是(m+n)*ln(m +n)但实际上因为此方法的剪枝优势，实际会少很多。

n*r2019-05-29 07:05

39 楼

最后的解法是这样的：
一维的情况你已经知道了，现在上升到二维，给一个二维矩阵，里面有0有1，所有的1
都是连续的，给一个点的坐标，已知这个点的值为1，求一个最小的矩形可以把所有的1
包括在内。
要找的矩形可以等同于找所有1形成的图形的边界，比如说找最左边的边界，
假设已知点的坐标为（x，y），我们就以x为end，0为start做二分，得到mid后，判断
以mid为横坐标的这一列是否有值为1的点，如果没有，说明1图形的左边界在mid的右边
，反之就在左边，继续二分，最后找到结果。
在横坐标上做二分的复杂度是logn，每列搜索的时间是m，所以总的时间复杂度就是
mlogn＋nlogm。
这是一道同学的面试题，我也没有别的条件……所以楼上很多遍历找边界的算法可能在
实际工作中更有效，不过就平均情况来讲，我觉得这个算法可能已经是最优的了……

【在 r*******g 的大作中提到】

: 不过这并不代表最后得到的解法会是O(nlgm) + O(mlgn)。因为虽然所有的1连成一起，
: 每一行其实可能出现多段连续的1，需要仔细想想。

r*g2019-05-29 07:05

40 楼

Thanks.
实际中我觉得dfs估计更快，二分法时间复杂度是固定的，dfs的话，除非输入满足一定
的pattern，不然效率肯定蛮高的。

1
的1

【在 n******r 的大作中提到】

: 最后的解法是这样的：
: 一维的情况你已经知道了，现在上升到二维，给一个二维矩阵，里面有0有1，所有的1
: 都是连续的，给一个点的坐标，已知这个点的值为1，求一个最小的矩形可以把所有的1
: 包括在内。
: 要找的矩形可以等同于找所有1形成的图形的边界，比如说找最左边的边界，
: 假设已知点的坐标为（x，y），我们就以x为end，0为start做二分，得到mid后，判断
: 以mid为横坐标的这一列是否有值为1的点，如果没有，说明1图形的左边界在mid的右边
: ，反之就在左边，继续二分，最后找到结果。
: 在横坐标上做二分的复杂度是logn，每列搜索的时间是m，所以总的时间复杂度就是
: mlogn＋nlogm。

f*e2019-05-29 07:05

41 楼

都木有人贴个code呢。。。