欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode刷题笔记——滑动窗口

程序员文章站 2024-03-19 15:20:22
...

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. 代码