LeetCode 周賽上分之旅 #35 兩題坐牢，菜雞現出原形
⭐️ 本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 和 [BaguTree Pro] 知識星球提問。
學習資料結構與演演算法的關鍵在於掌握問題背後的演演算法思維框架，你的思考越抽象，它能覆蓋的問題域就越廣，理解難度也更復雜。在這個專欄裡，小彭與你分享每場 LeetCode 周賽的解題報告，一起體會上分之旅。
本文是 LeetCode 上分之旅系列的第 35 篇文章，往期回顧請移步到文章末尾~
T1. 按分隔符拆分字串（Easy）
- 標籤：模擬
T2. 合併後陣列中的最大元素（Medium）
- 標籤：貪心
T3. 長度遞增組的最大數目（Hard）
- 標籤：排序、貪心
T4. 樹中可以形成迴文的路徑數（Hard）
- 標籤：狀態壓縮、字首和、雜湊表
T1. 按分隔符拆分字串（Easy）
https://leetcode.cn/problems/split-strings-by-separator/
題解（模擬）
簡單模擬題。
class Solution:
def splitWordsBySeparator(self, words: List[str], separator: str) -> List[str]:
ans = []
for x in words:
for y in x.split(separator):
if y != "":
ans.append(y)
return ans
複雜度分析：
- 時間複雜度：$O(L)$ 其中 $L$ 為字元總數；
- 空間複雜度：$O(1)$ 不考慮結果陣列，僅佔用常數級別空間。
T2. 合併後陣列中的最大元素（Medium）
https://leetcode.cn/problems/largest-element-in-an-array-after-merge-operations/
題解（貪心）
由於題目操作的前提是 nums[i] ≤ nums[i + 1]，因此我們可以優先合併靠後的相鄰序列，這樣可以保證靠前的更多數能夠被合併。如果中間出現 nums[i] 不小於 nums[i + 1] 的情況，說明遇到一個較大的數，它的權重大於後續陣列的合併，我們則直接使用這個較大的數。
class Solution:
def maxArrayValue(self, nums: List[int]) -> int:
for i in range(len(nums) - 2, -1, -1):
if (nums[i] <= nums[i + 1]): nums[i] += nums[i + 1]
return nums[0]
class Solution {
fun maxArrayValue(nums: IntArray): Long {
val n = nums.size
var ret = Long.MIN_VALUE
for (i in n - 1 downTo 0) {
if (ret >= nums[i]) {
ret += nums[i]
} else {
ret = nums[i].toLong()
}
}
return ret
}
}
複雜度分析：
- 時間複雜度：$O(n)$ 線性遍歷；
- 空間複雜度：$O(1)$ 僅使用常數級別空間。
T3. 長度遞增組的最大數目（Hard）
https://leetcode.cn/problems/maximum-number-of-groups-with-increasing-length/
題解（排序）
輸入陣列相當於數位的出現頻率，由於題目只關心構造組合的方案數而不關心數位的內容，數位本身是不重要的，因此我們可以先對頻率陣列排序，並從小到大列舉頻率。
在構造的過程中，我們將當前遍歷到的頻率追加到已經拼接過的分組上（預設存在一個空分組），如果當前的頻率不夠或者超出，則將剩餘元素放到候選容器中，嚴格證明見靈神的題解。
# 測試用例 [2, 2, 2]
0 => 0 1 => 0 1 2
1 1 2
0
# 測試用例 [1, 2, 5]
0 => 0 1 => 0 1 2
1 1 2
2
# 測試用例 [2, 1, 2] => 排序 [1, 2, 2]
0 => 0 1 => 0 1 2
1 1 2
# 測試用例 [1,1]
0
# 測試用例 [2, 100, 2, 2, 2] => 排序 [2, 2, 2, 2, 100]
0 => 0 1 => 0 1 2 => 跳過 => 0 1 2 3 => 剩餘的 4 可以拼接，但不會產生增加分組數量
1 1 2 1 2 3
0 0 4
4
class Solution {
fun maxIncreasingGroups(usageLimits: List<Int>): Int {
Collections.sort(usageLimits)
var ret = 0
var left = 0L
for (x in usageLimits) {
left += x.toLong()
// 可以構造新分組
if (left >= ret + 1) {
ret ++
left -= ret
}
}
return ret
}
}
複雜度分析：
- 時間複雜度：$O(nlgn)$ 瓶頸在排序；
- 空間複雜度：$O(lgn)$ 瓶頸在排序。
T4. 樹中可以形成迴文的路徑數（Hard）
https://leetcode.cn/problems/count-paths-that-can-form-a-palindrome-in-a-tree/
題解（狀態壓縮 + 字首和 + 雜湊表）
1、迴文判斷： 首先，由於題目的迴文串判斷允許重排，因此迴文串的 check 可以轉換為字母的計數:
- 出現次數為奇數的字母最多隻能出現 1 個；
- 出現次數為偶數的字母可以出現任意次。
2、奇偶性： 其次，由於題目的陣列僅為小寫字母，我們可以使用一個整型來壓縮表示 26 個字母的出現次數狀態，0 表示出現次數為偶數，1 表示出現次數為奇數。例如 0001 表示 ‘a’ 字母的出現次數為奇數，其他字母的出現次數為偶數（可能未出現）。
3、狀態壓縮： 基於以上 2 點，我們的目標是在樹上找到兩個點的路徑 [u, v] 使得路徑的狀態 mask 滿足以下其中 1 個條件：
- mask == 0：說明所有字母都出現偶數次；
- mask & (mask - 1) == 0：說明二進位制位中 1 的出現次數為 1 次，即只有一個字母出現奇數次。
4、字首和： 那麼，如果如何求樹上兩點間的路徑？這裡有一個技巧，如果直接收集兩個點之間的路徑資訊很難，我們可以先求從根節點到 u 的路徑 root_u，以及從根節點到 v 的路徑 root_v，再將兩段路徑互斥或就可以得到 u 到 v 的路徑（如果兩個節點的 LCA 不是根節點，那麼重複的路徑會被互斥或消除）。以題目範例 1 中節點 3 和節點 4 為例：path_3 = 0101，path_4 = 0110，而 path_3 xor path_4 = 0011，即 「ab」。
5、兩數之和： 最後，我們的目標就變成：尋找從到根節點的路徑互斥或值滿足「分析 3」條件的路徑，這可以用類似「兩數之和」中的雜湊表的方法求解。
class Solution {
fun countPalindromePaths(parent: List<Int>, s: String): Long {
var ret = 0L
val cnt = HashMap<Int, Int>()
val memo = HashMap<Int, Int>()
// 兩數之和模板
for (i in 0 until parent.size) {
val path = getPath(parent, s, memo, i)
// 1、兩條路徑互斥或值等於 0 的情況
ret += cnt.getOrDefault(path, 0)
for (j in 0 until 26) {
// 2、兩條路徑互斥或值中二進位制位 1 只有 1 個的情況
ret += cnt.getOrDefault(path xor 1.shl(j), 0)
}
cnt[path] = cnt.getOrDefault(path, 0) + 1
}
return ret
}
private fun getPath(parent: List<Int>, s: String, memo: MutableMap<Int, Int>, i: Int): Int {
// 終止條件
if (i == 0) return 0
// 讀備忘錄
if (memo.containsKey(i)) return memo[i]!!
val path = getPath(parent, s, memo, parent[i]) xor (1.shl(s[i] - 'a')) // 增加一個計數等於奇偶性翻轉
// 存備忘錄
memo[i] = path
return path
}
}
複雜度分析：
- 時間複雜度：$O(Cn)$ getPath() DFS 的時間複雜度為 $O(n)$，列舉方案的時間複雜度為 $O(Cn)$，其中 $C$ 為字元集大小；
- 空間複雜度：$O(n)$ 記錄每個節點到根節點的路徑值空間。
推薦閱讀
LeetCode 上分之旅系列往期回顧：
⭐️ 永遠相信美好的事情即將發生，歡迎加入小彭的 Android 交流社群~