leetcode刷题笔记——滑动窗口
leetcode刷题笔记——滑动窗口
目前完成的滑动窗口的leetcode算法题序号:
中等:1208
困难:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reconstruct-itinerary
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
文章目录
算法理解
滑动窗口和双指针的区别可以看零神在leetcode中的文章
提示:以下是滑动窗口相关的刷题笔记
一、1208题:尽可能使字符串相等
1.题干
给你两个长度相同的字符串,s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销(开销可能为 0),也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串,则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串,则返回 0。
题意梳理:这题的题意乍一看有点迷,实际的目的就是:给定一个数,作为允许变动字符串的次数(一次只能改变ASCII对应数值的1大小),问能够多大程度把两个字符串修改成一样的,问相同的部分最长能有多长。
2.思路
滑动窗口,窗口从0索引,窗口长度0开始向右滑动,每次迭代,窗口的长度只能增大或保持不变,不能够减小。
1)当窗口中,两个字符串之间字符的ASCII码数值之差的的绝对值小于等于限定值,窗口加长1;
2)如果当窗口中,两个字符串之间字符的ASCII码数值之差的的绝对值大于限定值,窗口长度不变,向右滑动,直到找到下一个更合适的窗口位置,再扩展窗口大小;
3.代码
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
lens = len(s)
left, right = 0, 0
sums = 0
#窗口的右边界不能超过给定字符串的右边界
while right < lens:
#每次迭代更新窗口中两个字符串ASCII码值之间的差值的绝对值
sums += abs(ord(s[right]) - ord(t[right]))
#如果超过限定值,右移左边界,保持窗口长度不变,窗口向右滑动
if sums > maxCost:
sums -= abs(ord(s[left]) - ord(t[left]))
left += 1
#无论如何窗口右边界每次迭代都向右移动一位,以保证窗口的长度不会减小
right += 1
#最终窗口的长度就是满足条件的最长字串的长度
return right - left
4. 问题点思考
二、
1.题干
2.解题思路
3.代码
4. 注意点
三、
1. 题干
2. 思路
3. 代码
四、
1. 题干
2. 解题思路
3. 代码
下一篇: AC自动机(python)