目錄
- 424. 替換后的最長重復字符
- 思考分析1
- 優化
- 1004. 最大連續1的個數 III
- 友情提醒
- 方法1，基于當前最大頻數
- 方法2，基于歷史最大頻數
424. 替換后的最長重復字符
https://leetcode-cn.com/problems/longest-repeating-character-replacement/
給你一個僅由大寫英文字母組成的字符串，你可以將任意位置上的字符替換成另外的字符，總共可最多替換 k 次。在執行上述操作后，找到包含重復字母的最長子串的長度。
注意:
字符串長度 和 k 不會超過 10^4。
示例 1:
輸入:
s = “ABAB”, k = 2
輸出:
4
解釋:
用兩個’A’替換為兩個’B’,反之亦然。
示例 2:
輸入:
s = “AABABBA”, k = 1
輸出:
4
解釋:
將中間的一個’A’替換為’B’,字符串變為 “AABBBBA”。
子串 “BBBB” 有最長重復字母, 答案為 4。
思考分析1
需要注意的地方：
1、何時擴充窗口？
當子串符合要求，向右擴充一位。（貪心思想，滿足了要求還要繼續膨脹）
2、子串達成什么條件能說明符合要求？
如果最大頻數 + k >= 當前窗口長度，(也就是說經過k此修改，我們可以將不是出現次數最多的元素修改為頻數最高元素，從而變為重復串，并且這個串的長度是大于此時窗口長度的)那么我們認為是符合條件的，此時更新窗口長度，取歷史窗口長度與當前窗口長度的較大值
3、什么時候滑動窗口
當子串不滿足條件的時候，窗口整體向右滑動一位，窗口長度不會減少。
class Solution {
public:int characterReplacement(string s, int k) {int left = 0, right = 0;//當前窗口中元素的最高頻數int now_max_freq = 0;int hash_map[26] ={0};//窗口長度最大值int max_window_length = 0;while(right < s.size()){//新加入窗口的元素char c = s[right];//窗口內這個元素對應的頻數+1hash_map[c - 'A']++;//找到整個窗口內最大頻數for(int i = 0; i < 26; i++)now_max_freq = max(now_max_freq,hash_map[i]);//如果最大頻數 + k >= 當前窗口長度，那么我們認為是符合條件的，此時更新窗口長度，取歷史窗口長度與當前窗口長度的較大值if(now_max_freq + k >= right - left + 1){max_window_length = max(max_window_length,right - left + 1);}//如果不滿足整個條件，我們需要將整個窗口平移else{char d = s[left];hash_map[d - 'A']--;left++;}right++;}return max_window_length;}
};
優化
關于優化，首先得知道一點就是我們之前更新窗口長度的條件：
1、先找這個窗口內的最大頻數
2、如果這個頻數 + k >= 當前窗口長度，我們選擇更新窗口長度
由于在尋找最大頻數的時候有個比較過程，并且每次新進來一個字符我們就得重新比較26次。（我們可以優化比較，例如加入備忘錄什么的）。但這里我們不需要這樣做。
我們只需要找到“歷史窗口內元素出現最大頻數”，然后觀察這個頻數 + k 是否 >= 當前窗口長度。
由于這道題目要求求解的是最長重復子串，如果當前窗口最大字符重復個數小于歷史窗口的最大字符重復個數，完全可以將此窗口忽略掉，因為它必然不可能是最長重復子串。只有當歷史窗口的最大字符重復個數更新時，其最大長度才會進行相應的更新。
現在我們將上面的代碼稍作修改，改成如下代碼：
class Solution {
public:int characterReplacement(string s, int k) {int left = 0, right = 0;//歷史最大頻數int history_max_freq = 0;int hash_map[26] ={0};int max_window_length = 0;while(right < s.size()){//新加入窗口的元素char c = s[right];hash_map[c - 'A']++;//觀察整個元素是不是窗口內出現次數最多的元素，如果是更新history值history_max_freq = max(history_max_freq,hash_map[c - 'A']);if(history_max_freq + k >= right - left + 1){max_window_length = max(max_window_length,right - left + 1);}else{char d = s[left];//窗口左移，被移除的元素在窗口內頻數-1hash_map[d - 'A']--;left++;}right++;}return max_window_length;}
};
兩種解法性能相差挺大的。
下面一題和本題幾乎一模一樣，甚至是簡化，我們也同樣用兩種思路來做吧。
1004. 最大連續1的個數 III
https://leetcode-cn.com/problems/max-consecutive-ones-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。
友情提醒
由于這一題的簡化性，最好好好看看兩者代碼有何區別，不然以為是一樣的。(其實性能應該差不多，因為這里在找當前最大頻數的時候不需要比較26次了，只需要一次。)
方法1，基于當前最大頻數
class Solution {
public:int longestOnes(vector<int>& A, int K) {int left = 0, right = 0;int one_times = 0;int now_max_freq = 0;int max_window_length = 0;while(right < A.size()){int c = A[right];if(c == 1) one_times++;if(one_times + K >= right - left + 1){max_window_length = max(max_window_length,right - left + 1);}else{int d = A[left];if(d == 1) one_times--;left++;}right++;}return max_window_length;}
};
方法2，基于歷史最大頻數
class Solution {
public:int longestOnes(vector<int>& A, int K) {int left = 0, right = 0;int one_times = 0;int history_max_freq = 0;int max_window_length = 0;while(right < A.size()){int c = A[right];if(c == 1) one_times++;history_max_freq = max(history_max_freq,one_times);if(history_max_freq + K >= right - left + 1){max_window_length = max(max_window_length,right - left + 1);}else{int d = A[left];if(d == 1) one_times--;left++;}right++;}return max_window_length;}
};
)
