日韩潮喷久久精品,综合欧美专区在线,九九热re

大家好，我是小彭。

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

周賽概覽

1. 將錢分給最多的兒童（Easy）
- 題解一：模擬 $O(1)$
- 題解二：完全背包 $O(children·money^2)$
1. 最大化數(shù)組的偉大值（Medium）
- 題解一：貪心 / 田忌賽馬 $O(nlgn)$
- 題解二：最大重復(fù)計(jì)數(shù) $O(n)$
1. 標(biāo)記所有元素后數(shù)組的分?jǐn)?shù)（Medium）
- 題解一：排序 O $(nlgn)$
- 題解二：按照嚴(yán)格遞減字段分組 $O(n)$
1. 修車的最少時(shí)間（Medium)
- 題解一：二分查找 $O(n + U·log(mc^2))$
- 題解二：二分查找 + 計(jì)數(shù)優(yōu)化 $O(n·log(mc^2))$

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

題目地址

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

題目描述

給你一個(gè)整數(shù) money ，表示你總共有的錢數(shù)（單位為美元）和另一個(gè)整數(shù) children ，表示你要將錢分配給多少個(gè)兒童。

你需要按照如下規(guī)則分配：

所有的錢都必須被分配。
每個(gè)兒童至少獲得 1 美元。
沒有人獲得 4 美元。

請你按照上述規(guī)則分配金錢，并返回最多有多少個(gè)兒童獲得恰好 **8 美元。如果沒有任何分配方案，返回 -1 。

題解一（模擬）

這道題搞數(shù)字迷信？發(fā)發(fā)發(fā) 888？

簡單模擬題，但是錯(cuò)誤率很高，提交通過率僅 19%。

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

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(1)$
空間復(fù)雜度： $O(1)$

題解二（完全背包問題）

競賽中腦海閃現(xiàn)過背包問題的思路，但第一題暴力才是王道，賽后驗(yàn)證可行。

包裹：最多有 children 人；
物品：每個(gè)金幣價(jià)值為 1 且不可分割，最多物品數(shù)為 money 個(gè)；
目標(biāo)：包裹價(jià)值恰好為 8 的最大個(gè)數(shù)；
限制條件：不允許包裹價(jià)值為 4，每個(gè)包裹至少裝 1 枚金幣。

令 dp[i][j] 表示分配到 i 個(gè)人為止，且分配總金額為 j 元時(shí)的最大價(jià)值，則有：

遞推關(guān)系：

$dp[i][j]=\sum_{k=1}^{j,k!=4} dp[i-1][j-k] + I(k==8)$

初始狀態(tài) dp[0][0] = 0
終止?fàn)顟B(tài) dp[children][money]

class Solution {
    fun distMoney(money: Int, children: Int): Int {
        var left = money
        // 每人至少分配 1 元
        left -= children
        // 違反規(guī)則 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：枚舉選項(xiàng)
                for (k in 0..j) {
                    // 不允許選擇 3
                    if (k == 3) continue
                    // 子狀態(tài)違反規(guī)則
                    if (-1 == dp[i - 1][j - k]) continue
                    // 子狀態(tài) + 當(dāng)前包裹狀態(tài)
                    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]
    }
}

滾動(dòng)數(shù)組優(yōu)化：

class Solution {
    fun distMoney(money: Int, children: Int): Int {
        var left = money
        // 每人至少分配 1 元
        left -= children
        // 違反規(guī)則 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：枚舉選項(xiàng)
                for (k in 0..j) {
                    // 不允許選擇 3
                    if (k == 3) continue
                    // 子狀態(tài)違反規(guī)則
                    if (-1 == dp[j - k]) continue
                    // 子狀態(tài) + 當(dāng)前包裹狀態(tài)
                    val cnt = dp[j - k] + if (k == 7) 1 else 0
                    dp[j] = Math.max(dp[j], cnt)
                }
            }
        }
        return dp[left]
    }

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(children·money^2)$
空間復(fù)雜度： $O(money)$

近期周賽背包問題：

LeetCode 周賽 333 · 無平方子集計(jì)數(shù)（Medium）
LeetCode 周賽 335 · 獲得分?jǐn)?shù)的方法數(shù)（Hard）

2592. 最大化數(shù)組的偉大值（Medium）

題目地址

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

題目描述

給你一個(gè)下標(biāo)從 0 開始的整數(shù)數(shù)組 nums 。你需要將 nums 重新排列成一個(gè)新的數(shù)組 perm 。

定義 nums 的 偉大值 為滿足 0 <= i < nums.length 且 perm[i] > nums[i] 的下標(biāo)數(shù)目。

請你返回重新排列 nums 后的最大偉大值。

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

貪心思路：田忌賽馬，以下賽馬策略最優(yōu)：

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

回到本題，考慮一組貢獻(xiàn)偉大值的配對 $(p, q)$ ，其中 $p < q$ 。由于越小的值越匹配到更大值，為了讓結(jié)果最優(yōu)，應(yīng)該讓 p 盡可能小，即優(yōu)先匹配 nums 數(shù)組的較小值。那么 $q$ 如何選擇呢？有 2 種策略：

