标签搜索

目 录CONTENT

文章目录

力扣--替换后的最长重复字符.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 3 阅读 / 1,142 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

力扣--替换后的最长重复字符

@[toc]

一、题目描述

在这里插入图片描述
在这里插入图片描述

二、分析

  •  题目的意思比较清楚,不过可能的情况有很多,不可能用代码去寻找最佳的替换位置,所以这里采用一种滑动窗口的方法
  •  定义start和end两个标记,中间的内容即是窗口,计算窗口内所有字母出现的次数,因为全是大写字母,所以可以用一个26位的数组来记录窗口内每个字母出现的次数
  •  找到窗口内出现最多的次数,加上允许替换的字母数k,看是否超过窗口宽度,如果超过了,说明窗口还可以更长, 也就是说窗口内重复的字母的长度可以更长,就将end右移一位,形成新的窗口,然后继续重复上面的步骤。
  •  如果没超过,说明能构成的最长的重复字母长度已经到顶了,这时应该将start右移一位,来寻找新的可能的更长重复字母长度。
  •  每次计算重复字母长度时,当出现更长的可能时,都更新最终的结果。
  •  为了减少时间复杂度,我们不去每次都遍历窗口来计算出现的字母次数,而是在移动end或者start时,将对应位置的字母的次数加一或者减一。
  •  这道题和:美团--最长全1串字节--字符串翻转类似

三、代码

class Solution {
public:
    int characterReplacement(string s, int k) {
        if (s.length() < 1) 
            return 0;
        //开始和结束区间
        int start = 0;
        int end = 0;

        //保存结果
        int res = 0;

        //把第一个字符先放到数组当中
        int charNum[26] = {0};
        charNum[s[0] - 'A']++;
        while (s.length() > end) 
        {
            //标记在left和right区间内出现次数最多的字符
            int maxChar = 0;
            //找在left和right区间内出现次数最多的字符
            for (int i = 0; i < 26; i++) 
            {
                if (charNum[i] > maxChar)
                    maxChar = charNum[i];
            }

            //如果maxChar+可操作的次数k大于区间的长度,说明还有操作的空间
            //继续++right
            if (maxChar + k > end - start) 
            {
                end++;
                if (end < s.length())
                   charNum[s[end] - 'A']++;
            } 
            //反之就是虽然在left和right区间内找到最多的字符,但是其小于区间的长度
            //需要右移left
            else 
            {
                charNum[s[start] - 'A']--;
                 start++;
             }
             //每次都要更新结果
             if (maxChar + k > res)
                 res = maxChar + k <= s.length() ? maxChar + k : s.length();
         }
         return res;
    }
};
0

评论区