424. 替换后的最长重复字符
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 *k *次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意:
字符串长度 和 *k *不会超过 104。
示例 1:
输入:
s = "ABAB", k = 2
输出:
4
解释:
用两个'A'替换为两个'B',反之亦然。
示例 2:
输入:
s = "AABABBA", k = 1
输出:
4
解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
滑动窗口示意
整体思路
初始窗口的宽度为1，不断的通过向当前窗口覆盖的子串后面追加一个字符看是否能够满足我们的条件，如果满足，则窗口扩张，如果不满足，则将窗口向右滑动。当窗口触达字符串末尾字符时，运算结束，窗口的宽度即为最终结果。
- 条件：当前字符串出现次数最多的字母个数+K要大于串的长度。
- 窗口扩张：left不变，right++
- 窗口滑动：left++, right++
用historyCharMax保存滑动窗口内相同字母出现次数的历史最大值，通过判断historyCharMax + K是否大于窗口宽度(right - left + 1)来决定窗口是滑动还是扩张,如果大于，则扩张窗口，如果小于，则滑动窗口。
class Solution {
int[] map = new int[26];
public int characterReplacement(String s, int k) {
int left = 0;
int right = 0;
int historyMax = 0;
// 当前右边界在map中的索引
int index = 0;
char[] chars = s.toCharArray();
for (right = 0; right < s.length(); right++) {
index = chars[right] - 'A';
// 给当前字母+1
map[index]++;
// 统计当前出现次数最多的字母
historyMax = Math.max(historyMax, map[index]);
// 如果当前出现次数最多的字母+k比窗口宽度小则滑动窗口
if (historyMax + k < right - left + 1) {
// 对应左边界的字符-1
map[chars[left] - 'A']--;
left++;
}
}
return right - left;
}
}
1004. 最大连续1的个数 III
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。
示例 1：
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
提示：
1 <= A.length <= 200000 <= K <= A.length-
A[i]为0或1
整体思路
这题和上一题的思路差不多。我们设定初始窗口的宽度为1，然后再进行窗口扩张，如果当前窗口内的1的数量加上k比窗口宽度大，则扩张窗口，否则移动窗口。
class Solution {
public int longestOnes(int[] A, int K) {
if (A.length == 0) {
return 0;
}
int left = 0;
int right = 0;
// 统计1的个数
int oneNum = 0;
// 当前窗口内1的最大个数
int maxCount = 0;
for (right = 0; right < A.length; right++) {
if (A[right] == 1) {
oneNum++;
}
maxCount = Math.max(maxCount, oneNum);
// 窗口滑动
if (maxCount + K < right - left + 1) {
if (A[left] == 1) {
oneNum--;
}
left++;
}
}
return right - left;
}
}
