LeetCode 周賽上分之旅 #33 摩爾投票派上用場

⭐️ 本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 和 [BaguTree Pro] 知識星球提問。

學習資料結構與演演算法的關鍵在於掌握問題背後的演演算法思維框架，你的思考越抽象，它能覆蓋的問題域就越廣，理解難度也更復雜。在這個專欄裡，小彭與你分享每場 LeetCode 周賽的解題報告，一起體會上分之旅。

本文是 LeetCode 上分之旅系列的第 33 篇文章，往期回顧請移步到文章末尾~

周賽 354

T1. 特殊元素平方和（Easy）

標籤：模擬、數學

T2. 陣列的最大美麗值（Medium）

標籤：排序、二分查詢、同向雙指標

T3. 合法分割的最小下標（Medium）

標籤：數學、前字尾分解

T4. 最長合法子字串的長度（Hard）

標籤：同向雙指標

T1. 特殊元素平方和（Easy）

https://leetcode.cn/problems/sum-of-squares-of-special-elements/

題解一（模擬）

簡單模擬題，列舉每個下標檢查是否能被 n 整除，同時記錄結果。

class Solution {
public:
    int sumOfSquares(vector<int>& nums) {
        int ret = 0;
        int n = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            if (n % (i + 1) == 0) ret += nums[i] * nums[i];
        }
        return ret;
    }
};

複雜度分析：

時間複雜度：$O(n)$
空間複雜度：$O(1)$

題解二（模擬 + 優化）

事實上，當下標 i 可以被 n 整除時，那麼有下標 n / i 也可以被 n 整除，因此我們只需要檢查 [0, \sqrt(n)] 的範圍。

1、將 nums[0] 和 nums[n - 1] 的平方值新增到結果中（如果陣列長度不大於 1，則不需要新增 nums[n - 1] 的影響）；
2、從 2 到 sqrt(n) 的範圍內遍歷所有元素下標 i，如果 n 能夠被 i 整除，那麼我們將 nums[i-1] 的平方值和 nums[n/i-1] 的平方值分別新增到結果中（如果 i 和 n/i 相等，我們只新增其中一個值，以避免重複）；

class Solution {
public:
    int sumOfSquares(vector<int>& nums) {
        int ret = nums[0] * nums[0];
        int n = nums.size();
        if (n < 2) return ret;
        ret += nums[n - 1] * nums[n - 1];
        for (int i = 2; i <= sqrt(n); i++) {
            if (n % i != 0) continue;
            ret += nums[i - 1] * nums[i - 1];
            if (i != n / i) {
                ret += nums[n / i - 1] * nums[n / i - 1];
            }
        }
        return ret;
    }
};

複雜度分析：

時間複雜度：$O(\sqrt(n))$
空間複雜度：$O(1)$

其他語言解法見 LeetCode 題解頁：列舉優化的 O(sqrt(n) 時間解法（C++/Python/Kotlin）

T2. 陣列的最大美麗值（Medium）

https://leetcode.cn/problems/maximum-beauty-of-an-array-after-applying-operation/

題解一（排序 + 二分查詢）

根據題目操作描述，每個元素都可以修改為範圍在 [nums[i] - k, nums[i] + k] 之間的任意元素，我們把兩個元素的差視為元素的相似度，那麼差值小於 2*k 的兩個數就能夠轉換為相等數（增大較小數，同時減小較大數）。

由於美麗值和陣列順序無關，我們先對陣列排序，然後列舉元素作為左值，再尋找最遠可匹配的右值（nums[i] + 2 * k），可以使用二分查詢尋找不大於右值的最大元素。

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ret = 0;
        for (int i = 0; i < nums.size(); i++) {
            int left = i;
            int right = nums.size() - 1;
            while (left < right) {
                int mid = (left + right + 1) / 2;
                if (nums[mid] > nums[i] + 2 * k) {
                    right = mid - 1;
                } else {
                    left = mid;
                }
            }
            ret = max(ret, left - i + 1);
        }
        return ret;
    }
};

複雜度分析：

時間複雜度：$O(nlgn)$ 瓶頸在排序，模擬時間為 $O(nlgn)$；
空間複雜度：$O(lgn)$ 瓶頸在排序。

題解二（排序 + 同向雙指標）

根據題目操作描述，每個元素都可以修改為範圍在 [nums[i] - k, nums[i] + k] 之間的任意元素，我們把這個範圍視為一個可選區間。那麼問題的最大美麗值正好就是所有區間的最多重疊數，這就是經典的 leetcode 253. 會議室 II 問題

