Google 不甘心的跪经

比较两个 bst 只需要比较两个的 preorder 一样。

因为知道 preorder，inorder 就已经确定（BST），然后根据 preorder 和 inorder 就可以还原出一棵 binary tree。

3d596d24 发表于 2016-11-23 13:09
比较两个 bst 只需要比较两个的 preorder 一样。

因为知道 preorder，inorder 就已经确定（BST），然后 ...

嗯这个解法是对的

楼主加油！！！

稀疏矩阵我觉得就用嵌套hashtable就能解决吧？因为如果是十字链表你也得是 doublely-linkedlist吧，这样你删除整行也得从左到右遍历linkedlist，然后cut与上下节点的link，这样的时间复杂度也是O(n)，操作数也和hashtable方法一样。。而且你十字链表的头指针也得用个hashset存着。。

hwu2498 发表于 2016-11-23 13:38
稀疏矩阵我觉得就用嵌套hashtable就能解决吧？因为如果是十字链表你也得是 doublely-linkedlist吧，这样你 ...

补充一下，这道问题还需要写将矩阵整行整列设为某个值的函数，你说得好像也有道理。。 这里需要用到两个hash，hash(row, hash(col, val)), hash(col, hash(row, val))，时间复杂度是一样，不过因为要从两个里面都插入或者删除，代码应该还是十字链表应该要简洁一些

lyc1994 发表于 2016-11-23 23:57
补充一下，这道问题还需要写将矩阵整行整列设为某个值的函数，你说得好像也有道理。。 这里需要用到两个h ...

代码确实是doubly-linked list简洁，但是说实话linkedlist底层运行得其实比hashtable要慢的。。重要的是不仅时间复杂度一样，"number of operations" 还是一样，并没有起到太多优化的效果

求问LZ加面第一轮的逻辑树怎么做？

liqingfd 发表于 2016-11-23 12:54
求问楼主在onsite之后多久收到加面的通知呀～

两周之后

新宿车站 发表于 2016-11-27 15:55
求问LZ加面第一轮的逻辑树怎么做？

这道题挺有意思，主要我觉得还是分情况讨论，我写了写，看这里：
https://github.com/CoderLiang/FlipLogic

lyc1994 发表于 2016-11-23 03:26
https://en.wikipedia.org/wiki/Partial_sorting

梁神 这个题的idea是不是先对原数组做partition,求得第K大的元素M，然后双指针，比M小的放数组左边，比M大的放数组右面？