leetcode滑动窗口

深碍√TFBOYSˉ_ 2022-10-27 01:33 175阅读 0赞

### leetcode滑动窗口 ###

*  一、题目
 *  二、思路和图示化讲解
 *  三、代码解析（每一行都有解析）

> 该篇用于记录"滑动窗口"类的做法，双指针。  
> 对比自己的代码又长又乱、时间复杂度还高，高血压都出来了。  
> 看完官方的代码，优美的如诗词般，不多也不少，每一行代码到恰到好处。  
> 我直呼，woshishabi~~

# 一、题目 #

424 替换后的最长重复字符  
**【中等】**  
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。  
**【注意】**：字符串长度 和 k 不会超过 10^4。  
示例 1：  
输入：s = “ABAB”, k = 2  
输出：4  
解释：用两个’A’替换为两个’B’,反之亦然。  
示例 2：  
输入：s = “AABABBA”, k = 1  
输出：4  
解释：  
将中间的一个’A’替换为’B’,字符串变为 “AABBBBA”。  
子串 “BBBB” 有最长重复字母, 答案为 4。

--------------------

# 二、思路和图示化讲解 #

**整体上来说**就是用一个maxl的窗口罩住字符串，慢慢扩大并移动，判断将窗口中任意位置上的字符替换成另外的字符，总共可最多替换 k 次，找到包含重复字母的最长子串的长度是否比之前找到的大则增大窗口继续移动。否则就维持窗口大小继续。最后返回窗口大小。

**细节上**

1.用一个26个元素的数组arr存储在\[l,r\]区间内出现的每个字母的次数  
2.区间\[l,r\]是从\[0,0\]开始，探寻将区间\[l,r\]中任意k个位置上的字符替换成另外的字符得到最大连续且字母相同的长度记录于maxl,\[l,r\]区间的长度就是maxl的映射。每扩充一次该区间，将该字母对应的数组arr中的元素加一，并判断满足题意的最大长度比之前出现过的长度大还是小。  
2\_1大，则保持扩大后区间的长度继续向下探寻。（即将右边界右移）  
2\_2小，则保持该区间的长度继续向下探寻（即将左边界右移），并将左边界移出的字母对应的数组arr中的元素减一。  
3.右边界右移出\[0,s.length()-1\]区间，r==slen退出循环，返回结果。

> 最好对照下面的代码看，更好理解  
> 输入：s = “ABACACDA”, k = 2  
> 输出：5  
> 制图过程有点赶，可能有误，麻烦大家指出

1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center]  
2  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 1]  
3  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 2]  
4  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 3]  
5  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 4]

6  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 5]

7  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 6]

8  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 7]

9  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 8]  
10  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 9]

# 三、代码解析（每一行都有解析） #

主代码

int characterReplacement(string s, int k)
    { 
        vector<int> arr(26);        //记录区间中的存在的所有字母的长度
        int l = 0, r = 0, maxl = 0; //[l,r]边界，maxl是[l,r]中在可以替换k次的得到的最长的连续相同的字母长度
        int slen = s.length();
        if (slen <= 1) //小于等于一的字母长度直接返即可
            return slen;
        while (r < slen) //在右边界走出[0，s.length()]区间时已经是最后一个可能存在[l,r]的，所以可以退出，无需做无用功
        { 
            arr[s[r] - 'A']++;                 //记录在[l,r]中26个字母出现的次数
            maxl = max(maxl, arr[s[r] - 'A']); //更新出现次数的字幕的长度
            if (r - l + 1 - maxl > k)          //r-l+1即在[l,r]中所有字母个数r-l+1-maxl即区间中与最长的字母不同的字母个数
            { 
                //左边边界移动，减去边界之外的字母所对应地个数
                arr[s[l] - 'A']--;
                l++;
            }
            r++; //移动右边界，若移动到边界不可以存在的区间即r==slen，即退出条件
        }
        return r - l; //不同于r-l+1是因为r在退出条件时已经走出[0,s.length()]多一步
    }

测试代码

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    
    int characterReplacement(string s, int k)
    { 
        vector<int> arr(26);        //记录区间中的存在的所有字母的长度
        int l = 0, r = 0, maxl = 0; //[l,r]边界，maxl是[l,r]中在可以替换k次的得到的最长的连续相同的字母长度
        int slen = s.length();
        if (slen <= 1) //小于等于一的字母长度直接返即可
            return slen;
        while (r < slen) //在右边界走出[0，s.length()]区间时已经是最后一个可能存在[l,r]的，所以可以退出，无需做无用功
        { 
            arr[s[r] - 'A']++;                 //记录在[l,r]中26个字母出现的次数
            maxl = max(maxl, arr[s[r] - 'A']); //更新出现次数的字幕的长度
            if (r - l + 1 - maxl > k)          //r-l+1即在[l,r]中所有字母个数r-l+1-maxl即区间中与最长的字母不同的字母个数
            { 
                //左边边界移动，减去边界之外的字母所对应地个数
                arr[s[l] - 'A']--;
                l++;
            }
            r++; //移动右边界，若移动到边界不可以存在的区间即r==slen，即退出条件
        }
        return r - l; //不同于r-l+1是因为r在退出条件时已经走出[0,s.length()]多一步
    }
    int main()
    { 
        string str1 = "ABAB";
        cout << "length:" << characterReplacement(str1, 2) << endl;
        string str2 = "AABABBA";
        cout << "length:" << characterReplacement(str2, 1) << endl;
        string str3 = "ABACACDA";
        cout << "length:" << characterReplacement(str3, 2) << endl;
        system("pause");
        return 0;
    }

![在这里插入图片描述][20210202185417422.jpg_pic_center]

--------------------

**回见~**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/5cf14805b5b14dbf84e8dd7e7a222edb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/18e8b5782a6147ec9478fc69afa620e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221024/43b65c2c630e4737bb5ba7371f750967.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221024/92900c0973c24d59b51b028a0fe75cb6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221024/278838823af0400f808b6cdec1c4542f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221024/8cf72a27aa4e4bb3af7d8df3a05bb567.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221024/a2259e7e45264037ab2b465f03e2c513.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221024/2f47e64796094c5e97f852f31c92ac68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221024/6b84e1e8ba5d47fa8d32d3b91efc650d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80ODU1NzQ5Ng_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221024/b49d626c4b944204baa23ca062de9318.png
[20210202185417422.jpg_pic_center]: /images/20221024/a07ba4e909a14980a9b77f59f2b90b24.png