学习内容

LeeCodeJava

424.替换后最长重复字符

我的代码(参考)

class Solution {
    public int characterReplacement(String s, int k) {
        int[] letters=new int[26];
        int left=0;
        int right=0;
        int maxLetter=0;
        for (right = 0; right < s.length(); right++) {
            //计入字母数量
            letters[s.charAt(right)-'A']++;
            //获得目前最大的字母数量
            maxLetter= Math.max(maxLetter,letters[s.charAt(right)-'A']);
            //计算不合规的字母数量:maxLetter在开始的时候为1了,所以要+1回正
            if(right-left-maxLetter+1>k){
                letters[s.charAt(left)-'A']--;
                left++;
            }
        }
        return right-left;
        //right的最终值会额外加一次1;
    }
}

思路:

将字符串规整为字符,字符数量的集合类.从最小的长度的开始替换,替换的时候从k里面减,减完为止.(抛弃)

题解思路:

使用滑动窗口的思想,从左侧开始找,逐步将整个字符串给获取.
如果发现左指针和右指针之间出现了超过预计的字符数量,就将左指针右移.
每次循环都需要将右指针右移,以尽可能扩大目标字符串的长度.

优解代码

class Solution {
    public int characterReplacement(String s, int k) {
        int[] num = new int[26];
        int n = s.length();
        int maxn = 0;
        int left = 0, right = 0;
        while (right < n) {
            num[s.charAt(right) - 'A']++;
            maxn = Math.max(maxn, num[s.charAt(right) - 'A']);
            while (right - left + 1 - maxn > k) {
                num[s.charAt(left) - 'A']--;
                left++;
            }
            right++;
        }
        return right - left;
    }
}

心得:

其将左端点的移动从if改成了while,注意的情况大概是在最大字符串中的特征字母改变过后,左指针可能需要连续跳过很多字母,如果用if的话,每次左移才能使用一次if,感觉会比较麻烦,其他的思路类似.