楼主: AllenNewgate
跳转到指定楼层
上一主题 下一主题
收起左侧

狗家谷阳挂经

全局:
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并不会被找到
回复

使用道具 举报

🔗
zwcelesta 2019-2-2 22:30:20 | 只看该作者
全局:
第四题,build一个bst,然后看有多少是invalid node。
回复

使用道具 举报

🔗
stellari 2019-2-3 04:01:35 | 只看该作者
全局:
可以用类似于判断树是否为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]这个下标范围内没有任何能找到的数字。

回复

使用道具 举报

🔗
vividlau 2019-2-3 04:11:10 | 只看该作者
全局:
patpat, 楼主HR有让你转SRE或者SETI吗
回复

使用道具 举报

🔗
vividlau 2019-2-3 04:12:30 | 只看该作者
全局:
最后一题具体是要干嘛呀,给一个数组,没排序,然后给一个数,找数在不在数组里?
还是求每个数具体有多个?

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

使用道具 举报

🔗
vividlau 2019-2-3 04:40:40 | 只看该作者
全局:
嗯,我感觉13楼的解法是对的。
如果要求返回数值的话,要求是array的元素不重复。
有重复的话就返回的是对应元素的index吧。

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

使用道具 举报

🔗
 楼主| AllenNewgate 2019-2-3 04:50:07 | 只看该作者
全局:
stellari 发表于 2019-2-3 04:01
可以用类似于判断树是否为BST的思路:维护一个“值域”R=(lo, hi)(即在当前搜索下标范围内,只有在R范围内 ...

很有道理,谢谢大佬点拨!
回复

使用道具 举报

🔗
donndonn 2019-2-6 14:12:06 | 只看该作者
全局:
请问第一题的思路是啥
回复

使用道具 举报

🔗
a2410036 2019-2-14 05:12:05 | 只看该作者
全局:
第一题follow up是用pq来求出每个点到root的最短时间, 然后找出所有点重的最大值吗
回复

使用道具 举报

🔗
littleric 2019-4-2 13:52:32 | 只看该作者
全局:
yeou110 发表于 2019-2-2 03:49
最后一题完全摸不到头脑

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表