雙周賽 110
T1. 取整購買后的賬戶余額（Easy）
- 標(biāo)簽：模擬
T2. 在鏈表中插入最大公約數(shù)（Medium）
- 標(biāo)簽：鏈表、數(shù)學(xué)
T3. 使循環(huán)數(shù)組所有元素相等的最少秒數(shù)（Medium）
- 標(biāo)簽：貪心阅悍、散列表
T4. 使數(shù)組和小于等于 x 的最少時(shí)間（Hard）
- 標(biāo)簽：排序不等式好渠、動(dòng)態(tài)規(guī)劃、貪心
T1. 取整購買后的賬戶余額（Easy）
https://leetcode.cn/problems/insert-greatest-common-divisors-in-linked-list/
題解（模擬）
閱讀理解題节视。
其實(shí)就是將 purchaseAmount 向最近的 10 的倍數(shù)四舍五入拳锚，再用 100 減去它。
class Solution {
fun accountBalanceAfterPurchase(purchaseAmount: Int): Int {
return 100 - (purchaseAmount + 5) / 10 * 10
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
T2. 在鏈表中插入最大公約數(shù)（Medium）
https://leetcode.cn/problems/insert-greatest-common-divisors-in-linked-list/
題解（數(shù)學(xué)）
久違的鏈表題寻行。
題目相對簡單霍掺，其實(shí)就是依次處理每兩個(gè)節(jié)點(diǎn)，并插入一個(gè)新的最大公約數(shù)節(jié)點(diǎn)拌蜘。以下提供兩個(gè)寫法：
- 構(gòu)造新鏈表：
class Solution {
fun insertGreatestCommonDivisors(head: ListNode?): ListNode? {
val dummy = ListNode(-1)
var rear = dummy
var p = head
while (null != p) {
rear.next = p
rear = p
val next = p.next
if (null != next) {
val newNode = ListNode(gcb(p.`val`, next.`val`))
newNode.next = next
p.next = newNode
rear.next = newNode
rear = newNode
}
p = next
}
return dummy.next
}
private fun gcb(a:Int, b:Int) :Int {
var x = a
var y = b
while (y != 0) {
val temp = x % y
x = y
y = temp
}
return x
}
}
- 在原鏈表上插入：
class Solution {
fun insertGreatestCommonDivisors(head: ListNode?): ListNode? {
var p = head
while (null != p?.next) {
val next = p.next
val newNode = ListNode(gcb(p.`val`, next.`val`))
newNode.next = next
p.next = newNode
p = next
}
return head
}
private fun gcb(a:Int, b:Int) :Int {
var x = a
var y = b
while (y != 0) {
val temp = x % y
x = y
y = temp
}
return x
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
其中單次最大公約數(shù)的計(jì)算時(shí)間復(fù)雜度為
杆烁，U 為數(shù)值上界；
- 空間復(fù)雜度：
不考慮輸出空間简卧。
T3. 使循環(huán)數(shù)組所有元素相等的最少秒數(shù)（Medium）
https://leetcode.cn/problems/minimum-seconds-to-equalize-a-circular-array/
題解（貪心 + 散列表）
根據(jù)題目要求兔魂，我們可以通過將數(shù)字復(fù)制到相鄰位置上，以實(shí)現(xiàn)數(shù)組中所有元素都相等举娩。因此入热，如果我們選擇數(shù)字 x 為最終元素，那么決定替換秒數(shù)的關(guān)鍵在與數(shù)組中不等于 x 的最長子數(shù)組長度晓铆。
所以，我們的算法是計(jì)算以每種數(shù)字 x 為目標(biāo)的方案中绰播，最短的不等于 x 的最長子數(shù)組長度骄噪，并除以 2 向上取整的到結(jié)果。
class Solution {
fun minimumSeconds(nums: List<Int>): Int {
// 最大間隔的最小值
val n = nums.size
// lens：記錄每種數(shù)字的最長間隔
val lens = HashMap<Int, Int>()
// preIndexs：記錄每種數(shù)字的上次出現(xiàn)位置
val preIndexs = HashMap<Int, Int>()
// 記錄最后出現(xiàn)位置（環(huán)形數(shù)組邏輯）
for ((i, e) in nums.withIndex()) {
preIndexs[e] = i
}
for ((i, e) in nums.withIndex()) {
lens[e] = Math.max(lens.getOrDefault(e, 0), (i - preIndexs[e]!! - 1 + n) % n)
preIndexs[e] = i
}
var ret = n
for ((_, len) in lens) {
ret = Math.min(ret, (len + 1) / 2)
}
return ret
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
線性遍歷蠢箩；
- 空間復(fù)雜度：
T4. 使數(shù)組和小于等于 x 的最少時(shí)間（Hard）
https://leetcode.cn/problems/minimum-time-to-make-array-sum-at-most-x/
題解（DP + 排序不等式）
- 時(shí)間的上界： 假設(shè)題目的最少時(shí)間超過數(shù)組長度 n事甜，那么根據(jù)抽屜原理必然有某個(gè)位置重復(fù)置零兩次，那么第一次操作的貢獻(xiàn)就丟失了滔韵，因此逻谦，題目的時(shí)間上界不應(yīng)該超過 n，即每個(gè)位置最多置零一次陪蜻；
- 二分答案（X)： 數(shù)組元素和小于等于 x 與操作時(shí)間 t 不具備單調(diào)性邦马，因此不能使用二分答案的思路；
- 逆向思維： 令 s1 = sum(nums1), s2 = sum(nums2)宴卖，假設(shè)經(jīng)過 t 時(shí)間且不進(jìn)行任何操作滋将，那么元素總和將變成 s1 + s2 *t。現(xiàn)在需要從 [0, n-1] 中非重復(fù)地選擇 t 個(gè)位置症昏，假設(shè)在第 x 秒選擇位置 [i]随闽，那么對最終元素總和減少的貢獻(xiàn)度為 nums1[i] + x·nums2[i]。
-
排序不等式： 現(xiàn)在的問題是「選擇哪些數(shù)」以及「如何分配選擇時(shí)間」使得減少的貢獻(xiàn)度盡可能大：假設(shè)選擇位置 [i]肝谭、[j] 和 [k]掘宪，那么貢獻(xiàn)度為：
- nums1[i] + nums2[i] * x
- nums1[j] + nums2[j] * y
- nums1[k] + nums2[k] * z
- 無論如何分配，加法左邊的貢獻(xiàn)度是恒定的攘烛，問題關(guān)鍵在與如何使得加法右邊的貢獻(xiàn)度盡可能大魏滚；
- 直觀地觀察，容易想到應(yīng)該將元素值更大的元素分配到更靠后的位置上医寿，使其置零時(shí)貢獻(xiàn)更多栏赴；
- 驗(yàn)證證明可以根據(jù) 排序不等式 ，假設(shè)有兩組有序序列 a 和 b靖秩，每一項(xiàng)正序相乘并累加的和是最大的须眷。
-
動(dòng)態(tài)規(guī)劃（選哪個(gè)）： 定義 dp[i][j] 表示到第 [i] 個(gè)元素為止操作 j 次時(shí)的最大貢獻(xiàn)度
- 目標(biāo)：滿足 dp[n][j] 小于等于 x 的最小 j 值
- 狀態(tài)轉(zhuǎn)移方程（選和不選）：
- 排序： 將元素按照 nums2 正序排序，對于選擇 [i] 位置且選擇 j 次的方案沟突，分配在第 j 次選擇上的貢獻(xiàn)度是最大的花颗。
class Solution {
fun minimumTime(nums1: List<Int>, nums2: List<Int>, x: Int): Int {
val INF = -0x3F3F3F3F // 減少判斷
val n = nums1.size
// 排序
val ids = Array<Int>(n) {it}
Arrays.sort(ids) {i1, i2 ->
nums2[i1] - nums2[i2]
}
// 動(dòng)態(tài)規(guī)劃
val dp = Array(n + 1) { IntArray(n + 1) { INF }}
dp[0][0] = 0 // 初始狀態(tài)
for (i in 1 .. n) { // 枚舉物品
for (j in 0 .. i) { // 枚舉次數(shù)
dp[i][j] = dp[i - 1][j]
if (j > 0) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + nums1[ids[i - 1]] + nums2[ids[i - 1]] * j)
}
}
// println(dp[n].joinToString())
// 輸出
val s1 = nums1.sum()
val s2 = nums2.sum()
for (t in 0 .. n) {
if (s1 + s2 * t - dp[n][t] <= x) return t
}
return -1
}
}
滾動(dòng)數(shù)組優(yōu)化：
class Solution {
fun minimumTime(nums1: List<Int>, nums2: List<Int>, x: Int): Int {
val INF = -0x3F3F3F3F // 減少判斷
val n = nums1.size
// 排序
val ids = Array<Int>(n) {it}
Arrays.sort(ids) {i1, i2 ->
nums2[i1] - nums2[i2]
}
// 動(dòng)態(tài)規(guī)劃
val dp = IntArray(n + 1) { INF }
dp[0] = 0 // 初始狀態(tài)
for (i in 1 .. n) { // 枚舉物品
for (j in i downTo 1) { // 枚舉次數(shù)（逆序）
dp[j] = Math.max(dp[j], dp[j - 1] + nums1[ids[i - 1]] + nums2[ids[i - 1]] * j)
}
}
// println(dp[n].joinToString())
// 輸出
val s1 = nums1.sum()
val s2 = nums2.sum()
for (t in 0 .. n) {
if (s1 + s2 * t - dp[t] <= x) return t
}
return -1
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
其中排序時(shí)間為
，動(dòng)態(tài)規(guī)劃時(shí)間為
- 空間復(fù)雜度：
推薦閱讀
LeetCode 上分之旅系列往期回顧：
