Google Onsite

virpro 发表于 2016-10-8 02:11
如果你的BST是
       [4, 6]
[1, 3]     [8, 9]

你就找和lower bound和upper bound分别重合的最左和最右边的interval，然后三个合起来，中间的全部删掉就好了

sunnyroom 发表于 2016-10-8 05:39
请问大神，game of life那题，board 无限大时该怎么处理。。。。
碰见这种输入 是 stream啊， 什么什么 ...

用map存alive的cell，然后再大就分机器存了

楼主第一轮怎么做的，给interval排序，然后追加interval，时间复杂度是O（n）的。

kevinwangjk 发表于 2016-9-22 13:05
假设棋盘如下
1 4 7 10
2 5 8 11

没看懂，能详细讲讲吗

virpro 发表于 2016-10-8 02:11
如果你的BST是
       [4, 6]
[1, 3]     [8, 9]

disjoint那题，我直接用的tree set，先拿到他的floor interval，然后可以合并直接把那个interval remove掉，然后合并之后重新插入，自己实现比较麻烦

kevinwangjk 发表于 2016-9-22 13:05
假设棋盘如下
1 4 7 10
2 5 8 11

但问题在于算5的时候，最后算的是一个综合状态啊，比如多余3个的时候死，等于3个时候复活，就算你知道5是从死到复活，你也不知道到底5周围哪些是死的哪些是活的，除非这样，算5的时候算了8个方向，得到SUM， 然后算8的时候，去掉1,2,3，加上5，去掉自身，再加上10 11 12，其实还是看了8个格子