【免费】RE_双指针1_双指针1资源-CSDN文库

需积分: 0 110 浏览量 2022-08-03 23:43:27 上传评论收藏 205KB PDF 举报

资源详情

资源评论

资源推荐

RE_双指针.md

2021/6/22

1 / 3

Q53 : 最大子序和

1. 动态规划：f(i) : 以ai结尾的最大子序和。 f(i) = max(f(i-1)+ai, ai); 然后dp压缩，空间使用o(0)

2. 滑动窗口：假设当前窗口和为sum, 最终结果为ans, 若当前sum <= 0 则如果对其继续扩张，sum对后边

反而是负担，不会有贡献。所以舍弃该窗口，然后sum = ai, ans = max(ans,sum) 只有当sum > 0 时对

sum扩张才有意义。

Q76 : 最小覆盖子串 s = "ADOBECODEBANC", t = "ABC" ans = "BANC" 即

BANC是一个最小子串，包含了 A,B,C三个字符。时间要求o(n)

1. right指针遇到不属于t的字母就不断扩张，遇到属于t的字母就停下，然后left收缩

2. left收缩时，若指向属于t的字母，就判断去掉之后是否满足t的需要，满足就收缩，否则right继续扩张。

ans在收缩后保留最小值。

3. 使用count记录频率到达t的字母的个数。当count到达t的字符频率就++， count和t的字符种类相同时，

说明当前窗口满足t.

4. 窗口收缩扩展时，要动态的修改count的值。

窗口第二大的值

Q239 : 滑动窗口最大值 [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]

1. 问题的关键是：若左端移出窗口，而他恰好是窗口内最大值。那么如何找到第二大的那个值。

2. 使用双端队列，的单调递减栈。若移出的元素不是队头那么直接删除即可，因为删除的不是窗口内最大

值。

3. 若移出窗口元素是队头元素，说明删除元素是窗口内最大值。那么对头元素也要删除。然后以单调栈的

方式把新元素加入队列尾部此时就可以确定新窗口的最大值，一定是队头。

4. 大的值入栈，会导致小的值出栈，恰好，小的值不需要。

Q283 : 移动零把数组中的0移动到数组右侧，且不破坏非0元素的顺序。

1. left指向永远指向当前数组第一个0的位置。 right指向left后第一个非0元素，然后交换。

2. right再走向下一个非0元素，left走向下一个0.

Q395 : 至少有 K 个重复字符的最长子串要求子串中每一个字符的频率都

大于等于k

1. 枚举字符

1. 对于字符x,若x的频率小于K,那么所有含有字符x的串都是非法的。

2. 对当前串进行字符统计，找到频率小于 k的字符x。然后按照x字符进行分割。

3. 若一个串找不到分割符，说明该串每一个字符频率都大于等于k.

4. 对以上过程进行递归，每次都对当前串进行统计。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

评论0

内容反馈

陈莽昆

粉丝: 19
资源: 291

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip