米哈游笔试 2024.8.17

记录一下秋招参加的第二场笔试,难度不大

  1. 购买原石,月卡 or 直接买?

    暴力贪心一下就行

  2. m名工人,第i个区间 ,计算有多少个区间满足完全被其他区间覆盖?

    首先通过差分+前缀和求出每个位置被多少个区间覆盖,并将只有一个区间的对应位置(独苗)按顺序记录下来,最后通过二分查找判断每个区间内是否存在独苗,若是,则表示其无法被其他区间覆盖。

  3. 有一个长为n的数组a,询问q次,每次询问 有多少个连续的子数组包含x

    正难则反,考虑每次询问 有多少个子数组不包含x

    首先,我们需要记录数组中每个数出现的下标位置,针对一次询问,可以通过二分查找到大于等于l的x出现的最小下标,以及小于等于r的x出现的最大下标,中间这些x的出现下标将 分割成一个个子数组,答案即为 子数组个数 - 被分割出的每个子数组的子数组个数。后者可以通过前缀和优化 O(1) 求得。

#软件开发笔面经#
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 12:11
点赞 评论 收藏
分享
07-02 13:52
武汉大学 golang
骗你的不露头也秒
牛客87776816...:😃查看图片
点赞 评论 收藏
分享
06-12 10:50
门头沟学院 Java
你的不定积分没加C:我怎么在学院群看到了同样的话
点赞 评论 收藏
分享
陆续:不可思议 竟然没那就话 那就我来吧 :你是我在牛客见到的最美的女孩
点赞 评论 收藏
分享
码农索隆:单休一个月少休息4天,一年就是48天,平时节假日,别人3天假期,单休的两天
点赞 评论 收藏
分享
评论
点赞
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务