刷爆 LeetCode 雙周賽 100，單方面宣布第一題最難

本文已收錄到 AndroidFamily，技術和職場問題，請關注公衆号 [彭旭銳] 提問。

大家好，我是小彭。

上周末是 LeetCode 第 100 場雙周賽，你參加了嗎？這場周賽整體沒有 Hard 題，但是也沒有 Easy 題。第一題國服前百名裡超過一半人 wa，很少見。

小彭的技術交流群 02 群來了，公衆号回複 “加群” 加入我們~

2591. 将錢分給最多的兒童（Easy）

題目位址

https://leetcode.cn/problems/distribute-money-to-maximum-children/description/

題目描述

給你一個整數 money ，表示你總共有的錢數（機關為美元）和另一個整數 children ，表示你要将錢配置設定給多少個兒童。

你需要按照如下規則配置設定：

• 所有的錢都必須被配置設定。
• 每個兒童至少獲得 1 美元。
• 沒有人獲得 4 美元。

請你按照上述規則配置設定金錢，并傳回 最多 有多少個兒童獲得 恰好 **8 美元。如果沒有任何配置設定方案，傳回 -1 。

題解一（模拟）

這道題搞數字迷信？發發發 888？

簡單模拟題，但是錯誤率很高，送出通過率僅 19%。

class Solution {
    fun distMoney(money: Int, children: Int): Int {
        var left = money
        // 每人至少配置設定 1 元
        left -= children
        // 違反規則 2
        if (left < 0) return -1
        // 1、完美：正好所有人可以配置設定 8 元
        if (left == children * 7) return children
        // 2、溢出：所有人可以配置設定 8 元有結餘，需要選擇 1 個人配置設定結餘的金額
        if (left > children * 7) return children - 1
        // 3、不足：盡可能配置設定 8 元
        var sum = left / 7
        // 結餘金額
        left -= sum * 7
        // 如果結餘 3 元，并且剩下 1 人配置設定了 1 元，需要破壞一個 8 元避免出現配置設定 4 美元
        if (left == 3 && children - sum == 1) return sum - 1
        return sum
    }
}
           

複雜度分析：

• 時間複雜度：O(1)
• 空間複雜度：O(1)

題解二（完全背包問題）

競賽中腦海閃現過背包問題的思路，但第一題暴力才是王道，賽後驗證可行。

• 包裹：最多有 children 人；
• 物品：每個金币價值為 1 且不可分割，最多物品數為 money 個；
• 目标：包裹價值恰好為 8 的最大個數；
• 限制條件：不允許包裹價值為 4，每個包裹至少裝 1 枚金币。

令 dp[i][j] 表示配置設定到 i 個人為止，且配置設定總金額為 j 元時的最大價值，則有：

• 遞推關系：
• 初始狀态 dp[0][0] = 0
• 終止狀态 dp[children][money]

class Solution {
    fun distMoney(money: Int, children: Int): Int {
        var left = money
        // 每人至少配置設定 1 元
        left -= children
        // 違反規則 2
        if (left < 0) return -1
        val dp = Array(children + 1) { IntArray(left + 1) { -1 } }
        dp[0][0] = 0
        // i：枚舉包裹
        for (i in 1..children) {
            // j：枚舉金額
            for (j in 0..left) {
                // k：枚舉選項
                for (k in 0..j) {
                    // 不允許選擇 3
                    if (k == 3) continue
                    // 子狀态違反規則
                    if (-1 == dp[i - 1][j - k]) continue
                    // 子狀态 + 目前包裹狀态
                    val cnt = dp[i - 1][j - k] + if (k == 7) 1 else 0
                    dp[i][j] = Math.max(dp[i][j], cnt)
                }
            }
        }
        return dp[children][left]
    }
}
           

滾動數組優化：