策略 1 - 優(yōu)先匹配最大值：無法得到最優(yōu)解，因?yàn)闀?huì)消耗了較大的 q 值，可能導(dǎo)致部分 p 值無法匹配（如果田忌用上等馬對齊威王的下等馬，最終將是齊威王生出）；
策略 2- 優(yōu)先匹配最接近的更大值：最優(yōu)解，即田忌賽馬策略，以 [1,1,1,2,3,3,5] 為例：
- 初始狀態(tài) i = 0，j = 0；
- i = 0，j = 0，無法貢獻(xiàn)偉大值，j 自增 1（尋找最接近的更大值）；
- i = 0，j = 1，無法貢獻(xiàn)偉大值，j 自增 1；
- i = 0，j = 2，無法貢獻(xiàn)偉大值，j 自增 1；
- i = 0，j = 3，貢獻(xiàn)偉大值，j 自增 1，i 自增 1；
- i = 1，j = 4，貢獻(xiàn)偉大值，j 自增 1，i 自增 1；
- i = 2，j = 5，貢獻(xiàn)偉大值，j 自增 1，i 自增 1；
- i = 3，j = 6，貢獻(xiàn)偉大值，j 自增 1，i 自增 1；
- 退出循環(huán)，i = 4；正好等于偉大值 4。

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

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(nlgn + n)$ 排序 + 線性遍歷，其中 $n$ 是 $nums$ 數(shù)組長度；
空間復(fù)雜度： $O(lgn)$ 排序遞歸?？臻g。

題解二（最大重復(fù)計(jì)數(shù)）

競賽中從測試用例中觀察到題解與最大重復(fù)數(shù)存在關(guān)系，例如：

用例 [1,1,1,2,3,3,5]：最大重復(fù)數(shù)為 3，一個(gè)最優(yōu)方案為 [2,3,3,5,x,x,x]，最大偉大值為 7 - 3 = 4，其中 7 是數(shù)組長度；
用例 [1,2,2,2,2,3,5]：最大重復(fù)數(shù)為 4，一個(gè)最優(yōu)方案為 [2,3,5,x,x,x,x]，最大偉大值為 7 - 4 = 3，其中 7 是數(shù)組長度；
用例 [1,1,2,2,2,2,3,3,5]，最大重復(fù)數(shù)為 4，一個(gè)最優(yōu)方案為 [2,2,3,3,5,x,x,x,x]，最大偉大值為 9 - 4 = 5，其中 9 是數(shù)組長度。

我們發(fā)現(xiàn)題目的瓶頸在于數(shù)字最大重復(fù)出現(xiàn)計(jì)數(shù)。最大偉大值正好等于 數(shù)組長度 - 最大重復(fù)計(jì)數(shù)。

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

當(dāng) i 指針指向重復(fù)元素的首個(gè)元素時(shí)（例如下標(biāo)為 0、2、6 的位置），j 指針必須移動(dòng)到最接近的較大元素（例如下標(biāo)為 2，6，8 的位置）。而 i 指針和 j 指針的最大錯(cuò)開距離取決于數(shù)組重復(fù)出現(xiàn)次數(shù)最多的元素，只要錯(cuò)開這個(gè)距離，無論數(shù)組后續(xù)部分有多長，都能夠匹配上。

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
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(n)$ 其中 $n$ 是 $nums$ 數(shù)組的長度；
空間復(fù)雜度： $O(n)$ 其中 $n$ 是 $cnts$ 散列表空間。

2593. 標(biāo)記所有元素后數(shù)組的分?jǐn)?shù)（Medium）

題目地址

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

題目描述

給你一個(gè)數(shù)組 nums ，它包含若干正整數(shù)。

一開始分?jǐn)?shù) score = 0 ，請你按照下面算法求出最后分?jǐn)?shù)：

從數(shù)組中選擇最小且沒有被標(biāo)記的整數(shù)。如果有相等元素，選擇下標(biāo)最小的一個(gè)。
將選中的整數(shù)加到 score 中。
標(biāo)記 被選中元素，如果有相鄰元素，則同時(shí)標(biāo)記 與它相鄰的兩個(gè)元素 。
重復(fù)此過程直到數(shù)組中所有元素都被標(biāo)記。

請你返回執(zhí)行上述算法后最后的分?jǐn)?shù)。

題解一（排序）

這道題犯了大忌，沒有正確理解題意。一開始以為 “相鄰的元素” 是指未標(biāo)記的最相鄰元素，花了很多時(shí)間思考如何快速找到左右未標(biāo)記的數(shù)。其實(shí)題目沒有這么復(fù)雜，就是標(biāo)記數(shù)組上的相鄰元素。

如此這道題只能算 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
            // 標(biāo)記
            sum += nums[index]
            nums[index] = 0
            // 標(biāo)記相鄰元素
            if (index > 0) nums[index - 1] = 0
            if (index < nums.size - 1) nums[index + 1] = 0
        }
        return sum
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(nlgn)$ 堆排序時(shí)間，其中 $n$ 是 $nums$ 數(shù)組長度；
空間復(fù)雜度： $O(n)$ 堆空間。

