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((n))O(\sqrt(n))O((​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+n2⋅M2)O(L + n^2M^2)O(L+n2⋅M2) 构造 $forbiddenSet$ 散列表的时刻杂乱度为 $O(L)$，其间 L 为 forbidden 中一切字符的总长度。枚举子串的个数为 n2n^2n2，而查看子串是否合法的时刻杂乱度是 O(M2)O(M^2)O(M2)，其间 n 是 word 字符串的长度，而 M 是子串的最大长度，M = 10，因而枚举阶段的时刻杂乱度是 O(n2⋅M2)O(n^2M^2)O(n2⋅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⋅M2)O(L + nM^2)O(L+n⋅M2) check 函数最多仅调用 n 次；
• 空间杂乱度：$O(L)$ 散列表空间。

引荐阅读

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

• LeetCode 单周赛第 353 场 看似没考 LIS 最长递增子序列，如同又考了
• LeetCode 单周赛第 350 场 滑动窗口与离散化模板题
• LeetCode 双周赛第 107 场 很有意思的 T2 题
• LeetCode 双周赛第 104 场 流水的动态规划，铁打的结构化考虑

⭐️ 永远信任夸姣的工作即将产生，欢迎加入小彭的 Android 交流社群~