class Solution {
    fun distMoney(money: Int, children: Int): Int {
        var left = money
        // 每人至少配置設定 1 元
        left -= children
        // 違反規則 2
        if (left < 0) return -1
        val dp = IntArray(left + 1) { -1 }
        dp[0] = 0
        // i：枚舉包裹
        for (i in 1..children) {
            // j：枚舉金額
            for (j in left downTo 0) {
                // k：枚舉選項
                for (k in 0..j) {
                    // 不允許選擇 3
                    if (k == 3) continue
                    // 子狀态違反規則
                    if (-1 == dp[j - k]) continue
                    // 子狀态 + 目前包裹狀态
                    val cnt = dp[j - k] + if (k == 7) 1 else 0
                    dp[j] = Math.max(dp[j], cnt)
                }
            }
        }
        return dp[left]
    }

           

複雜度分析：

• 時間複雜度：O(children·money^1)
• 空間複雜度：O(money)

近期周賽背包問題：

• LeetCode 周賽 333 · 無平方子集計數（Medium）
• LeetCode 周賽 335 · 獲得分數的方法數（Hard）

2592. 最大化數組的偉大值（Medium）

題目位址

https://leetcode.cn/problems/maximize-greatness-of-an-array/

題目描述

給你一個下标從 0 開始的整數數組 nums 。你需要将 nums 重新排列成一個新的數組 perm 。

定義 nums 的 偉大值 為滿足 0 <= i < nums.length 且 perm[i] > nums[i] 的下标數目。

請你傳回重新排列 nums 後的 最大 偉大值。

題解一（貪心 / 田忌賽馬）

貪心思路：田忌賽馬，以下賽馬政策最優：

• 田忌的中等馬對齊威王的下等馬，田忌勝；
• 田忌的上等馬對齊威王的中等馬，田忌勝；
• 田忌的下等馬對齊威王的下等馬，齊威王勝。

回到本題，考慮一組貢獻偉大值的配對 (p,q)，其中 p<q。由于越小的值越比對到更大值，為了讓結果最優，應該讓 p 盡可能小，即優先比對 nums 數組的較小值。那麼 q 如何選擇呢？有 2 種政策：

• 政策 1 - 優先比對最大值：無法得到最優解，因為會消耗了較大的 q 值，可能導緻部分 p 值無法比對（如果田忌用上等馬對齊威王的下等馬，最終将是齊威王生出）；
• 政策 2- 優先比對最接近的更大值：最優解，即田忌賽馬政策，以 [1,1,1,2,3,3,5] 為例：初始狀态 i = 0，j = 0；i = 0，j = 0，無法貢獻偉大值，j 自增 1（尋找最接近的更大值）；i = 0，j = 1， 無法貢獻偉大值，j 自增 1；i = 0，j = 2， 無法貢獻偉大值，j 自增 1；i = 0，j = 3， 貢獻偉大值，j 自增 1，i 自增 1；i = 1，j = 4， 貢獻偉大值，j 自增 1，i 自增 1；i = 2，j = 5， 貢獻偉大值，j 自增 1，i 自增 1；i = 3，j = 6， 貢獻偉大值，j 自增 1，i 自增 1；退出循環，i = 4；正好等于偉大值 4。

class Solution {
    fun maximizeGreatness(nums: IntArray): Int {
        nums.sort()
        // i：參與比對的指針
        var i = 0
        for (num in nums) {
            // 貢獻偉大值
            if (num > nums[i]) i++
        }
        return i
    }
}
           

複雜度分析：

• 時間複雜度：O(nlgn + n)
• 空間複雜度：O(lgn)

題解二（最大重複計數）

競賽中從測試用例中觀察到題解與最大重複數存在關系，例如：

• 用例 [1,1,1,2,3,3,5]：最大重複數為 3，一個最優方案為 [2,3,3,5,x,x,x]，最大偉大值為 7 - 3 = 4，其中 7 是數組長度；
• 用例 [1,2,2,2,2,3,5]：最大重複數為 4，一個最優方案為 [2,3,5,x,x,x,x]，最大偉大值為 7 - 4 = 3，其中 7 是數組長度；
• 用例 [1,1,2,2,2,2,3,3,5]，最大重複數為 4，一個最優方案為 [2,2,3,3,5,x,x,x,x]，最大偉大值為 9 - 4 = 5，其中 9 是數組長度。

我們發現題目的瓶頸在于數字最大重複出現計數。最大偉大值正好等于 數組長度 - 最大重複計數。

如何證明？關鍵在于 i 指針和 j 指針的最大距離：

當 i 指針指向重複元素的首個元素時（例如下标為 0、2、6 的位置），j 指針必須移動到最接近的較大元素（例如下标為 2，6，8 的位置）。而 i 指針和 j 指針的最大錯開距離取決于數組重複出現次數最多的元素，隻要錯開這個距離，無論數組後續部分有多長，都能夠比對上。

class Solution {
    fun maximizeGreatness(nums: IntArray): Int {
        var maxCnt = 0
        val cnts = HashMap<Int, Int>()
        for (num in nums) {
            cnts[num] = cnts.getOrDefault(num, 0) + 1
            maxCnt = Math.max(maxCnt, cnts[num]!!)
        }
        return nums.size - maxCnt
    }
}
           

複雜度分析：

• 時間複雜度：O(n)
• 空間複雜度：O(n)

2593. 标記所有元素後數組的分數（Medium）

題目位址

https://leetcode.cn/problems/find-score-of-an-array-after-marking-all-elements/

題目描述

給你一個數組 nums ，它包含若幹正整數。

一開始分數 score = 0 ，請你按照下面算法求出最後分數：

• 從數組中選擇最小且沒有被标記的整數。如果有相等元素，選擇下标最小的一個。
• 将選中的整數加到 score 中。
• 标記 被選中元素，如果有相鄰元素，則同時标記 與它相鄰的兩個元素 。
• 重複此過程直到數組中所有元素都被标記。

請你傳回執行上述算法後最後的分數。

題解一（排序）

這道題犯了大忌，沒有正确了解題意。一開始以為 “相鄰的元素” 是指未标記的最相鄰元素，花了很多時間思考如何快速找到左右未标記的數。其實題目沒有這麼複雜，就是标記數組上的相鄰元素。

如此這道題隻能算 Medium 偏 Easy 難度。

class Solution {
    fun findScore(nums: IntArray): Long {
        // 小頂堆（索引）
        val heap = PriorityQueue<Int>() { i1, i2 ->
            if (nums[i1] != nums[i2]) nums[i1] - nums[i2] else i1 - i2
        }.apply {
            for (index in nums.indices) {
                offer(index)
            }
        }
        var sum = 0L
        while (!heap.isEmpty()) {
            val index = heap.poll()
            if (nums[index] == 0) continue
            // 标記
            sum += nums[index]
            nums[index] = 0
            // 标記相鄰元素
            if (index > 0) nums[index - 1] = 0
            if (index < nums.size - 1) nums[index + 1] = 0
        }
        return sum
    }
}
           

複雜度分析：

• 時間複雜度：O(nlgn)
• 空間複雜度：O(n)

題解二（按照嚴格遞減字段分組）

思路參考：靈茶山艾府的題解

按照嚴格遞減字段分組，在找到坡底後間隔累加 nums[i]，nums[i - 2]，nums[i - 4]，并從 i + 2 開始繼續尋找坡底。

class Solution {
    fun findScore(nums: IntArray): Long {
        val n = nums.size
        var sum = 0L
        var i = 0
        while (i < nums.size) {
            val i0 = i // 坡頂
            while (i + 1 < n && nums[i] > nums[i + 1]) i++ // 尋找坡底
            for (j in i downTo i0 step 2) { // 間隔累加
                sum += nums[j]
            }
            i += 2 // i + 1 不能選
        }
        return sum
    }
}
           

複雜度分析：

• 時間複雜度：O(n)
• 空間複雜度：O(1)

2594. 修車的最少時間（Medium)

