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

第一题， 我直接用暴力，估计过不了。
public int getServedBuilding(int[] buildingCount, int[] routeLocation, int[] routerRange) {
        int res = 0;
        for (int i = 0; i < routeLocation.length; i++) {
            int building = routeLocation[i];
            int rangeLeftIndex = building - routerRange[i];
            int rangeRightIndex = building + routerRange[i];
            for (int j = rangeLeftIndex; j < rangeRightIndex; j++) {
                buildingCount[j - 1]--;
            }
        }

        for (int i = 0; i < buildingCount.length; i++) {
            if (buildingCount[i] <= 0) {
                res++;
            }
        }
        return res;
    }

第一题个人思路：

您好！
本帖隐藏的内容需要积分高于 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会超时。

多谢楼主分享~