携程集团Java开发工程师(第四批)
10月23日 笔试
第一题
求可爱区间的数量(区间的最大值大于等于区间长度)怎么做啊,暴力便利30%测试用例通过,使用单调栈感觉还是不对。
第二题
合并后最后一个石子的最大权值,这道题测试用例没有通过
有没有AC的牛友,欢迎评论
第一题
求可爱区间的数量(区间的最大值大于等于区间长度)怎么做啊,暴力便利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)。
跟你一样一样的
第一题滑动窗口吗
多多主站商业化招人,感兴趣可以聊一下~
我也是这些题 好难…
相关推荐