狗家谷阳挂经

cjhsu0319 发表于 2019/02/02 04:50:23
For question 4. 一个数如果在"正确"的位子上,那他就可以被binary search到,即使array不是有序.  For example, 2,1,3,6,7,5,9,5中,3就可以...

不知道你的“正确”是怎么定义的，但如果这指的是和有序（升序）排列的位置相同就为“正确”的话，你的做法是有问题的。
简单例子12543，4在正确的位置上，但因为第一次mid会选中5，右半部被舍弃了，4并不会被找到

第四题，build一个bst，然后看有多少是invalid node。

可以用类似于判断树是否为BST的思路：维护一个“值域”R=(lo, hi)（即在当前搜索下标范围[i, j]内，只有在R范围内的数才有可能被二分法找到）。求得当前搜索范围[i, j]的中点mid。如果A[mid]在当前的R中，那A[mid]就一定能被找到。然后分别递归mid的左右两侧[i, mid-1]和[mid+1, j]。递归左侧时，允许的值域是(lo, min(A[mid], hi))；同理右侧的值域是(max(A[mid], lo), hi)。如果任何时刻发现值域R已经不包含任何整数，那就表示[i, j]这个下标范围内没有任何能找到的数字。

patpat, 楼主HR有让你转SRE或者SETI吗

最后一题具体是要干嘛呀，给一个数组，没排序，然后给一个数，找数在不在数组里？
还是求每个数具体有多个？

补充内容 (2019-2-3 04:13):
啊，等等，我好像有点理解了，我再看看

嗯，我感觉13楼的解法是对的。
如果要求返回数值的话，要求是array的元素不重复。
有重复的话就返回的是对应元素的index吧。

补充内容 (2019-2-3 04:46):
递归接收检查的范围 i, j, 和 该范围对应的值域 lo, hi,
递归出口是
1. lo > hi ：该检查范围全都不合法
2. i +1 == j: 同样对比 lo, hi来返回。

stellari 发表于 2019-2-3 04:01
可以用类似于判断树是否为BST的思路：维护一个“值域”R=(lo, hi)（即在当前搜索下标范围内，只有在R范围内 ...

很有道理，谢谢大佬点拨！

请问第一题的思路是啥

第一题follow up是用pq来求出每个点到root的最短时间， 然后找出所有点重的最大值吗

yeou110 发表于 2019-2-2 03:49
最后一题完全摸不到头脑

第一题的follow up是不是用最小生成树的方法来做？