狗家实习面经，求打捞！

求问第一题有重叠咋做的

Seventh 发表于 2018-1-26 15:02
若这些块都有自己的承受能力，用数字表示 是什么意思呀？数字表示的是这个这个块竖直方向上， 可以地方连接 ...

比如这个块是9，那么它上方链接的块数不能超过9

xiaofengshan 发表于 2018-1-26 23:16
求问第一题有重叠咋做的

当时我也没有做出来，但是后来想想，感觉是蠡口里skyline的思路

zc1994zc 发表于 2018-1-27 01:01
比如这个块是9，那么它上方链接的块数不能超过9

还是不太理解诶。比如那个4，上面放了5块，那岂不是直接掉下来一块？那掉下哪一块怎么决定呢？

zc1994zc 发表于 2018-1-26 14:14
O(n)是把Interval存到list里，然后直接搜索
O(nlogn)是binary search
O(1)是把Interval存成boolean arr ...

懂了!感谢楼主！！

zc1994zc 发表于 2018-1-26 14:14
O(n)是把Interval存到list里，然后直接搜索
O(nlogn)是binary search
O(1)是把Interval存成boolean arr ...

求问楼主O(1)的详细做法？没懂存成什么样的boolean array。。

fly6464猪仔气球 发表于 2018-1-30 03:44
还是不太理解诶。比如那个4，上面放了5块，那岂不是直接掉下来一块？那掉下哪一块怎么决定呢？

其实我最开始的那个例子应该是有点问题的，是我随手打的，没有检查数值是否合理。下面这个例子应该是合理的：
ooooo
111oo
3o1oo
9o1oo
-------
最开始因为有9，所以可以支撑住。如果在3处断裂，那么右边虽然连着地面，但是无法支撑了，然后就全落下了

rippersean 发表于 2018-1-31 00:24
求问楼主O(1)的详细做法？没懂存成什么样的boolean array。。

就是说Interval的start和end都是int型，如果有Interval是[1,3]，那么我们就把boolean array的1，2，3都标为true。检查的时候就是O(1)了

楼主能问一下如果每个块都有承受能力这个题怎么答的吗？ 想不出来~~~~(>_<)~~~~

求问第一轮若矩形有重叠时候的具体思路= =，感觉好难