由於區間重疊數和順序無關，我們可以對所有元素排序（由於區間長度相等，等價於按照結束時間排序），使用同向雙指標求解：

維護重疊區間的左右指標 i 和 j
如果當前區間 [j] 與左指標指向的區間不重疊，則將左指標 i 向右移動，並記錄最大重疊數

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int i = 0;
        int ret = 0;
        for (int j = 0; j < nums.size(); j++) {
            while (nums[j] - k > nums[i] + k) i++;
            ret = max(ret, j - i + 1);
        }
        return ret;
    }
};

複雜度分析：

時間複雜度：$O(nlgn)$ 瓶頸在排序，同向雙指標模擬時間為 $O(n)$；
空間複雜度：$O(lgn)$ 瓶頸在排序。

其他語言解法見 LeetCode 題解頁：會議室問題求最大重疊區間數、同向雙指標（C++/Python/Kotlin/TypeScript）

T3. 合法分割的最小下標（Medium）

https://leetcode.cn/problems/minimum-index-of-a-valid-split/

題解一（數學 + 前字尾分解）

根據題目描述，支配元素是指陣列中的眾數，同時要求出現次數嚴格大於陣列一半長度，所以支配元素可能是 -1。其實，支配元素的定義與經典題目 169. 多數元素和劍指 Offer 39. 陣列中出現次數超過一半的數位定義是相同的。

容易證明，無論陣列如何分割，子陣列的支配元素要麼不存在，要麼就等於原陣列的支配元素：

假設 cnt1 是左子陣列的支配元素，cnt2 是右子陣列的支配元素，那麼右 cnt1 * 2 > len1 且 cnt2 * 2 > len2；
由於兩個子陣列的支配元素相同，且滿足兩式相加右 (cnt1 + cnt2) * 2 > (len1 + len2)，說明子陣列的支配元素與原陣列相同。

因此，我們的演演算法是：

計算原陣列的支配元素
並從左到右列舉分割點，並記錄支配元素在左右子陣列中的個數，當左右子陣列中支配元素的數量條件成立時，返回下標。

class Solution {
public:
    int minimumIndex(vector<int>& nums) {
        // 計算支配元素
        unordered_map<int, int> cnts;
        int x = -1;
        for (int i = 0; i < nums.size(); i++) {
            ++cnts[nums[i]];
            if (x == -1 || cnts[nums[i]] > cnts[x]) {
                x = nums[i];
            }
        }
        // 列舉分割點
        int leftXCnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != x) continue;
            leftXCnt++;
            if (leftXCnt * 2 > i + 1 && (cnts[x] - leftXCnt) * 2 > nums.size() - 1 - i) return i;
        }
        return -1;
    }
};

複雜度分析：

時間複雜度：$O(n)$ 求支配元素和列舉分割點的時間複雜度都是 $O(n)$；
空間複雜度：$O(n)$ 雜湊表空間。

題解二（摩爾投票優化）

題解一中使用雜湊表求原陣列的支配元素，可以使用摩爾投票演演算法來優化空間複雜度：

我們將眾數的權重視為 +1，把其他數視為 -1。
首先我們維護一個候選數，然後遍歷陣列的每個元素，如果 count == 0，說明它在當前的權重最大，那麼將它記為 candidate，對於接下來的元素，如果它等於 candidate，則 count ++，否則 count--。
最終得到的 candidate 就是眾數。

class Solution {
public:
    int minimumIndex(vector<int>& nums) {
        // 計算支配數
        int x = -1;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (0 == count) x = nums[i];
            if (nums[i] == x) count++; else count --;
        }
        // 計算支配數出現次數
        int total = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == x) total ++;
        }
        // 列舉分割點
        int leftXCnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != x) continue;
            leftXCnt++;
            if (leftXCnt * 2 > i + 1 && (total - leftXCnt) * 2 > nums.size() - 1 - i) return i;
        }
        return -1;
    }
};

複雜度分析：

時間複雜度：$O(n)$ 求支配元素和列舉分割點的時間複雜度都是 $O(n)$；
空間複雜度：$O(1)$ 僅使用常數級別空間。

其他語言解法見 LeetCode 題解頁：數學、前字尾分解、摩爾投票 O(1) 空間（C++/Python/Kotlin）

T4. 最長合法子字串的長度（Hard）

https://leetcode.cn/problems/length-of-the-longest-valid-substring/

