关注
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
相关推荐
昨天 12:20
郑州大学 材料工程师 码农索隆:看我帖子https://www.nowcoder.com/discuss/764127692135370752,神州信息那个2B董成杰,我离职的时候,直接干他干了一仗
点赞 评论 收藏
分享
06-04 10:32
安徽大学 单片机 实习僧和BOSS直聘都投了几十家,硬件开发,硬件测试,嵌入式都投了,全是已读不回……我现在考虑想在秋招前速成一个Linux项目,其实现在完全不知道自己要找什么方向的,只能海投了,求大佬们给点意见😭😭😭
西工程小巴:数电课设+数字信号处理课设+微机原理课设?

点赞 评论 收藏
分享
牛客热帖
更多
- 1... 🌟择难路,未有疑,四非学院本运气拉满,春招拿下大厂后端4.5W
- 2... 秋招应该侧重准备哪个部分的内容1.5W
- 3... 恋爱四年没想到过自己会出轨8248
- 4... 史上最细SQL实战系列:sql笔试例题总结篇(建议收藏)7698
- 5... 其实主包早就找到工作了,但还是每天都刷7050
- 6... 离开软件测试才发现外面没有雨5371
- 7... 双非二本的漫漫游戏开发春招路Ver2.0——失业、感悟、再出发(万字长文)4961
- 8... 作为实习生,我问薪无愧4818
- 9... 25届毕业现在在家呆了一个多月,没工作4818
- 10... 从天坑文科到大二腾讯的经历4257
正在热议
更多
# 实习生的蛐蛐区 #
8528次浏览 68人参与
# 说说你知道的学历厂 #
3956次浏览 37人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
40461次浏览 291人参与
# 应届生,你找到工作了吗 #
6556次浏览 62人参与
# 秋招盘点:机械人值得去的企业 #
72908次浏览 671人参与
# 简历当中有水分算不算造假? #
7229次浏览 65人参与
# 双非应该如何逆袭? #
177402次浏览 3082人参与
# 你认为小厂实习有用吗? #
1765次浏览 27人参与
# 毕业旅行去哪玩儿 #
9143次浏览 127人参与
# 歌尔求职进展汇总 #
54811次浏览 335人参与
# 社会教会你的第一课 #
3366次浏览 58人参与
# 没有合适的工作,你会先找个干着,还是考公考研 #
117130次浏览 1134人参与
# 神州信息工作体验 #
12494次浏览 62人参与
# 三一集团提前批进度交流 #
23390次浏览 139人参与
# 非技术岗投递进展 #
145521次浏览 1264人参与
# 材料进Fab厂真的劝退吗? #
44258次浏览 184人参与
# 上班到公司第一件事做什么? #
62214次浏览 527人参与
# 百度工作体验 #
231742次浏览 2010人参与
# 数字马力求职进展汇总 #
179849次浏览 1489人参与
# 春招进度记录 #
344469次浏览 3352人参与
# 百度秋招提前批进度 #
106191次浏览 1124人参与