?? 本文已收錄到 AndroidFamily，技術(shù)和職場(chǎng)問題，請(qǐng)關(guān)注公眾號(hào) [彭旭銳] 和 BaguTree Pro 知識(shí)星球提問。

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)鍵在于掌握問題背后的算法思維框架，你的思考越抽象，它能覆蓋的問題域就越廣，理解難度也更復(fù)雜。在這個(gè)專欄里，小彭與你分享每場(chǎng) LeetCode 周賽的解題報(bào)告，一起體會(huì)上分之旅。

本文是 LeetCode 上分之旅系列的第 42 篇文章，往期回顧請(qǐng)移步到文章末尾~

周賽 360

T1. 距離原點(diǎn)最遠(yuǎn)的點(diǎn)（Easy）

• 標(biāo)簽：模擬

T2. 找出美麗數(shù)組的最小和（Medium）

• 標(biāo)簽：散列表、貪心、數(shù)學(xué)

T3. 使子序列的和等于目標(biāo)的最少操作次數(shù)（Hard）

• 標(biāo)簽：位運(yùn)算、散列表、排序

T4. 在傳球游戲中最大化函數(shù)值（Hard）

• 標(biāo)簽：樹、倍增、動(dòng)態(tài)規(guī)劃、內(nèi)向基環(huán)樹

---

T1. 距離原點(diǎn)最遠(yuǎn)的點(diǎn)（Easy）

https://leetcode.cn/problems/furthest-point-from-origin/

題解（模擬）

根據(jù)題意 “_” 既可以作為 “L” 也可以作為 “R”。容易想到，為了使得終點(diǎn)距離原點(diǎn)更遠(yuǎn)，當(dāng)所有 “_” 僅作為 “L” 或 “R” 對(duì)結(jié)果的貢獻(xiàn)是最優(yōu)的，此時(shí)問題的結(jié)果就取決于 “L” 和 “R” 的差絕對(duì)值。

class Solution {fun furthestDistanceFromOrigin(moves: String): Int {return moves.count{ it == '_' } + abs(moves.count{ it == 'L' } - moves.count{ it == 'R' })}
}

一次遍歷：

