LeetCode——替換後的最長重複字元（滑動視窗）

這是我參與8月更文挑戰的第14天，活動詳情檢視： 8月更文挑戰

題目描述

解題思路

核心的解題思路是：滑動視窗。

1. 構造一個數組，該數組擁有26個元素，下标代表的是大寫字母A-Z。

let letterArr = new Array(26).fill(0);
複制代碼      

1. 定義滑動視窗的左右邊界和滑動視窗中出現次數最多的字母的出現次數。

// 定義滑動視窗的左邊界
let left = 0;
// 定義滑動視窗的右邊界
let right = 0;
// 定義滑動視窗中出現次數最多的字母的次數
let max = 0;
複制代碼      

1. 當右邊界小于數組長度的時候，進入循環體，首先判斷滑動視窗右邊界指向的元素的是哪一個字母，然後将對應出現的次數+1，然後更新最大值，如果滑動視窗不滿足條件，則更新左邊界，反之更新右邊界。

while (right < s.length) {
    // 判斷滑動視窗右邊界指向的字母是哪一個字母，對應的将其次數加1
    let sub = s[right].charCodeAt() - 65;
    letterArr[sub]++;
    // 将右邊界指向的字母出現的次數和最大值進行比較更新
    max = Math.max(max, letterArr[sub]);
    // 判斷是更新左邊界還是更新右邊界
    if (right - left + 1 > max + k) {
        // 此時更新左邊界
        letterArr[s[left].charCodeAt() - 65]--;
        left++;
        letterArr[s[right].charCodeAt() - 65]--;
    } else {
        right++;
    }
}
複制代碼      

1. 傳回滑動視窗的長度

return s.length - left;
複制代碼      

AC代碼

var characterReplacement = function (s, k) {
    // 核心思路：滑動視窗
    // 構造所有大寫字母的數組，下标代表元素A-Z，值代表的是在滑動視窗中出現的次數
    let letterArr = new Array(26).fill(0);
    // 定義滑動視窗的左邊界
    let left = 0;
    // 定義滑動視窗的右邊界
    let right = 0;
    // 定義滑動視窗中出現次數最多的字母的次數
    let max = 0;
    while (right < s.length) {
        // 判斷滑動視窗右邊界指向的字母是哪一個字母，對應的将其次數加1
        let sub = s[right].charCodeAt() - 65;
        letterArr[sub]++;
        // 将右邊界指向的字母出現的次數和最大值進行比較更新
        max = Math.max(max, letterArr[sub]);
        // 判斷是更新左邊界還是更新右邊界
        if (right - left + 1 > max + k) {
            // 此時更新左邊界
            letterArr[s[left].charCodeAt() - 65]--;
            left++;
            letterArr[s[right].charCodeAt() - 65]--;
        } else {
            right++;
        }
    }
    return s.length - left;
};
複制代碼      

題目反思

• 學會使用數組的下标和值表示某些元素出現的次數。
• 學會使用滑動視窗解決數組中的替換問題。