題解二（按照嚴(yán)格遞減字段分組）

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

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

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
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(n)$ 其中 $n$ 是 $nums$ 數(shù)組的長度，每個(gè)元素最多訪問 2 次；
空間復(fù)雜度： $O(1)$ 只使用常數(shù)空間。

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

題目地址

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

題目描述

給你一個(gè)整數(shù)數(shù)組 ranks ，表示一些機(jī)械工的 能力值 。ranksi 是第 i 位機(jī)械工的能力值。能力值為 r 的機(jī)械工可以在 r * n2 分鐘內(nèi)修好 n 輛車。

同時(shí)給你一個(gè)整數(shù) cars ，表示總共需要修理的汽車數(shù)目。

請你返回修理所有汽車最少需要多少時(shí)間。

注意： 所有機(jī)械工可以同時(shí)修理汽車。

題解（二分查找）

我們發(fā)現(xiàn)問題在時(shí)間 t 上存在單調(diào)性：

假設(shè)可以在 t 時(shí)間內(nèi)修完所有車，那么大于 t 的時(shí)間都能修完；
如果不能在 t 時(shí)間內(nèi)修完所有車，那么小于 t 的時(shí)間都無法修完。

因此，我們可以用二分查找尋找 “可以修完的最小時(shí)間”：

二分的下界：1；
二分的上界：將所有的車交給能力值排序最高的工人，因?yàn)樗男首罡摺?/li>

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 時(shí)間內(nèi)修完所有車
    private fun check(ranks: IntArray, cars: Int, t: Long): Boolean {
        // 計(jì)算并行修車 t 時(shí)間能修完的車（由于 t 的上界較大，carSum 會(huì)溢出 Int）
        var carSum = 0L
        for (rank in ranks) {
            carSum += Math.sqrt(1.0 * t / rank).toLong()
        }
        return carSum >= cars
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(n·log(mc^2))$ 其中 $n$ 是 $ranks$ 數(shù)組長度， $m$ 是 $ranks$ 數(shù)組的最小值， $c$ 是車輛數(shù)量，二分的次數(shù)是 $O(log(mc^2))$ ，每次 $check$ 操作花費(fèi) $O(n)$ 時(shí)間；
空間復(fù)雜度： $O(1)$ 僅使用常量級別空間。

題解二（二分查找 + 計(jì)數(shù)優(yōu)化）

我們發(fā)現(xiàn) $ranks$ 的取值范圍很小，所有可以用計(jì)數(shù)優(yōu)化每次 $check$ 操作的時(shí)間復(fù)雜度：

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 時(shí)間內(nèi)修完所有車
    private fun check(ranks: IntArray, cars: Int, cnts: IntArray, minRank: Int, t: Long): Boolean {
        // 計(jì)算并行修車 t 時(shí)間能修完的車（由于 t 的上界較大，carSum 會(huì)溢出 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
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(n + U·log(mc^2))$ 其中 $n$ 是 $ranks$ 數(shù)組長度， $m$ 是 $ranks$ 數(shù)組的最小值， $U$ 是 $ranks$ 數(shù)組的取值范圍， $c$ 是車輛數(shù)量，二分的次數(shù)是 $O(log(mc^2))$ ，每次 $check$ 操作花費(fèi) $O(U)$ 時(shí)間；
空間復(fù)雜度： $O(U)$ $cnts$ 計(jì)數(shù)數(shù)組空間。

近期周賽二分查找題目：

LeetCode 332 · 統(tǒng)計(jì)公平數(shù)對的數(shù)目（Medium）
LeetCode 334 · 在網(wǎng)格圖中訪問一個(gè)格子的最少時(shí)間（Hard）

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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

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

周賽概覽

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

題目地址

題目描述

題解一（模擬）

題解二（完全背包問題）

2592. 最大化數(shù)組的偉大值（Medium）

題目地址

題目描述

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

題解二（最大重復(fù)計(jì)數(shù)）

2593. 標(biāo)記所有元素后數(shù)組的分?jǐn)?shù)（Medium）

題目地址

題目描述

題解一（排序）

題解二（按照嚴(yán)格遞減字段分組）

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

題目地址

題目描述

題解（二分查找）

題解二（二分查找 + 計(jì)數(shù)優(yōu)化）

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

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

周賽概覽

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

題目地址

題目描述

題解一（模擬）

題解二（完全背包問題）

2592. 最大化數(shù)組的偉大值（Medium）

題目地址

題目描述

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

題解二（最大重復(fù)計(jì)數(shù)）

2593. 標(biāo)記所有元素后數(shù)組的分?jǐn)?shù)（Medium）

題目地址

題目描述

題解一（排序）

題解二（按照嚴(yán)格遞減字段分組）

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

題目地址

題目描述

題解（二分查找）

題解二（二分查找 + 計(jì)數(shù)優(yōu)化）

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av