class Solution {fun furthestDistanceFromOrigin(moves: String): Int {var cntL = 0var cntR = 0for (e in moves) {when (e) {'L' -> {cntL ++cntR --}'R' -> {cntL --cntR ++}else -> {cntL ++cntR ++}}}return max(abs(cntL), abs(cntR))}
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$ 線性遍歷；
• 空間復(fù)雜度：$O(1)$ 僅使用常量級(jí)別空間。

---

T2. 找出美麗數(shù)組的最小和（Medium）

https://leetcode.cn/problems/find-the-minimum-possible-sum-of-a-beautiful-array/

這道題與上周周賽 359 T2 2829.?k-avoiding 數(shù)組的最小總和 相比，除了數(shù)據(jù)范圍之外是完全相同的，有點(diǎn)離譜。

題解一（散列表 + 貪心）

從 $1$ 開始從小到大枚舉，如果當(dāng)前元素 $cur$ 與已選列表不沖突，則加入結(jié)果中。為了驗(yàn)證是否沖突，我們使用散列表在 $O(1)$ 時(shí)間復(fù)雜度判斷。

class Solution {fun minimumPossibleSum(n: Int, k: Int): Long {val set = HashSet<Int>()var sum = 0Lvar cur = 1repeat(n) {while (!set.isEmpty() && set.contains(k - cur)) cur++sum += curset.add(cur)cur++}return sum}
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$ 線性遍歷；
• 空間復(fù)雜度：$O(n)$ 散列表空間。

題解二（數(shù)學(xué)）

這道題還可以繼續(xù)挖掘數(shù)學(xué)規(guī)律，我們發(fā)現(xiàn)當(dāng)我們從 $1$ 開始從小到大枚舉時(shí)，每選擇一個(gè)數(shù)的同時(shí)必然會(huì)使得另一個(gè)數(shù) $k?x$ 不可選。例如：

• 選擇 $1$，則 $k?1$ 不可選；
• 選擇 $2$，則 $k?2$ 不可選；
• …
• 選擇 $k/2$，則 $k?k/2$ 不可選。

可以發(fā)現(xiàn)，最終選擇的元素被分為兩部分：

• 小于 $k$ 的部分：選擇所有和為 $k$ 的配對(duì)中的較小值，即 ；
• 大于等于 $k$ 的部分：與其他任意正整數(shù)相加都不會(huì)等于 $k$，因此大于等于 $k$ 的數(shù)必然可以選擇，即 共 n - m 個(gè)數(shù)。

我們令 $m=min(k/2,n)$，使用求和公式可以 $O(1)$ 求出兩部分的總和：

• 小于 k 的部分：$m(m+1)/2$
• 大于等于 k 的部分：$(n?m)?(2?k+n?m?1)/2$

class Solution {fun minimumPossibleSum(n: Int, k: Int): Long {val m = 1L * Math.min(n, k / 2)return m * (m + 1) / 2 + (n - m) * (2 * k + n - m - 1) / 2}
}

復(fù)雜度分析：

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

---

T3. 使子序列的和等于目標(biāo)的最少操作次數(shù)（Hard）

https://leetcode.cn/problems/minimum-operations-to-form-subsequence-with-target-sum/

這道題的考點(diǎn)不復(fù)雜，難點(diǎn)在模擬問題挺考驗(yàn)編碼功底的。

問題分析

• 關(guān)鍵信息： $nums$ 數(shù)組中所有元素都是 $2$ 的冪，元素順序?qū)Y(jié)果沒有影響；
• 問題是否有解： 考慮到所有數(shù)最終都能拆分成 $1$，那么只要 $nums$ 數(shù)組的和大于等于 $target$ 就一定有解；

# 二進(jìn)制位
nums:   _ _ _ 1 _ _ _ _
target: _ _ _ _ _ 1 _ _

• 子問題： 問題是否有解的判斷不僅適用于原問題，對(duì)于僅考慮二進(jìn)制位最低位 $[0]$ 到 $[k]$ 的子問題亦是如此。

以示例 1 nums = [1,2,8], target = 7 與示例 2 nums = [1,32,1,2], target = 12 為例，我們將統(tǒng)計(jì) $nums$ 中不同 $2$ 的冪的出現(xiàn)次數(shù)：

# 二進(jìn)制位
nums:   _ _ _ _ 1 _ 1 1
target: _ _ _ _ _ 1 1 1# 二進(jìn)制位
nums:   _ _ 1 _ _ _ 1 2 # 1 出現(xiàn) 2 次
target: _ _ _ _ 1 1 _ _

那么當(dāng)我們從右向左枚舉二進(jìn)制位 $k$ 時(shí)，如果「$nums$ 中小于等于 $2^k$ 的元素和」$\ge$ 「$target$ 中低于等于 $k$ 位的值」，那么對(duì)于僅考慮 $[0,k]$ 位上的子問題是有解的。否則，我們需要找到 $nums$ 中最近大于 $2^k$ 的最近數(shù)組做拆分：

# 只考慮低 2 位，可以構(gòu)造
nums:   _ _ _ _ 1 _ | 1 1
target: _ _ _ _ _ 1 | 1 1# 只考慮低 3 位，無法構(gòu)造，需要找到最近的 “1” 做拆分
nums:   _ _ _ _ 1 | _ 1 1
target: _ _ _ _ _ | 1 1 1# 只考慮低 3 位，無法構(gòu)造，需要找到最近的 “1” 做拆分
nums:   _ _ 1 _ _ | _ 1 2
target: _ _ _ _ 1 | 1 _ _# 只考慮低 6 位，可以構(gòu)造
nums:   _ _ | 1 _ _ _ 1 2
target: _ _ | _ _ 1 1 _ _

組合以上技巧：

寫法一（數(shù)組模擬）

思路參考靈神的題解。

• 首先，我們使用長(zhǎng)為 $32$ 的數(shù)組，計(jì)算出 $nums$ 數(shù)組中每個(gè) $2$ 的冪的出現(xiàn)次數(shù)；
• 隨后，我們從低位到高位枚舉二進(jìn)制位 $i$，在每輪迭代中將 $nums$ 數(shù)組中的 $2^i$ 元素累加到 $sum$ 中，此舉相當(dāng)于在求「低 $i$ 位的子問題」可以構(gòu)造的最大值；
• 最后，我們比較 $sum$ 是否大于等于 $target$（只考慮低 $i$ 位），此舉相當(dāng)于在判斷「低 $i$ 位的子問題」是否可構(gòu)造。如果不可構(gòu)造，我們嘗試尋找最近的 $2^j$ 做拆分；
• 另外，有一個(gè)優(yōu)化點(diǎn)：當(dāng)我們拆分將 $2^j$ 拆分到 $2^i(j>i)$ 時(shí)并不是直接丟棄 $2^j$，而是會(huì)留下 等一系列數(shù)，可以直接跳到第 $j$ 位繼續(xù)枚舉。

注意一個(gè)容易 WA 的地方，在開頭特判的地方，由于元素和可能會(huì)溢出 $Int$ 上界，所以我們需要轉(zhuǎn)換為在 $Long$ 上的求和。

class Solution {fun minOperations(nums: List<Int>, target: Int): Int {if (nums.fold(0L) { it, acc -> it + acc } < target) return -1// if (nums.sum() < target) return -1 // 溢出// 計(jì)數(shù)val cnts = IntArray(32)for (num in nums) {var i = 0var x = numwhile (x > 1) {x = x shr 1i += 1}cnts[i]++}var ret = 0var i = 0var sum = 0Lwhile(sum < target) {// 累加低位的 numssum += (cnts[i]) shl i// println("i=$i, sum=$sum")// 低 i 位掩碼val mask = (1 shl (i + 1)) - 1// 構(gòu)造子問題if (sum < target and mask) {var j = i + 1while (cnts[j] == 0) { // 基于開頭的特判，此處一定有解j++}// 拆分ret += j - ii = j} else {i += 1}}return ret}
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n?U+U$) 其中 $n$ 為 $nums$ 數(shù)組的長(zhǎng)度，$U$ 為整型大小 $32$；
• 空間復(fù)雜度：$O(U)$ 數(shù)組空間。

寫法二（散列表模擬）

在計(jì)數(shù)的部分，我們可以使用散列表模擬，復(fù)雜度相同。

class Solution {fun minOperations(nums: List<Int>, target: Int): Int {if (nums.fold(0L) { it, acc -> it + acc } < target) return -1// if (nums.sum() < target) return -1 // 溢出// 計(jì)數(shù)val cnts = HashMap<Int, Int>()for (num in nums) {cnts[num] = cnts.getOrDefault(num, 0) + 1}var ret = 0var i = 0var sum = 0Lwhile(sum < target) {// 累加低位的 numssum += (cnts[1 shl i] ?: 0) shl i// println("i=$i, sum=$sum")// 低 i 位掩碼val mask = (1 shl (i + 1)) - 1// 構(gòu)造子問題if (sum < target and mask) {var j = i + 1while (!cnts.containsKey(1 shl j)) { // 基于開頭的特判，此處一定有解j++}// 拆分ret += j - ii = j} else {i += 1}}return ret}
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n+U)$ 其中 $n$ 為 $nums$ 數(shù)組的長(zhǎng)度，$U$ 為整型大小 $32$；
• 空間復(fù)雜度：$O(U)$ 散列表空間。

寫法三（逆向思維）

思路參考雪景式的題解，前兩種寫法是在從小到大枚舉「選哪個(gè)」，我們也可以枚舉「不選哪個(gè)」。

• 思考 1： 在原問題有解$（sum>target）$的情況下，如果從 $sum$ 中剔除最大的元素 $x$ 后，依然滿足剩余的元素和 $sum’>target$，那么直接將 $x$ 去掉，這是因?yàn)橐欢ù嬖诒?$x$ 操作次數(shù)更小的方案能夠構(gòu)造 $target$（元素越大拆分次數(shù)越多）。
• 思考 2： 如果從 $sum$ 中剔除最大的元素 $x$ 后不能構(gòu)造，說明 $x$ 是一定要選擇或者拆分，此時(shí)考慮 $x$ 對(duì) $target$ 的影響：
  • 如果 $x>target$，那么 $x$ 需要先拆分
  • 如果 $x\le target$，那么 $x$ 可以被選擇并抵消 $target$

class Solution {fun minOperations(nums: MutableList<Int>, target: Int): Int {var sum = nums.fold(0L) { it, acc -> it + acc }if (sum < target) return -1// 排序nums.sortDescending()// 從大到小枚舉var ret = 0var left = targetwhile (sum > left) {val x = nums.removeFirst()if (sum - x >= left){sum -= x} else if (x <= left) {sum -= xleft -= x} else {ret += 1nums.add(0, x / 2)nums.add(0, x / 2)}// println("ret=$ret, sum=$sum, left=$left, x=$x,  nums=${nums.joinToString()}")}return ret}
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(nlgn+n+U)$ 瓶頸在排序，枚舉階段每個(gè)元素最多訪問 $1$ 次，拆分次數(shù)最多為 $U$；
• 空間復(fù)雜度：$O(lgn)$ 排序遞歸棧空間。

---

T4. 在傳球游戲中最大化函數(shù)值（Hard）

https://leetcode.cn/problems/maximize-value-of-function-in-a-ball-passing-game/

題解（樹上倍增）

從近期周賽的趨勢(shì)看，出題人似乎有意想把 LeetCode 往偏競(jìng)賽的題目引導(dǎo)。

這道題如果知道樹上倍增算法，其實(shí)比第三題還簡(jiǎn)單一些。

• 問題目標(biāo)： 找到最佳方案，使得從起點(diǎn)開始傳球 $k$ 次的路徑和最大化；
• 暴力： 對(duì)于暴力的做法，我們可以枚舉以每名玩家為起點(diǎn)的方案，并模擬傳球過程求出最佳方案。但是這道題的步長(zhǎng) $k$ 的上界非常大 $10^{10}$，如果逐級(jí)向上傳球，那么單次查詢的時(shí)間復(fù)雜度是 $O(k)$?，F(xiàn)在，需要思考如何優(yōu)化模擬 $k$ 次傳球的效率；
• 倍增思想： 借鑒 1483. 樹節(jié)點(diǎn)的第 K 個(gè)祖先 的解法，我們可以利用倍增算法將線性的操作施加指數(shù)級(jí)別的貢獻(xiàn)：
  • 如果可以預(yù)處理出每個(gè)玩家的多級(jí)后驅(qū)玩家，那么在查詢時(shí)可以加速跳轉(zhuǎn)；
  • 由于每個(gè)數(shù)都可以進(jìn)行二進(jìn)制拆分為多個(gè) $2$ 的冪的和，如果預(yù)處理出第 個(gè)后驅(qū)玩家，那么求解第 $k$ 次傳球時(shí)可以轉(zhuǎn)化為多次 $2^i$ 個(gè)后驅(qū)玩家跳轉(zhuǎn)操作，大幅減少操作次數(shù)。

class Solution {fun getMaxFunctionValue(receiver: List<Int>, k: Long): Long {val n = receiver.sizeval m = 64 - k.countLeadingZeroBits()// 預(yù)處理// dp[i][j] 表示 i 傳球 2^j 次后的節(jié)點(diǎn)val dp = Array(n) { IntArray(m) }// dp[i][j] 表示 i 傳球 2^j 次的路徑和val sum = Array(n) { LongArray(m) }for (i in 0 until n) {dp[i][0] = receiver[i]sum[i][0] = receiver[i].toLong()}for (j in 1 until m) {for (i in 0 until n) { // 這道題沒有根節(jié)點(diǎn)，不需要考慮 child == -1 的情況val child = dp[i][j - 1]// 從 i 條 2^{j-1} 次，再跳 2^{j-1}dp[i][j] = dp[child][j - 1]sum[i][j] = sum[i][j - 1] + sum[child][j - 1]}}// 枚舉方案var ret = 0Lfor (node in 0 until n) {var i = nodevar x = kvar s = node.toLong() // 起點(diǎn)的貢獻(xiàn)while (x != 0L) {val j = x.countTrailingZeroBits()s += sum[i][j]i = dp[i][j]x = x and (x - 1)}ret = max(ret, s)}return ret}
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：預(yù)處理時(shí)間為 $O(nlgk)$，枚舉時(shí)間為 $O(nlgk)$，其中 $n$ 為 $receivers$ 數(shù)組的長(zhǎng)度；
• 空間復(fù)雜度：預(yù)處理空間 $O(nlgk)$。

另外，這道題還有基于「內(nèi)向基環(huán)樹」的 $O(n)$ 解法。

---

推薦閱讀

LeetCode 上分之旅系列往期回顧：

• LeetCode 單周賽第 359 場(chǎng) · 結(jié)合離散化的線性 DP 問題
• LeetCode 單周賽第 358 場(chǎng) · 結(jié)合中心擴(kuò)展的單調(diào)棧貪心問題
• LeetCode 雙周賽第 111 場(chǎng) · 按部就班地解決動(dòng)態(tài)規(guī)劃問題
• LeetCode 雙周賽第 110 場(chǎng) · 結(jié)合排序不等式的動(dòng)態(tài)規(guī)劃

?? 永遠(yuǎn)相信美好的事情即將發(fā)生，歡迎加入小彭的 Android 交流社群~