关注
3、给一个由大小写字母组成的字符串,每次删除一个最长的且最左侧的一个连续子串(需要由相同字母构成),求最小删除次数。模拟题,暴力模拟是O(n^2),据说这题暴力是可以AC的。一种低复杂度解法是把连续的部分组织成链表,比如aBBa变成 (a, 1) -> (B, 2) -> (a, 1) 这样,链表的好处是可以很快地删除并且合并两个端点。现在问题就是怎么找最长的那一个部分(比如之前的例子就是(B, 2))。可以考虑用线段树维护最大值,然后通过二分的形式把最大且最左的那一个部分给找出来。找出来之后更新链表,然后同时更新线段树。复杂度O(nlog^2n)。
4、给一个正整数组成的列表,找出一个长度不小于m的子段使得其中平均值最大。暴力据说可以骗不少分。首先区间和转前缀和,设前缀和为S[i],那么平均值就是(S[r] - S[l]) / (r - l)。给定一个平均值k,另(S[r] - S[l]) / (r - l) >= k 则有 S[r]-kr >= S[l]-kl。这样给定k,我们可以很快地找出满足上式成立的最大区间长度 t=r-l,而t关于k是单调的。这样二分答案k,然后对于每一个k找出这个t,如果t<m说明k找大了,就二分左半区间,否则二分右半区间。由于这个找t的过程需要算一个前缀最小值并且在其中二分,复杂度就是O(nlog^2n)。
查看原帖
2 1
相关推荐
07-15 12:06
门头沟学院 前端工程师 点赞 评论 收藏
分享
07-16 12:06
北京理工大学 机械工程师 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 假如你的老板掉河里,你的工作能为他做什么 #
30764次浏览 375人参与
# 你觉得早上几点上班合适? #
73072次浏览 306人参与
# 听劝,这个公司值得去吗 #
487029次浏览 1709人参与
# 学历贬值真的很严重吗? #
25398次浏览 178人参与
# 双非能在秋招上岸吗? #
222524次浏览 1178人参与
# 第一份工作应该选高薪还是热爱? #
68047次浏览 609人参与
# 打工人的工作餐日常 #
54155次浏览 426人参与
# 推荐一首陪你工作的歌吧 #
14859次浏览 99人参与
# 月薪多少能在一线城市生存 #
32792次浏览 336人参与
# 秋招签约后的心态变化 #
83281次浏览 819人参与
# 26届的你们有几段实习? #
47559次浏览 520人参与
# 大学最后一个寒假,我想…… #
47039次浏览 576人参与
# 你上一次加班是什么时候? #
89357次浏览 574人参与
# 你以为的实习VS真实的实习 #
33082次浏览 295人参与
# 2023毕业生求职有问必答 #
181612次浏览 1626人参与
# 外包能不能当跳板? #
37411次浏览 227人参与
# 哪些公司真双非友好? #
16300次浏览 82人参与
# 你后悔自己读研吗? #
22515次浏览 247人参与
# 追觅科技求职进展汇总 #
18689次浏览 120人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
92669次浏览 684人参与