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

學習數(shù)據(jù)結(jié)構與算法的關鍵在于掌握問題背后的算法思維框架，你的思考越抽象，它能覆蓋的問題域就越廣，理解難度也更復雜。在這個專欄里，小彭與你分享每場 LeetCode 周賽的解題報告，一起體會上分之旅。

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

LeetCode 雙周賽 114

T1. 收集元素的最少操作次數(shù)（Easy）

• 標簽：模擬、散列表

T2. 使數(shù)組為空的最少操作次數(shù)（Medium）

• 標簽：貪心、散列表

T3. 將數(shù)組分割成最多數(shù)目的子數(shù)組（Medium）

• 標簽：思維、位運算

T4. 可以被 K 整除連通塊的最大數(shù)目（Hard）

• 標簽：樹上 DP

---

T1. 收集元素的最少操作次數(shù)（Easy）

https://leetcode.cn/problems/minimum-operations-to-collect-elements/description/

題解（散列表)

簡單模擬題。

預初始化包含 $1?k$ 元素的集合，根據(jù)題意逆向遍歷數(shù)組并從集合中移除元素，當集合為空時表示已經(jīng)收集到所有元素，返回 $n?i$。

class Solution {fun minOperations(nums: List<Int>, k: Int): Int {val n = nums.sizeval set = (1..k).toHashSet()for (i in n - 1 downTo 0) {set.remove(nums[i])if (set.isEmpty()) return n - i}return -1}
}

class Solution:def minOperations(self, nums, k):n, nums_set = len(nums), set(range(1, k+1))for i in range(n-1, -1, -1):nums_set.discard(nums[i])if not nums_set:return n - ireturn -1

class Solution {
public:int minOperations(std::vector<int>& nums, int k) {int n = nums.size();unordered_set<int> set;for (int i = 1; i <= k; ++i) {set.insert(i);}for (int i = n - 1; i >= 0; --i) {set.erase(nums[i]);if (set.empty()) {return n - i;}}return -1;}
};

function minOperations(nums: number[], k: number): number {var n = nums.length;var set = new Set<number>();for (let i = 1; i <= k; ++i) {set.add(i);}for (let i = n - 1; i >= 0; --i) {set.delete(nums[i]);if (set.size === 0) {return n - i;}}return -1;
};

class Solution {int minOperations(List<int> nums, int k) {int n = nums.length;Set<int> set = Set<int>();for (int i = 1; i <= k; i++) {set.add(i);}for (int i = n - 1; i >= 0; i--) {set.remove(nums[i]);if (set.isEmpty) return n - i;}return -1;}
}

復雜度分析：

• 時間復雜度：$O(n)$ 線性遍歷；
• 空間復雜度：$O(k)$ 散列表空間。

---

T2. 使數(shù)組為空的最少操作次數(shù)（Medium）

https://leetcode.cn/problems/minimum-number-of-operations-to-make-array-empty/description/

題解（貪心）

題目兩種操作的前提是數(shù)字相等，因此我們先統(tǒng)計每個元素的出現(xiàn)次數(shù)。

從最少次數(shù)的目標出發(fā)，顯然能移除 $3$ 個就盡量移除 $3$ 個，再分類討論：

• 如果出現(xiàn)次數(shù)為 $1$，那么一定無解，返回 $?1$；
• 如果出現(xiàn)次數(shù)能夠被 $3$ 整除，那么操作 $cnt/3$ 次是最優(yōu)的；
• 如果出現(xiàn)次數(shù)除 $3$ 余 $1$，那么把 $1$ 個 $3$ 拆出來合并為 4，操作 $cnt/3+1$ 次是最優(yōu)的；
• 如果出現(xiàn)次數(shù)除 $3$ 余 $2$，那么剩下的 $2$ 操作 $1$ 次，即操作 $cnt/3+1$ 次是最優(yōu)的。

組合以上討論：

class Solution {fun minOperations(nums: IntArray): Int {val cnts = HashMap<Int, Int>()for (e in nums) {cnts[e] = cnts.getOrDefault(e, 0) + 1}var ret = 0for ((_, cnt) in cnts) {if (cnt == 1) return -1when (cnt % 3) {0 -> {ret += cnt / 3}1, 2 -> {ret += cnt / 3 + 1}}}return ret}
}

繼續(xù)挖掘題目特性，對于余數(shù)大于 $0$ 的情況總是 向上取整 ，那么可以簡化為：

