LeetCode 雙週賽 98，腦筋急轉彎轉不過來！
theme: jzman
我正在參加「掘金·啟航計劃」
大家好，我是小彭。
昨晚是 LeetCode 第 98 場雙週賽，你參加了嗎？這場周賽需要腦筋急轉彎，轉不過來 Medium 就會變成 Hard，轉得過來就變成 Easy。
小彭的 Android 交流群 02 群已經建立啦，公眾號回覆 “加群” 加入我們~
2566. 替換一個數字後的最大差值（Easy）
題目地址
http://leetcode.cn/problems/maximum-difference-by-remapping-a-digit/
題目描述
給你一個整數 num 。你知道 Danny Mittal 會偷偷將 0 到 9 中的一個數字 替換 成另一個數字。
請你返回將 num 中 恰好一個 數字進行替換後，得到的最大值和最小值的差位多少。
注意：
- 當 Danny 將一個數字
d1替換成另一個數字d2時，Danny 需要將nums中所有d1都替換成d2。 - Danny 可以將一個數字替換成它自己，也就是說
num可以不變。 - Danny 可以將數字分別替換成兩個不同的數字分別得到最大值和最小值。
- 替換後得到的數字可以包含前導 0 。
- Danny Mittal 獲得周賽 326 前 10 名，讓我們恭喜他。
題解（字串操作）
- 技巧：將整型轉換為字串能夠更方便地修改具體位置。
簡單模擬題，有 2 個思路：
- 思路 1 - 暴力列舉：嘗試列舉每類的數字，將其替換為
9取得最大值，將其替換為0取得最小值，最後取所有方案的最大值和最小值取差值； - 思路 2 - 貪心思路：替換越靠近 “高位” 的數字能夠使得差值越大，所以我們將從高位開始的首個非
9數字替換為9（例如90替換為99）必然得到最大值，將從高位開始的首個數字替換為0（例如90替換為00）必然得到最小值。
kotlin
// 思路 1
class Solution {
fun minMaxDifference(num: Int): Int {
val numStr = "$num"
var max = num
var min = num
for (element in numStr) {
max = Math.max(max, numStr.replace(element, '9').toInt())
min = Math.min(min, numStr.replace(element, '0').toInt())
}
return max - min
}
}
複雜度分析：
- 時間複雜度：$O(log^2\,{num})$ 數字最多有 log num 位，外層迴圈與記憶體迴圈的字串替換操作都是 $O(log\,{num})$ 時間級別複雜度；
- 空間複雜度：$O(log\,{num})$ 字串佔用空間。
kotlin
// 思路 2
class Solution {
fun minMaxDifference(num: Int): Int {
val numStr = "$num"
val min = numStr.replace(numStr[0], '0').toInt()
var max = num
for (element in numStr) {
if ('9' != element) {
max = numStr.replace(element, '9').toInt()
break
}
}
return max - min
}
}
複雜度分析：
- 時間複雜度：$O(log\,{num})$ 記憶體迴圈的字串替換操作最多隻會執行一次，均攤下來整體只有 $O(log\,{num})$ 級別的時間複雜度；
- 空間複雜度：$O(log\,{num})$ 字串佔用空間。
2567. 修改兩個元素的最小分數（Medium)
題目地址
http://leetcode.cn/problems/minimum-score-by-changing-two-elements/
題目描述
給你一個下標從 0 開始的整數陣列 nums 。
nums的 最小 得分是滿足0 <= i < j < nums.length的|nums[i] - nums[j]|的最小值。nums的 最大 得分是滿足0 <= i < j < nums.length的|nums[i] - nums[j]|的最大值。nums的分數是 最大 得分與 最小 得分的和。
我們的目標是最小化 nums 的分數。你 最多 可以修改 nums 中 2 個元素的值。
請你返回修改 nums 中 至多兩個 元素的值後，可以得到的 最小分數 。
|x| 表示 x 的絕對值。
題解（排序 + 列舉）
這道題也有腦筋急轉彎的成分，同時我們可以擴充套件思考下 “最多修改 k 個元素的最小得分” 問題，最後再說。
這道題的關鍵在於得分的定義：
- “最小得分” 表示任意陣列中兩個數字之間的最小絕對差；
- “最大得分” 表示任意陣列中兩個數字之間的最大絕對差。
理解題意後容易發現：
- 影響 “最小得分” 的是陣列中最接近的兩個數字。當陣列中存在兩個相同元素時，“最小得分” 可以取到最小值 0；
- 影響 “最大得分” 的是陣列中最不接近的兩個數，即最大值和最小值。當我們將最大值和最小值修改為陣列中間的某個元素時，能使得差值變小的同時，保持 “最小得分” 取最小值 0。
因此得知： 這道題的關鍵點在於修改陣列的最大值或最小值成為陣列中間的某個元素。 要麼讓最大值變小，要麼讓最小值變大。由於題目最多隻能修改 2 次，因此最多隻能以下 3 種情況：
- 情況 1：修改陣列中最大的兩個數為
nums[n - 3]； - 情況 2：修改陣列中最小的兩個數為
nums[2]； - 情況 3：修改陣列的最大值為
nums[n - 1]，修改陣列的最小值為nums[1]。
簡單枚舉出 3 種情況的解後再進行一輪比較即可。
最後再觀察邊界條件，陣列的最小長度為 3，所以不需要特判。
kotlin
class Solution {
fun minimizeSum(nums: IntArray): Int {
nums.sort()
val n = nums.size
val choice1 = nums[n - 3] - nums[0]
val choice2 = nums[n - 1] - nums[2]
val choice3 = nums[n - 2] - nums[1]
return Math.min(choice1, Math.min(choice2, choice3))
}
}
複雜度分析：
- 時間複雜度：$O(nlgn)$ 快速排序佔用的時間，如果手動維護最小的 3 個元素和最大的 3 個元素可以降低到 $O(n)$ 時間複雜度；
- 空間複雜度：$O(lgn)$ 排序佔用的遞迴棧空間。
再擴充套件思考一下，如果題目說明最多可以修改 $k （0 ≤ k ≤ nums.length）$次的話，應該解決問題呢？ —— 即 “求最多修改 k 個元素的最小得分”，原題就是 k = 2 的情況。
那麼這道題就是考察 “滑動視窗” 技巧了，我們可以將修改的範圍視為一個跨越陣列首尾且長度為 k 的滑動視窗，那麼而問題的答案就取決於 “不被” 滑動視窗包圍的另一部分。再逆向思考一下，我們可以用長度為 length - k 的滑動視窗在陣列上移動，並記錄視窗首尾元素的差值，列舉所有情況後記錄最小值即為最小得分：
舉個例子，在輸入陣列為 [1, 4, 5, 7, 8] ，k = 2 時，前文提到的 3 種方案分別對應以下 3 個視窗狀態：
- 情況 1：修改陣列中最大的兩個數：
1,4 | 5,7,8 | - 情況 2：修改陣列中最小的兩個數：
| 1,4,5 | 7,8 - 情況 3：修改陣列的最大值和最小值：
1 | 4,5,7 | 8
kotlin
class Solution {
fun minimizeSum(nums: IntArray): Int {
val n = nums.size
// 操作次數
val k = 2
// 滑動視窗
val len = n - k
nums.sort()
var min = Integer.MAX_VALUE
for (left in 0..n - len) {
val right = left + len - 1
min = Math.min(min, nums[right] - nums[left])
}
return min
}
}
複雜度分析同上。
2568. 最小無法得到的或值（Medium）
題目地址
http://leetcode.cn/problems/minimum-impossible-or/
題目描述
給你一個下標從 0 開始的整數陣列 nums 。
如果存在一些整數滿足 0 <= index1 < index2 < ... < indexk < nums.length ，得到 nums[index1] | nums[index2] | ... | nums[indexk] = x ，那麼我們說 x 是 可表達的 。換言之，如果一個整數能由 nums 的某個子序列的或運算得到，那麼它就是可表達的。
請你返回 nums 不可表達的 最小非零整數 。
題解一（散列表）
相似題目：2154. 將找到的值乘以 2
這道題需要腦筋急轉彎。
首先，我們先觀察輸入資料範圍中小數值的二進位制表示，嘗試發現規律：
- 0 = 0000 = 0
- 1 = 0001 = 1
- 2 = 0010 = 2
- 3 = 0011 = 2 | 1
- 4 = 0100 = 4
- 5 = 0101 = 4 | 1
- 6 = 0110 = 4 | 2
- 7 = 0111 = 4 | 2 | 1，或者 5 | 1
- 8 = 1000 = 8
- 9 = 1001 = 8 | 1
- 10 = 1010 = 8 | 2
我們發現以下 2 點資訊：
- 除了數字 7 = 5 | 1 的特殊方案外，其他數字的表示方案都可以由形如 $x = 2^i | 2^j | 2^ k$ 的格式表達（很容易理解）；
- $2^i$ 格式的數字不可能被其他數用 “或” 的形式表示（也很容易理解）。
由此可以得出結論： 影響陣列最小可表達數的關鍵在於陣列中 “未出現的最小的 $2^i$”，並且這個數就是不可表達的最小非零數。
舉例說明：假設 8 是陣列中未出現的最小 $2^i$（此時 [1, 2, 4] 肯定在陣列中出現$2^i$），那麼數字 1 ~ 7 之間的所有數字都可以由 [1、2、4] 通過或表示，而 8 無法被 [1, 2, 3, 4, 5, 6 ,7] 之間的任何數字表達，同時也無法被大於 8 的其他數表示，因此 8 就是最小的可表達數。
完成問題轉換後編碼就很容易了，我們只要從小到大列舉所有 $2^i$ ，並檢查它是否在陣列中出現即可：
kotlin
class Solution {
fun minImpossibleOR(nums: IntArray): Int {
val numSet = nums.toHashSet()
var i = 1
while (numSet.contains(i)) {
i = i shl 1
}
return i
}
}
複雜度分析：
- 時間複雜度：$O(n + logU)$ 其中 n 是陣列長度，U 是陣列的最大值，最多隻需要檢查 logU 位數字；
- 空間複雜度：$O(n)$ 散列表佔用的空間。
題解二（位運算）
題解一使用散列表來輔助判斷 $2^i$ 是否存在於陣列中，可以進一步優化：我們將直接從陣列元素的二進位制資料中提取特徵值，並還原出 “未出現的最小的 $2^i$”：
- 1、遍歷陣列中所有元素，如果元素值是 $2^i$ 則將其記錄到 mask 特徵值中；
- 2、遍歷結束後將得到形如
0011, 1011格式的特徵值，此時 “未出現的最小的 $2^i$” 正好位於從低位到高位出現的首個 0 的位置，即0000, 0100; - 3、為了還原出目標數，執行以下位運算：
kotlin
x = ~x // 按位取反： 0011,1011 => 1100,0100
x & -x // lowbit 公式：1100,0100 => 0000,0100
```kotlin class Solution { fun minImpossibleOR(nums: IntArray): Int { var mask = 0 for (x in nums) { // x & (x - 1) 將消除最低位的 1，如果消除後值為 1 說明 x 本身就是 2 的冪 if (x and (x - 1) == 0) mask = mask or x } // 取反 mask = mask.inv() // 取最低位 1 return mask and -mask } }
```
複雜度分析：
- 時間複雜度：$O(n)$ 其中 n 是陣列長度；
- 空間複雜度：$O(1)$ 僅佔用常數級別空間。
2569. 更新陣列後處理求和查詢（Hard）
題目地址
http://leetcode.cn/problems/handling-sum-queries-after-update/
題目描述
給你兩個下標從 0 開始的陣列 nums1 和 nums2 ，和一個二維陣列 queries 表示一些操作。總共有 3 種類型的操作：
- 操作型別 1 為
queries[i] = [1, l, r]。你需要將nums1從下標l到下標r的所有0反轉成1或將1反轉成0。l和r下標都從 0 開始。 - 操作型別 2 為
queries[i] = [2, p, 0]。對於0 <= i < n中的所有下標，令nums2[i] = nums2[i] + nums1[i] * p。 - 操作型別 3 為
queries[i] = [3, 0, 0]。求nums2中所有元素的和。
請你返回一個數組，包含所有第三種操作型別的答案。
預備知識
類似的區間求和問題，我們先回顧一下解決方案：
- 1、靜態陣列求區間和：「字首和陣列」、「樹狀陣列」、「線段樹」
- 2、頻繁單點更新，求區間和：「樹狀陣列」、「線段樹」
- 3、頻繁區間更新，求具體位置：「差分陣列」
- 4、頻繁區間更新，求區間和：「線段樹 + 懶更新」
這道題涉及 “區間更新” 和 “區間求和”，所以屬於線段樹的典型例題。
題解一（樸素線段樹）
我們先理解題目中三種操作的含義：
- 操作一：對
nums1陣列中位於[left, right]區間的數進行反轉，也就是進行 “區間更新”； - 操作二：將
nums1陣列上的數值nums1[index]乘以p後累加到nums2陣列的相同位置上，即nums2[index] += nums1[index] * p，同樣也是進行 “區間更新”； - 操作三：求
nums2陣列中所有元素和，即 “求區間和”。
OK，既然操作一和操作二是對不同陣列進行 “區間更新”，那麼我們需要分別為這兩個陣列建立線段樹嗎？並不需要，這是題目丟擲的煙霧彈。
因為題目最終的解是求 nums2 陣列的全體和，所以我們並不需要真正地維護 nums2 陣列，只需要將操作二的增量累加到全體和中。這樣的話就是隻需要維護 nums1 陣列的線段樹。
理解題意後，我們可以寫出題解的主框架：
- 1、首先計算
nums2陣列的初始全體和sum； - 2、建立
nums1陣列的線段樹； - 3、依次處理每種操作，操作一對線段樹做區間更新，操作二對線段樹做區間求和後乘以
p，並累加到全體和sum中，操作三將sum推入結果列表。
```kotlin
// 程式主框架
class Solution {
fun handleQuery(nums1: IntArray, nums2: IntArray, queries: Array
private class SegementTree(private val data: IntArray) {
// 區間更新（反轉）
fun update(left: Int, right: Int) {
}
// 單點更新（反轉）- 本題不需要
fun set(pos: Int) {
}
// 區間查詢
fun query(left: Int, right: Int): Int {
}
}
} ```
接下來就是實現線段樹的內部程式碼了。
- 技巧 1：這道題的更新操作是對 0/ 1 反轉，我們可以用異或來實現；
- 技巧 2：相對於在函式中重複傳遞節點所代表的區間範圍（例如
update(i: int, l: int, r: int, L: int, R: int)），使用 Node 節點記錄更為方便。
```kotlin
class Solution {
fun handleQuery(nums1: IntArray, nums2: IntArray, queries: Array
private class SegementTree(private val data: IntArray) {
// 線段樹節點（區間範圍與區間值）
private class Node(val left: Int, val right: Int, var value: Int)
// 線段樹陣列
private val tree = Array<Node?>(4 * data.size) { null } as Array<Node>
// 左子節點的索引
private val Int.left get() = this * 2 + 1
// 右子節點的索引
private val Int.right get() = this * 2 + 2
init {
// 建樹
buildNode(0, 0, data.size - 1)
}
// 構建線段樹節點
private fun buildNode(index: Int, left: Int, right: Int) {
if (left == right) {
// 葉子節點
tree[index] = Node(left, right, data[left])
return
}
val mid = (left + right) ushr 1
// 構建左子節點
buildNode(index.left, left, mid)
// 構建左子節點
buildNode(index.right, mid + 1, right)
// 合併左右子節點
tree[index] = Node(left, right, tree[index.left].value + tree[index.right].value)
}
// 區間更新（反轉）
fun update(left: Int, right: Int) {
update(0, left, right)
}
// 區間更新（反轉）
private fun update(index: Int, left: Int, right: Int) {
// 1、當前節點不處於區間範圍內
if (tree[index].left > right || tree[index].right < left) return
// 2、葉子節點
if (tree[index].left == tree[index].right) {
// 反轉：0->1,1->0
tree[index].value = tree[index].value xor 1
return
}
// 3、更新左子樹
update(index.left, left, right)
// 4、更新右子樹
update(index.right, left, right)
// 5、合併子節點的結果
tree[index].value = tree[index.left].value + tree[index.right].value
}
// 單點更新（反轉）- 本題不需要
fun set(pos: Int) {
set(0, pos)
}
// 單點更新（反轉）- 本題不需要
private fun set(index: Int, pos: Int) {
// 1、當前節點不處於區間範圍內
if (tree[index].left > pos || tree[index].right < pos) return
// 2、葉子節點
if (tree[index].left == tree[index].right) {
// 反轉：0->1,1->0
tree[index].value = tree[index].value xor 1
return
}
// 3、更新左子樹
set(index.left, pos)
// 4、更新右子樹
set(index.right, pos)
// 5、合併子節點的結果
tree[index].value = tree[index.left].value + tree[index.right].value
}
// 區間查詢
fun query(left: Int, right: Int): Int {
return query(0, left, right)
}
// 區間查詢
private fun query(index: Int, left: Int, right: Int): Int {
// 1、當前節點不處於區間範圍內
if (tree[index].left > right || tree[index].right < left) return 0
// 2、當前節點完全處於區間範圍之內
if (tree[index].left >= left && tree[index].right <= right) return tree[index].value
// 3、合併子節點的結果
return query(index.left, left, right) + query(index.right, left, right)
}
}
} ```
複雜度分析：
- 時間複雜度：$O(n + q_1n + q_2)$ 其中 n 是 nums1 陣列長度，$q_1$ 是操作一的個數，$q_2$ 是操作二的個數。我們需要花費 $O(n)$ 時間建樹，操作一線段樹區間更新的時間複雜度是 $O(n)$，操作二線段樹區間查詢的複雜度是 $O(lgn)$，但本題中的查詢正好是線段樹根節點，所以操作二實際上只需要 $O(1)$ 複雜度。
- 空間複雜度：$O(n)$ 線段樹空間。
樸素線段樹解法在本題中會超時，我們需要優化為 “懶更新” 的線段樹實現。
題解二（線段樹 + 懶更新）
樸素線段樹的效能瓶頸在於：區間更新需要改動從根節點到葉子節點中所有與目標區間有交集的節點，因此單次區間更新操作的時間複雜度是 $O(n)$。
懶更新線段樹的核心思想是：當一個節點代表的區間完全包含於目標區間內時，我們沒有必要繼續向下遞迴更新，而是在當前節點上標記 Lazy Tag 。只有將來更新該節點的某個子區間時，才會將懶更新 pushdown 到子區間。
舉個例子：在長度為 10 的線段樹中執行 [1,10] 和 [1,5] 兩次區間更新操作（對區間內的元素加一）：
[1,10]區間更新：從根節點出發，此時發現根節點與目標區間[1,10]完全相同，那麼只更新根節點並標記 Lazy Tag，更新結束；[1,5]區間更新：從根節點出發，此時發現根節點有 Lazy Tag，那麼需要先將懶更新 pushdown 到[1,5]和[6,10]兩個子節點，然後再更新[1,5]區間。- 到目前為止，
[1,10]和[1,5]節點被修改 2 次，[6,10]節點被修改 1 次，其它節點沒有被修改。
接下來就是實現線段樹的內部程式碼了。
- 技巧 1：0 /1 反轉是負負得正的，所以 Lazy Tag 可以用
Boolean型別表示，true表示被反轉； - 技巧 2：區間反轉可以用區間長度 - 舊值實現，即：
value = right - left + 1 - value。
提示：相比題解一改動的函式有 【懶更新】 標記 。
```kotlin
class Solution {
fun handleQuery(nums1: IntArray, nums2: IntArray, queries: Array
private class LazySegementTree(private val data: IntArray) {
// 線段樹節點（區間範圍與區間值）【懶更新】
private class Node(val left: Int, val right: Int, var value: Int, var lazy: Boolean = false)
// 線段樹陣列
private val tree = Array<Node?>(4 * data.size) { null } as Array<Node>
// 左子節點的索引
private val Int.left get() = this * 2 + 1
// 右子節點的索引
private val Int.right get() = this * 2 + 2
init {
// 建樹
buildNode(0, 0, data.size - 1)
}
// 構建線段樹節點
private fun buildNode(index: Int, left: Int, right: Int) {
if (left == right) {
// 葉子節點
tree[index] = Node(left, right, data[left])
return
}
val mid = (left + right) ushr 1
// 構建左子節點
buildNode(index.left, left, mid)
// 構建左子節點
buildNode(index.right, mid + 1, right)
// 合併左右子節點
tree[index] = Node(left, right, tree[index.left].value + tree[index.right].value)
}
// 區間更新（反轉）
fun update(left: Int, right: Int) {
update(0, left, right)
}
// 區間更新（反轉）【懶更新】
private fun update(index: Int, left: Int, right: Int) {
// 1、當前節點不處於區間範圍內
if (tree[index].left > right || tree[index].right < left) return
// 2、當前節點完全處於區間範圍之內
if (tree[index].left >= left && tree[index].right <= right) {
lazyUpdate(index)
return
}
// 3、pushdown 到子節點
if (tree[index].lazy) {
lazyUpdate(index.left)
lazyUpdate(index.right)
tree[index].lazy = false
}
// 4、更新左子樹
update(index.left, left, right)
// 5、更新右子樹
update(index.right, left, right)
// 6、合併子節點的結果
tree[index].value = tree[index.left].value + tree[index.right].value
}
// 單點更新（反轉）- 本題不需要
fun set(pos: Int) {
set(0, pos)
}
// 單點更新（反轉）【懶更新】- 本題不需要
private fun set(index: Int, pos: Int) {
// 1、當前節點不處於區間範圍內
if (tree[index].left > pos || tree[index].right < pos) return
// 2、葉子節點
if (tree[index].left == tree[index].right) {
lazyUpdate(index)
return
}
// 3、pushdown 到子節點
if (tree[index].lazy) {
lazyUpdate(index.left)
lazyUpdate(index.right)
tree[index].lazy = false
}
// 4、更新左子樹
set(index.left, pos)
// 5、更新右子樹
set(index.right, pos)
// 6、合併子節點的結果
tree[index].value = tree[index.left].value + tree[index.right].value
}
// 區間查詢
fun query(left: Int, right: Int): Int {
return query(0, left, right)
}
// 區間查詢
private fun query(index: Int, left: Int, right: Int): Int {
// 1、當前節點不處於區間範圍內
if (tree[index].left > right || tree[index].right < left) return 0
// 2、當前節點完全處於區間範圍之內
if (tree[index].left >= left && tree[index].right <= right) return tree[index].value
// 3、pushdown 到子節點
if (tree[index].lazy) {
lazyUpdate(index.left)
lazyUpdate(index.right)
tree[index].lazy = false
}
// 4、合併子節點的結果
return query(index.left, left, right) + query(index.right, left, right)
}
// 懶更新
private fun lazyUpdate(index: Int) {
// 反轉
tree[index].value = tree[index].right - tree[index].left + 1 - tree[index].value
// 標記（負負得正）
tree[index].lazy = !tree[index].lazy
}
}
} ```
複雜度分析：
- 時間複雜度：$O(n + q_1lgn + q_2)$ 其中 n 是 nums1 陣列長度，$q_1$ 是操作一的個數，$q_2$ 是操作二的個數。
- 空間複雜度：$O(n)$ 線段樹空間。
我們下週見，有用請點贊關注！
本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 提問。
- LeetCode 周賽 336，多少人直接 CV？
- LeetCode 周賽 335，純純手速場！
- LeetCode 雙週賽 98，腦筋急轉彎轉不過來！
- Android IO 框架 Okio 的實現原理，到底哪裡 OK？
- 12 張圖看懂 CPU 快取一致性與 MESI 協議，真的一致嗎？
- Android 序列化框架 Gson 原理分析，可以優化嗎？
- 為什麼計算機中的負數要用補碼錶示？
- 什麼是二叉樹？
- 我把 CPU 三級快取的祕密，藏在這 8 張圖裡
- 全網最全的 ThreadLocal 原理詳細解析 —— 原理篇
- 程式設計師學習 CPU 有什麼用？
- WeakHashMap 和 HashMap 的區別是什麼，何時使用？
- 萬字 HashMap 詳解，基礎（優雅）永不過時 —— 原理篇
- Java 面試題：說一下 ArrayDeque 和 LinkedList 的區別?
- Java 面試題：說一下 ArrayList 和 LinkedList 的區別？
- Java 面試題：ArrayList 可以完全替代陣列嗎？
- 已經有 MESI 協議，為什麼還需要 volatile 關鍵字？
- JVM 系列（6）吊打面試官：為什麼 finalize() 方法只會執行一次？
- 使用字首和陣列解決"區間和查詢"問題
- NDK 系列（5）：JNI 從入門到實踐，萬字爆肝詳解！