狗家昂赛跪经

jeanwang2012 发表于 2018-3-14 05:16
输入可以自己定义，他给举的例子里看是一个类似2d vector的，以及一个会消失的砖块的位置(i,j)
**** 本 ...

楼主，你好，请问我们怎么确定一个 "b" 会不会下落呢？ 如图中如果去掉 比如说第二行中左数第四个 b 的话，是哪些 brick 掉下来呢？ 谢谢！

jeanwang2012 发表于 2018-3-14 05:16
输入可以自己定义，他给举的例子里看是一个类似2d vector的，以及一个会消失的砖块的位置(i,j)
**** 本 ...

这题感觉应该首先以紧挨着天花板的几个砖块作为种子进行BFS，构造每个砖块的依赖和被依赖列表（记录a被b和c稳定住， b稳定了d和e等），然后对于输入的砖块(i,j)，遍历它的被依赖列表，把里面元素的依赖列表里删除该砖块，如果依赖列表为空了，说明这个砖也会掉，又是一次类似BFS的过程
我理解的对么？

zhengyiyu 发表于 2018-3-14 07:50
rank我的理解就是sort后的顺序，所以理解的就是找到第k大的数字，或者给一个节点，想知道他在所有数据里 ...

层主，这个思路当然是对的，但是这个方法问题是不是在于如果BST不平衡的话，插入，删除都几乎是O（n）了？

楼主，感谢分享面经！请问第一题是不是类似于LC司令就？需要输出所有最长palindrome呗？

Kwang100 发表于 2018-3-15 03:19
层主，这个思路当然是对的，但是这个方法问题是不是在于如果BST不平衡的话，插入，删除都几乎是O（n）了 ...

这个如果不写代码，纯followup的话，用个 height balance的bst就可以解决了吧

感觉不会让写出来的，最多就提一下红黑树/avl树之类的呗。

其实这个题，我还想过另外一种方式就是用bucket的思想，在对数据有假设的情况下，或许能做到overhead很高的O（1），或者O（logn）的话，在bucket级别上加上skip list的结构。但是基本只能用来口头讨论，不能写代码了

zhengyiyu 发表于 2018-3-15 03:47
这个如果不写代码，纯followup的话，用个 height balance的bst就可以解决了吧

感觉不会让写出来的，最 ...

嗯..但是这一轮就这一题，看样子是要写代码的..
bucket这种方法到没有想到，skip list没听过，查一查..

jeanwang2012 发表于 2018-3-14 05:16
输入可以自己定义，他给举的例子里看是一个类似2d vector的，以及一个会消失的砖块的位置(i,j)
**** 本 ...

问下楼主这道题是怎么回答的？每个砖块不是只由正下方的砖块支撑的吗？谢谢

请问第一题的shuffle和删除是什么意思呢？能再详细说说么？