class Solution {fun minOperations(nums: IntArray): Int {val cnts = HashMap<Int, Int>()for (e in nums) {cnts[e] = cnts.getOrDefault(e, 0) + 1}var ret = 0for ((_, cnt) in cnts) {if (cnt == 1) return -1ret += (cnt + 2) / 3 // 向上取整}return ret}
}

class Solution:def minOperations(self, nums: List[int]) -> int:cnts = Counter(nums)ret = 0for cnt in cnts.values():if cnt == 1: return -1ret += (cnt + 2) // 3return ret

class Solution {
public:int minOperations(std::vector<int>& nums) {unordered_map<int, int> cnts;for (auto &e : nums) {cnts[e] += 1;}int ret = 0;for (auto &p: cnts) {if (p.second == 1) return -1;ret += (p.second + 2) / 3;}return ret;}
};

function minOperations(nums: number[]): number {let cnts: Map<number, number> = new Map<number, number>();for (let e of nums) {cnts.set(e, (cnts.get(e) ?? 0) + 1);}let ret = 0;for (let [_, cnt] of cnts) {if (cnt == 1) return -1;ret += Math.ceil(cnt / 3);}return ret;
};

class Solution {int minOperations(List<int> nums) {Map<int, int> cnts = {};for (int e in nums) {cnts[e] = (cnts[e] ?? 0) + 1;}int ret = 0;for (int cnt in cnts.values) {if (cnt == 1) return -1;ret += (cnt + 2) ~/ 3; // 向上取整}return ret;}
}

復雜度分析：

• 時間復雜度：$O(n)$ 線性遍歷
• 空間復雜度：$O(n)$ 計數(shù)空間。

---

T3. 將數(shù)組分割成最多數(shù)目的子數(shù)組（Medium）

https://leetcode.cn/problems/split-array-into-maximum-number-of-subarrays/description/

題解（思維題）

一個重要的結(jié)論是：當按位與的數(shù)量增加時，按位與的結(jié)果是非遞增的。

題目要求在子數(shù)組的按位與的和最小的前提下，讓子數(shù)組的個數(shù)最大。根據(jù)上面的結(jié)論，顯然將數(shù)組全部按位與是最小的。

分類討論：

• 如果整體按位于的結(jié)果不為 $0$，那么就不可能存在分割數(shù)組的方法使得按位與的和更小，直接返回 $1$；
• 否則，問題就變成分割數(shù)組的最大個數(shù)，使得每個子數(shù)組按位與為 $0$，直接貪心分割就好了。

class Solution {fun maxSubarrays(nums: IntArray): Int {val mn = nums.reduce { acc, it -> acc and it }if (mn > 0) return 1 // 特判var ret = 0var cur = Integer.MAX_VALUEfor (i in nums.indices) {cur = cur and nums[i]if (cur == 0) {cur = Integer.MAX_VALUEret++}}return ret }
}

class Solution:def maxSubarrays(self, nums: List[int]) -> int:if reduce(iand, nums): return 1ret, mask = 0, (1 << 20) - 1cur = maskfor num in nums:cur &= numif cur == 0: ret += 1; cur = maskreturn ret

class Solution {
public:int maxSubarrays(vector<int>& nums) {int mn = nums[0];for (auto num : nums) mn &= num;if (mn != 0) return 1;int ret = 0;int cur = INT_MAX;for (int i = 0; i < nums.size(); i++) {cur &= nums[i];if (cur == 0) {cur = INT_MAX;ret++;}}return ret;}
};

function maxSubarrays(nums: number[]): number {const n = nums.length;let mn = nums.reduce((acc, it) => acc & it);if (mn > 0) return 1; // 特判l(wèi)et mask = (1 << 20) - 1let ret = 0;let cur = mask;for (let i = 0; i < n; i++) {cur = cur & nums[i];if (cur === 0) {cur = mask;ret++;}}return ret;
};

class Solution {int maxSubarrays(List<int> nums) {var mn = nums.reduce((acc, it) => acc & it);if (mn > 0) return 1; // 特判var mask = (1 << 20) - 1;var ret = 0;var cur = mask;for (var i = 0; i < nums.length; i++) {cur = cur & nums[i];if (cur == 0) {cur = mask;ret++;}}return ret;}
}

復雜度分析：

• 時間復雜度：$O(n)$ 線性遍歷；
• 空間復雜度：$O(1)$ 僅使用常量級別空間。

---

T4. 可以被 K 整除連通塊的最大數(shù)目（Hard）

https://leetcode.cn/problems/maximum-number-of-k-divisible-components/

問題分析

初步分析：

• 問題目標： 求解分割后滿足條件的最大連通塊數(shù)量；
• 問題條件： 連通塊的和能夠被 K 整除；
• 關鍵信息： 題目保證數(shù)據(jù)是可以分割的，這是重要的前提。

思考實現(xiàn)：

在保證問題有解的情況下，樹上的每個節(jié)點要么是單獨的連通分量，要么與鄰居組成連通分量。那么，這就是典型的「連或不連」和「連哪個」動態(tài)規(guī)劃思維。

• 思考「連或不連」：

如果節(jié)點 $A$ 的價值能夠被 $K$ 整除，那么節(jié)點 $A$ 能作為單獨的連通分量嗎？

不一定，例如 $K=3$ 且樹為 $1?3?5$ 的情況，連通分量只能為 $1$，因為 $3$ 左右子樹都不能構造合法的連通塊，因此需要與 $3$ 連接才行。

• 繼續(xù)思考「連哪個」：

那么，節(jié)點 $A$ 應該與誰相連呢？對于節(jié)點 $A$ 的某個子樹 $Tre{e}_i$ 來說，存在 $2$ 種情況：

• 能整除：那么子樹 $Tre{e}_i$ 不需要和節(jié)點 $A$ 相連；
• 不能整除：那么子樹 $Tre{e}_i$ 的剩余值就必須與節(jié)點 $A$ 相連，有可能湊出 $K$ 的整除。

當節(jié)點 $A$ 與所有子樹的剩余值組合后，再加上當前節(jié)點的價值，如果能夠構造出 $K$ 的整數(shù)倍時，說明找到一個新的連通塊，并且不需要和上一級節(jié)點組合。否則，則進入不能整除的條件，繼續(xù)和上一級節(jié)點組合。

題解（DFS）

• 定義 DFS 函數(shù)并返回兩個數(shù)值：<子樹構造的連通分量, 剩余值>；
• 任意選擇一個節(jié)點為根節(jié)點走一遍 DFS，最終返回 $dfs(0,?1)[0]$。

class Solution {fun maxKDivisibleComponents(n: Int, edges: Array<IntArray>, values: IntArray, k: Int): Int {// 建圖val graph = Array(n) { LinkedList<Int>() }for ((u, v) in edges) {graph[u].add(v)graph[v].add(u)}// DFS <cnt, left>fun dfs(i: Int, pre: Int): IntArray {var ret = intArrayOf(0, values[i])for (to in graph[i]) {if (to == pre) continueval (childCnt, childLeft) = dfs(to, i)ret[0] += childCntret[1] += childLeft}if (ret[1] % k == 0) {ret[0] += 1ret[1] = 0}return ret}return dfs(0, -1)[0]}
}

class Solution:def maxKDivisibleComponents(self, n, edges, values, k):# 建圖graph = defaultdict(list)for u, v in edges:graph[u].append(v)graph[v].append(u)# DFS <cnt, left>def dfs(i, pre):ret = [0, values[i]]for to in graph[i]:if to == pre: continuechildCnt, childLeft = dfs(to, i)ret[0] += childCntret[1] += childLeftif ret[1] % k == 0:ret[0] += 1ret[1] = 0return retreturn dfs(0, -1)[0]

class Solution {
public:int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) {// 建圖vector<list<int>> graph(n);for (auto& edge : edges) {int u = edge[0];int v = edge[1];graph[u].push_back(v);graph[v].push_back(u);}// DFS <cnt, left>function<vector<int>(int, int)> dfs = [&](int i, int pre) -> vector<int> {vector<int> ret(2, 0);ret[1] = values[i];for (int to : graph[i]) {if (to == pre) continue;vector<int> child = dfs(to, i);ret[0] += child[0];ret[1] += child[1];}if (ret[1] % k == 0) {ret[0] += 1;ret[1] = 0;}return ret;};return dfs(0, -1)[0];}
};

function maxKDivisibleComponents(n: number, edges: number[][], values: number[], k: number): number {// 建圖let graph = Array(n).fill(0).map(() => []);for (const [u, v] of edges) {graph[u].push(v);graph[v].push(u);}// DFS <cnt, left>let dfs = (i: number, pre: number): number[] => {let ret = [0, values[i]];for (let to of graph[i]) {if (to === pre) continue;let [childCnt, childLeft] = dfs(to, i);ret[0] += childCnt;ret[1] += childLeft;}if (ret[1] % k === 0) {ret[0] += 1;ret[1] = 0;}return ret;};return dfs(0, -1)[0];  
};

class Solution {int maxKDivisibleComponents(int n, List<List<int>> edges, List<int> values, int k) {// 建圖List<List<int>> graph = List.generate(n, (_) => []);for (final edge in edges) {int u = edge[0];int v = edge[1];graph[u].add(v);graph[v].add(u);}// DFS <cnt, left>List<int> dfs(int i, int pre) {List<int> ret = [0, values[i]];for (int to in graph[i]) {if (to == pre) continue;List<int> child = dfs(to, i);ret[0] += child[0];ret[1] += child[1];}if (ret[1] % k == 0) {ret[0] += 1;ret[1] = 0;}return ret;}return dfs(0, -1)[0];}
}

復雜度分析：

• 時間復雜度：$O(n)$ 每個節(jié)點訪問 $1$ 次；
• 空間復雜度：$O(n)$ 圖空間。

推薦閱讀

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

• LeetCode 單周賽第 364 場 · 前后綴分解結(jié)合單調(diào)棧的貢獻問題
• LeetCode 單周賽第 363 場 · 經(jīng)典二分答案與質(zhì)因數(shù)分解
• LeetCode 雙周賽第 113 場 · 精妙的 O(lgn) 掃描算法與樹上 DP 問題
• LeetCode 雙周賽第 112 場 · 計算機科學本質(zhì)上是數(shù)學嗎？

?? 永遠相信美好的事情即將發(fā)生，歡迎加入小彭的 Android 交流社群~