狗家实习面经，求打捞！

Seventh 发表于 2018-1-31 15:44
楼主能问一下如果每个块都有承受能力这个题怎么答的吗？ 想不出来~~~~(>_

我当时给的思路是DFS，返回值是所有子节点的vaule和，然后拿这个和与当前节点承受能力比较，面试官说ok，但是时间不够就没写完

hxidkd 发表于 2018-1-31 17:32
求问第一轮若矩形有重叠时候的具体思路= =，感觉好难

当时没有想出来，后来想了一个思路，不确定对不对，可以参考一下：
将所有矩阵的x坐标存在一个list里并排序，然后把所有矩阵按x坐标排序，在每两个相邻的x坐标之间找矩形，这样就可以把有重叠的矩阵分成没有重叠的矩阵了，然后用第二个follow up的code得到解

请问楼主，承重是包括左右上的总重量吗，这么说在你的例子里，第二行第二列数值为4是不是无法承受，因为整个第一行有五个建筑块

恭喜楼主！！希望楼主一切顺利！
想问一问interval 那题的O(1)是怎么做的呢？楼主说boolean array，想了很久还是没想出来，希望能再给点hints

Victorzhang 发表于 2018-2-1 07:44
请问楼主，承重是包括左右上的总重量吗，这么说在你的例子里，第二行第二列数值为4是不是无法承受，因为整 ...

对的，是这样的

ja0b 发表于 2018-2-4 10:33
恭喜楼主！！希望楼主一切顺利！
想问一问interval 那题的O(1)是怎么做的呢？楼主说boolean array，想了很 ...

比如给你个Interval是[2,5]，那么array[2], array[3], array[4]和array[5]就都标为true，其他是false。如果你查3出有没有Interval，那就看array[3]是不是true就行了

zc1994zc 发表于 2018-2-4 15:19
比如给你个Interval是[2,5]，那么array[2], array[3], array[4]和array[5]就都标为true，其他是false。如 ...

哦哦原来是给Interval 插数字！我一直理解成了插Interval哈哈

感谢楼主！

楼主您好， 对于您的那个follow up我有点不太明白，如果一个数字是1，那么他上面就不能用任何数字了，还是说可以有1个呢？

有重叠的话用蠡口skyline的方法转成无重叠的就行了吧

jiaweib 发表于 2018-2-6 05:53
楼主您好， 对于您的那个follow up我有点不太明白，如果一个数字是1，那么他上面就不能用任何数字了，还是 ...

还可以有1个的