LeetCode 周赛上分之旅 #33 摩尔投票派上用场

leetcode,摩尔,投票,派上用场 · 浏览次数 : 115

小编点评

**题解一** * 使用双向指针 i 和 j 枚举子串。 * 检查每个子串是否在禁止字符集合中。 * 若子串合法，更新答案。 * 最终返回最长合法子串的长度。 **题解二** * 使用摩尔投票优化空间复杂度。 * 维护一个候选数，记录当前权重最大元素的索引。 * 遍历数组，如果当前元素与候选数相同，则更新候选数。 * 最终，候选数就是众数。 **复杂度分析** **题解一** * 时间复杂度：$O(n)$，其中 n 是字符串长度。 * 空间复杂度：$O(1)$。 **题解二** * 时间复杂度：$O(L + n^2 \cdot M^2)$，其中 L 是禁止字符集的大小，n 是字符串长度，M 是子串的最大长度。 * 其中： * L 是 O(L) 的计算时间。 * n^2 是枚举子串的次数。 * M^2 是检查子串是否合法所需的时间。 **空间复杂度分析** **题解二** * 散列表空间复杂度为 O(L)。

正文

⭐️ 本文已收录到 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 交流社群~