周賽 354
T1. 特殊元素平方和（Easy）
- 標(biāo)簽：模擬、數(shù)學(xué)
T2. 數(shù)組的最大美麗值（Medium）
- 標(biāo)簽：排序耕餐、二分查找、同向雙指針
T3. 合法分割的最小下標(biāo)（Medium）
- 標(biāo)簽：數(shù)學(xué)辟狈、前后綴分解
T4. 最長合法子字符串的長度（Hard）
- 標(biāo)簽：同向雙指針
T1. 特殊元素平方和（Easy）
https://leetcode.cn/problems/sum-of-squares-of-special-elements/
題解一（模擬）
簡單模擬題肠缔，枚舉每個下標(biāo)檢查是否能被 n 整除夏跷，同時記錄結(jié)果。
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;
}
};
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
題解二（模擬 + 優(yōu)化）
事實上明未，當(dāng)下標(biāo) i 可以被 n 整除時槽华，那么有下標(biāo) n / i 也可以被 n 整除，因此我們只需要檢查 [0, \sqrt(n)] 的范圍趟妥。
- 1猫态、將 nums[0] 和 nums[n - 1] 的平方值添加到結(jié)果中（如果數(shù)組長度不大于 1，則不需要添加 nums[n - 1] 的影響）煮纵；
- 2懂鸵、從 2 到 sqrt(n) 的范圍內(nèi)遍歷所有元素下標(biāo) i，如果 n 能夠被 i 整除行疏，那么我們將 nums[i-1] 的平方值和 nums[n/i-1] 的平方值分別添加到結(jié)果中（如果 i 和 n/i 相等匆光，我們只添加其中一個值，以避免重復(fù)）酿联；
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;
}
};
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
其他語言解法見 LeetCode 題解頁：枚舉優(yōu)化的 O(sqrt(n) 時間解法（C++/Python/Kotlin）
T2. 數(shù)組的最大美麗值（Medium）
https://leetcode.cn/problems/maximum-beauty-of-an-array-after-applying-operation/
題解一（排序 + 二分查找）
根據(jù)題目操作描述终息，每個元素都可以修改為范圍在 [nums[i] - k, nums[i] + k] 之間的任意元素，我們把兩個元素的差視為元素的相似度贞让，那么差值小于 2*k 的兩個數(shù)就能夠轉(zhuǎn)換為相等數(shù)（增大較小數(shù)周崭，同時減小較大數(shù)）。
由于美麗值和數(shù)組順序無關(guān)喳张，我們先對數(shù)組排序续镇，然后枚舉元素作為左值，再尋找最遠(yuǎn)可匹配的右值（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;
}
};
復(fù)雜度分析：
- 時間復(fù)雜度：
瓶頸在排序，模擬時間為
- 空間復(fù)雜度：
瓶頸在排序酱虎。
題解二（排序 + 同向雙指針）
根據(jù)題目操作描述，每個元素都可以修改為范圍在 [nums[i] - k, nums[i] + k] 之間的任意元素擂涛，我們把這個范圍視為一個可選區(qū)間读串。那么問題的最大美麗值正好就是所有區(qū)間的最多重疊數(shù)，這就是經(jīng)典的 leetcode 253. 會議室 II 問題
由于區(qū)間重疊數(shù)和順序無關(guān)撒妈，我們可以對所有元素排序（由于區(qū)間長度相等恢暖，等價于按照結(jié)束時間排序），使用同向雙指針求解：
- 維護重疊區(qū)間的左右指針 i 和 j
- 如果當(dāng)前區(qū)間 [j] 與左指針指向的區(qū)間不重疊踩身，則將左指針 i 向右移動胀茵，并記錄最大重疊數(shù)
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;
}
};
復(fù)雜度分析：
- 時間復(fù)雜度：
挟阻；
- 空間復(fù)雜度：
其他語言解法見 LeetCode 題解頁：會議室問題求最大重疊區(qū)間數(shù)、同向雙指針（C++/Python/Kotlin/TypeScript）
T3. 合法分割的最小下標(biāo)（Medium）
https://leetcode.cn/problems/minimum-index-of-a-valid-split/
題解一（數(shù)學(xué) + 前后綴分解）
根據(jù)題目描述附鸽，支配元素是指數(shù)組中的眾數(shù)脱拼，同時要求出現(xiàn)次數(shù)嚴(yán)格大于數(shù)組一半長度，所以支配元素可能是 -1坷备。其實熄浓，支配元素的定義與經(jīng)典題目 169. 多數(shù)元素 和 劍指 Offer 39. 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字 定義是相同的。
容易證明省撑，無論數(shù)組如何分割赌蔑，子數(shù)組的支配元素要么不存在，要么就等于原數(shù)組的支配元素：
- 假設(shè) cnt1 是左子數(shù)組的支配元素竟秫，cnt2 是右子數(shù)組的支配元素娃惯，那么右 cnt1 * 2 > len1 且 cnt2 * 2 > len2；
- 由于兩個子數(shù)組的支配元素相同肥败，且滿足兩式相加右 (cnt1 + cnt2) * 2 > (len1 + len2)趾浅，說明子數(shù)組的支配元素與原數(shù)組相同。
因此馒稍，我們的算法是：
- 計算原數(shù)組的支配元素
- 并從左到右枚舉分割點皿哨，并記錄支配元素在左右子數(shù)組中的個數(shù)，當(dāng)左右子數(shù)組中支配元素的數(shù)量條件成立時纽谒，返回下標(biāo)证膨。
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;
}
};
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
題解二（摩爾投票優(yōu)化）
題解一中使用散列表求原數(shù)組的支配元素央勒，可以使用摩爾投票算法來優(yōu)化空間復(fù)雜度：
- 我們將眾數(shù)的權(quán)重視為 +1，把其他數(shù)視為 -1请祖。
- 首先我們維護一個候選數(shù) 订歪，然后遍歷數(shù)組的每個元素，如果 count == 0肆捕，說明它在當(dāng)前的權(quán)重最大刷晋，那么將它記為 candidate，對于接下來的元素慎陵，如果它等于 candidate眼虱，則 count ++，否則 count--席纽。
- 最終得到的 candidate 就是眾數(shù)捏悬。
class Solution {
public:
int minimumIndex(vector<int>& nums) {
// 計算支配數(shù)
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 --;
}
// 計算支配數(shù)出現(xiàn)次數(shù)
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;
}
};
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
僅使用常量級別空間润梯。
其他語言解法見 LeetCode 題解頁：數(shù)學(xué)过牙、前后綴分解甥厦、摩爾投票 O(1) 空間（C++/Python/Kotlin）
T4. 最長合法子字符串的長度（Hard）
https://leetcode.cn/problems/length-of-the-longest-valid-substring/
題解一（暴力枚舉子串· 超出時間限制）
這道題中 forbidden[i] 字符串的長度不超過 10，說明檢查字符串匹配的時間常數(shù)是比較低的寇钉，我們先考慮暴力的解法刀疙。
- 使用同向雙指針 i 和 j 枚舉子串，并檢查該子串是否合法扫倡；
- 由于在內(nèi)存循環(huán)中移動 j 指針只是在 [i, j - 1] 的基礎(chǔ)上增加字符 nums[j]谦秧，所以在檢查的時候僅需要檢查 [i, j] 范圍中，以 nums[j] 為結(jié)尾的子字符串是否被禁用撵溃。同時疚鲤，由于 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 // 后續(xù)子串不可能合法
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
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
構(gòu)造
散列表的時間復(fù)雜度為
集歇，其中 L 為 forbidden 中所有字符的總長度。枚舉子串的個數(shù)為
卖哎，而檢查子串是否合法的時間復(fù)雜度是
鬼悠，其中 n 是 word 字符串的長度，而 M 是子串的最大長度亏娜，M = 10焕窝，因此枚舉階段的時間復(fù)雜度是
。
- 空間復(fù)雜度：
提示：我們可以使用滾動哈希優(yōu)化 check 的時間復(fù)雜度到 O(M)它掂，但由于 M 本身很小，優(yōu)化效果不高溯泣。
題解二（同向雙指針）
這道題需要結(jié)合 KMP 思想虐秋。
題解一中的 check 會重復(fù)計算多次子串，需要想辦法剪枝：
- 由于我們是求最長子串垃沦，所以 [i + 1, j] 的結(jié)果不會由于 [i, j] 的結(jié)果客给。這說明了，如果 [i, j] 中存在不合法的子串肢簿，那么移動 i 指針 + 1 后再去重新枚舉 j 指針靶剑，不可能獲得更優(yōu)解，完全沒有必要枚舉 i 指針池充，只需要在 [i, j] 不合法的時候移動 i 指針 + 1桩引；
- 同時，在 check 函數(shù)中最早出現(xiàn)的非法子串位置收夸，可以加快收縮 i 指針坑匠，直接將 i 指針指向最早出現(xiàn)的非法子串位置 + 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
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
check 函數(shù)最多僅調(diào)用 n 次卧惜；
- 空間復(fù)雜度：
推薦閱讀
LeetCode 上分之旅系列往期回顧：