題解一（暴力列舉子串· 超出時間限制）

這道題中 forbidden[i] 字串的長度不超過 10，說明檢查字串匹配的時間常數是比較低的，我們先考慮暴力的解法。

使用同向雙指標 i 和 j 列舉子串，並檢查該子串是否合法；
由於在記憶體迴圈中移動 j 指標只是在 [i, j - 1] 的基礎上增加字元 nums[j]，所以在檢查的時候僅需要檢查 [i, j] 範圍中，以 nums[j] 為結尾的子字串是否被禁用。同時，由於 forbidden[i] 的最大長度為 10，所以在檢查時只需要檢查長度不超過 10 的子串。

class Solution {
    fun longestValidSubstring(word: String, forbidden: List<String>): Int {
        val forbiddenSet = forbidden.toHashSet()
        var ret = 0
        for (i in 0 until word.length) {
            for (j in i until word.length) {
                if (!check(forbiddenSet, word, i, j)) break // 後續子串不可能合法
                ret = Math.max(ret, j - i + 1)
            }
        }
        return ret
    }

    // return：是否合法
    private fun check(set: Set<String>, word: String, i: Int, j: Int): Boolean {
        // 檢查 [i,j] 中以新增字母 nums[j] 為右端點的所有子串方案是否被禁用
        for (k in j downTo i) {
            val key = word.substring(k, j + 1)
            if (set.contains(key)) return false
        }
        return true
    }
}

複雜度分析：

時間複雜度：$O(L + n^2·M2)$ 構造 $forbiddenSet$ 雜湊表的時間複雜度為 $O(L)$，其中 L 為 forbidden 中所有字元的總長度。列舉子串的個數為 $n^2$，而檢查子串是否合法的時間複雜度是 $O(M^2)$，其中 n 是 word 字串的長度，而 M 是子串的最大長度，M = 10，因此列舉階段的時間複雜度是 $O(n^2·M2)$。
空間複雜度：$O(L)$ 雜湊表空間。

提示：我們可以使用捲動雜湊優化 check 的時間複雜度到 O(M)，但由於 M 本身很小，優化效果不高。

題解二（同向雙指標）

這道題需要結合 KMP 思想。

題解一中的 check 會重複計算多次子串，需要想辦法剪枝：

由於我們是求最長子串，所以 [i + 1, j] 的結果不會由於 [i, j] 的結果。這說明了，如果 [i, j] 中存在不合法的子串，那麼移動 i 指標 + 1 後再去重新列舉 j 指標，不可能獲得更優解，完全沒有必要列舉 i 指標，只需要在 [i, j] 不合法的時候移動 i 指標 + 1；
同時，在 check 函數中最早出現的非法子串位置，可以加快收縮 i 指標，直接將 i 指標指向最早出現的非法子串位置 + 1。

class Solution {
    fun longestValidSubstring(word: String, forbidden: List<String>): Int {
        // word = "leetcode", forbidden = ["de","le","e"]
        val forbiddenSet = forbidden.toHashSet()
        var ret = 0
        var i = 0
        for (j in 0 until word.length) {
            // 不合法
            while (true) {
                val pivot = check(forbiddenSet, word, i, j)
                if (-1 != pivot) i = pivot + 1 else break
            }
            ret = Math.max(ret, j - i + 1)
        }
        return ret
    }

    // return：最早的非法子串的起始位置
    private fun check(set: Set<String>, word: String, i: Int, j: Int): Int {
        // 檢查 [i,j] 中以新增字母 nums[j] 為右端點的所有子串方案是否被禁用
        for (k in Math.max(i, j - 10) .. j) {
            val key = word.substring(k, j + 1)
            if (set.contains(key)) return k
        }
        return -1
    }
}

複雜度分析：

時間複雜度：$O(L + n·M^2)$ check 函數最多僅呼叫 n 次；
空間複雜度：$O(L)$ 雜湊表空間。

推薦閱讀

LeetCode 上分之旅系列往期回顧：

LeetCode 單週賽第 353 場 · 看似沒考 LIS 最長遞增子序列，好像又考了

LeetCode 單週賽第 350 場 · 滑動視窗與離散化模板題

LeetCode 雙週賽第 107 場 · 很有意思的 T2 題

LeetCode 雙週賽第 104 場 · 流水的動態規劃，鐵打的結構化思考

⭐️ 永遠相信美好的事情即將發生，歡迎加入小彭的 Android 交流社群~