題目位址

https://leetcode.cn/problems/minimum-time-to-repair-cars/

題目描述

給你一個整數數組 ranks ，表示一些機械工的 能力值 。ranksi 是第 i 位機械工的能力值。能力值為 r 的機械工可以在 r * n2 分鐘内修好 n 輛車。

同時給你一個整數 cars ，表示總共需要修理的汽車數目。

請你傳回修理所有汽車 最少 需要多少時間。

注意： 所有機械工可以同時修理汽車。

題解（二分查找）

我們發現問題在時間 t 上存在單調性：

• 假設可以在 t 時間内修完所有車，那麼大于 t 的時間都能修完；
• 如果不能在 t 時間内修完所有車，那麼小于 t 的時間都無法修完。

是以，我們可以用二分查找尋找 “可以修完的最小時間”：

• 二分的下界：1；
• 二分的上界：将所有的車交給能力值排序最高的勞工，因為他的效率最高。

class Solution {
    fun repairCars(ranks: IntArray, cars: Int): Long {
        // 尋找能力值排序最高的勞工
        var minRank = Integer.MAX_VALUE
        for (rank in ranks) {
            minRank = Math.min(minRank, rank)
        }
        var left = 1L
        var right = 1L * minRank * cars * cars
        // 二分查找
        while (left < right) {
            val mid = (left + right) ushr 1
            if (check(ranks, cars, mid)) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }

    // return 能否在 t 時間内修完所有車
    private fun check(ranks: IntArray, cars: Int, t: Long): Boolean {
        // 計算并行修車 t 時間能修完的車（由于 t 的上界較大，carSum 會溢出 Int）
        var carSum = 0L
        for (rank in ranks) {
            carSum += Math.sqrt(1.0 * t / rank).toLong()
        }
        return carSum >= cars
    }
}
           

複雜度分析：

• 時間複雜度：
• 空間複雜度：

題解二（二分查找 + 計數優化）

我們發現 ranks 的取值範圍很小，所有可以用計數優化每次 check 操作的時間複雜度：

class Solution {
    fun repairCars(ranks: IntArray, cars: Int): Long {
        // 尋找能力值排序最高的勞工
        val cnts = IntArray(101)
        var minRank = Integer.MAX_VALUE
        for (rank in ranks) {
            minRank = Math.min(minRank, rank)
            cnts[rank]++
        }
        var left = 1L
        var right = 1L * minRank * cars * cars
        // 二分查找
        while (left < right) {
            val mid = (left + right) ushr 1
            if (check(ranks, cars, cnts, minRank, mid)) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }

    // return 能否在 t 時間内修完所有車
    private fun check(ranks: IntArray, cars: Int, cnts: IntArray, minRank: Int, t: Long): Boolean {
        // 計算并行修車 t 時間能修完的車（由于 t 的上界較大，carSum 會溢出 Int）
        var carSum = 0L
        for (rank in minRank..100) {
            if (cnts[rank] == 0) continue
            carSum += cnts[rank] * Math.sqrt(1.0 * t / rank).toLong()
        }
        return carSum >= cars
    }
}
           

複雜度分析：

• 時間複雜度：
• 空間複雜度：

近期周賽二分查找題目：

• LeetCode 332 · 統計公平數對的數目（Medium）
• LeetCode 334 · 在網格圖中通路一個格子的最少時間（Hard）

這場周賽就這麼多，我們下周見。