亚麻 OA1 2022-01-15 新鲜热辣

O

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

，0代表没有路。
DP问题。。没写好，内心非常自责
此次面试886，再会

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第一题个人思路：

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第一题，我有另外一个思路， 用两个priority queue， 起始位置放一个queue，终止位置在放一个queue，然后遍历所有building， 然后有一个当前位置的router 数量的变量， 如果遇到新起始位置 变量++ queue pop()， 遇到终止位置就变量-- queue pop()， 然后遍历的过程中如果足够覆盖那个building就加到最后的结果里。

楼主是ng吗，感觉和之前ng换了题型？

匿名者 发表于 2022-1-15 22:02
楼主是ng吗，感觉和之前ng换了题型？

不是ng，确实没有在别的帖子看到

teargone08 发表于 2022-1-16 06:25
第一题， 我直接用暴力，估计过不了。
public int getServedBuilding(int[] buildingCount, int[] routeL ...

我也是这么做的 过不了嘿嘿

第二题bfs，我周三也是做的这道题
第一题应该可以对router数据排序，通过整理router location和range信息，然后生成intervels,然后合并intervel，最后就能够用一次遍历获得覆盖的house数量。复杂度应该也只是o(n)。简单版的幺伞而留

meiyoudewo 发表于 2022-1-16 16:47
第二题bfs，我周三也是做的这道题
第一题应该可以对router数据排序，通过整理router location和range信息 ...

第二题 DP 能解吗？

厉害厉害，题号都出来了。

FoxShuang 发表于 2022-1-16 16:51
第二题 DP 能解吗？

厉害厉害，题号都出来了。

dp不是很适合这种题。而且我觉得你应该说的是dfs吧，dfs会超时。

多谢楼主分享~