携程集团Java开发工程师(第四批)

10月23日 笔试

第一题
求可爱区间的数量(区间的最大值大于等于区间长度)怎么做啊,暴力便利30%测试用例通过,使用单调栈感觉还是不对。

第二题
合并后最后一个石子的最大权值,这道题测试用例没有通过

有没有AC的牛友,欢迎评论
全部评论
第一题 预处理一个数组为p数组pi表示i + a[i] - 1;表示以i为最左侧,能够扩展到的最右边界。 然后遍历1-n,在i位置,找到以i为右边界,区间[1, i - 1]选一个作为左边界满足的个数。 那么每个在i位置的贡献就为 a[i] + sum(p[j] >= i) (j ∈ [1, i - a[i]]) 。 sum(p[j] >= i) 表示j所在区间中,p[j] >= i 的个数。这个值可以用树状数组快速计算得出。 时间复杂度为O(nlogn)。
1 回复 分享
发布于 10-24 11:03 湖南
跟你一样一样的
点赞 回复 分享
发布于 10-23 16:15 安徽
第一题滑动窗口吗
点赞 回复 分享
发布于 10-23 16:26 四川
多多主站商业化招人,感兴趣可以聊一下~
点赞 回复 分享
发布于 10-23 20:26 上海
我也是这些题 好难…
点赞 回复 分享
发布于 10-24 12:57 美国

相关推荐

3 1 评论
分享
牛客网
牛客企业服务