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 上分之旅系列往期回顧：

LeetCode 單周賽第 354 場 · 摩爾投票派上用場

LeetCode 單周賽第 353 場 · 看似沒考 LIS 最長遞增子序列，好像又考了

LeetCode 雙周賽第 109 場 · 按部就班地解決動态規劃問題

LeetCode 雙周賽第 107 場 · 很有意思的 T2 題

⭐️ 永遠相信美好的事情即将發生，歡迎加入小彭的 Android 交流社群~