大家好，我是小彭。
前天剛舉辦 2023 年力扣杯個人 SOLO 賽，昨天周賽就出了一場 Easy - Easy - Medium - Medium 的水場，不得不說 LeetCode 是懂禮數的 。
接下來，請你跟着小彭的思路，一步步将問題做難，再将問題做簡單。
往期回顧：LeetCode 單周賽 341 · 難度上來了，圖論的問題好多啊！
LeetCode 周賽 342 概覽
Q1. 計算列車到站時間（Easy）
簡單模拟題，不多講解。
Q2. 倍數求和（Easy）
題解 1：暴力解法 O(n) 時間複雜度
題解 2：分析資料特征後發現資料存在等差數列性質，我們利用容斥原理和等差數列求和公式，可以把優化到 O(1) 時間複雜度
Q3. 滑動子數組的美麗值（Medium）
題解 1：在滑動視窗的基礎上，結合快速選擇查找滑動視窗中第 x 小的元素，時間複雜度是 O(n·k)
題解 2：分析資料特征後發現題目的值域非常小，我們可以用計數排序代替快速選擇，時間複雜度為 O(n·U)
Q4. 使數組所有元素變成 1 的最少操作次數（Medium）
在問題分析後我們将原問題抽象為 “尋找 GCB 為 1 的最短子數組”，關聯相似的 “和為 k 的最短子數組” 問題，我們有從暴力 → 有序集合 → 單調性優化的解法：
題解 1：暴力 O(n·(n + logU)) 時間複雜度
題解 2：有序集合 O(n·lgU·lg(lgU)) 時間複雜度
題解 3：單調性優化 O(n·lgU) 時間複雜度
Q1. 計算列車到站時間（Easy）
題目位址
https://leetcode.cn/problems/calculate-delayed-arrival-time/
題目描述
給你一個正整數 arrivalTime 表示列車正點到站的時間（機關：小時），另給你一個正整數 delayedTime 表示列車延誤的小時數。
傳回列車實際到站的時間。
注意，該問題中的時間采用 24 小時制。
示例 1：
輸入：arrivalTime = 15, delayedTime = 5
輸出：20
解釋：列車正點到站時間是 15:00 ，延誤 5 小時，是以列車實際到站的時間是 15 + 5 = 20（20:00）。
示例 2：
輸入：arrivalTime = 13, delayedTime = 11
輸出：0
解釋：列車正點到站時間是 13:00 ，延誤 11 小時，是以列車實際到站的時間是 13 + 11 = 24（在 24 小時制中表示為 00:00 ，是以傳回 0）。
提示：
- 1 <= arrivaltime < 24
- 1 <= delayedTime <= 24
題解（模拟）
簡單模拟題，按題意實作即可。
class Solution {
fun findDelayedArrivalTime(arrivalTime: Int, delayedTime: Int): Int {
return (arrivalTime + delayedTime) % 24
}
}
複雜度分析：
- 時間複雜度：O(1)
- 空間複雜度：O(1)
Q2. 倍數求和（Easy）
題目位址
https://leetcode.cn/problems/sum-multiples/
題目描述
給你一個正整數 n ，請你計算在 [1，n] 範圍内能被 3、5、7 整除的所有整數之和。
傳回一個整數，用于表示給定範圍内所有滿足限制條件的數字之和。
示例 1：
輸入：n = 7
輸出：21
解釋：在[1, 7] 範圍内能被 3、5、7 整除的所有整數分别是 3、5、6、7 。數字之和為21 。
示例 2：
輸入：n = 10
輸出：40
解釋：在[1, 10] 範圍内能被 3、5、7 整除的所有整數分别是 3、5、6、7、9、10 。數字之和為40 。
示例 3：
輸入：n = 9
輸出：30
解釋：在[1, 9] 範圍内能被 3、5、7 整除的所有整數分别是 3、5、6、7、9 。數字之和為30 。
提示：
- 1 <= n <= 103
預備知識 - 容斥原理
定義集合 A 表示能夠被 3 整除的數，定義集合 B 表示能夠被 5 整除的數，定義集合 C 表示能夠被 7 整除的數。如果把這 3 個集合直接加起來，會多出來一些元素重複統計了，是以需要扣除 A ∩ B，A ∩ C 和 B ∩ C ，但是又有一小部分元素多扣了，反而再需要加上 A ∩ B ∩ C。這就是 容斥原理：
A ∪ B ∪ C = A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
其中：
- A ∪ B ∪ C 表示能夠被 3 或 5 或 7 整除的數，也就是原問題的解；
- A ∩ B 表示能夠同時被 3 和 5 整除的數；
- A ∩ C 表示能夠同時被 3 和 7 整除的數；
- B ∩ C 表示能夠同時被 5 和 7 整除的數。
預備知識 - 等差數列求和
- 等差數列求和公式：(首項 + 尾項) * 項數 / 2
題解一（暴力）
先思考暴力解法：
算法：枚舉每個數，檢查該數字是否為 3 / 5 / 7 的倍數，是則計入結果中。
class Solution {
fun sumOfMultiples(n: Int): Int {
var ret = 0
for (i in 1 .. n) {
if(i % 3 == 0 || i % 5 == 0 || i % 7 == 0) ret += i
}
return ret
}
}
複雜度分析：
- 時間複雜度：O(n) 其中 n 為 nums 數組的長度，每個元素最多通路 1 次；
- 空間複雜度：O(1)
題解二（容斥原理 + 等差數列求和公式）
暴力解法是否有優化空間呢，先分析重複計算：
- 要點 1：可以觀察到 [1, n] 範圍中的目标數是存在關聯的，以 3 的倍數為例，3、6、9、12 是以 3 為等差的等差數列，而等差數列的和可以使用公式計算。數字 m 在 [1, n] 範圍内中的倍數為 n / m 個，可以使用等差數列求和公式以 O(1) 算出這部分元素之和；
- 要點 2：結合容斥原理，可以在 O(1) 時間複雜度求出原問題。那麼能夠同時被 3 和 5 整除的等差數列如何計算呢？其實就是計算 15 的倍數。同理能夠同時被 3 和 5 和 7 整除的等差數列就是 105 的倍數。
至此，結合容斥原理模拟即可：
class Solution {
fun sumOfMultiples(n: Int): Int {
return sum(n, 3) + sum(n, 5) + sum(n, 7) - sum(n, 15) - sum(n, 21) - sum(n, 35) + sum(n, 105)
}
private fun sum(n:Int, k:Int) :Int {
// 等差數列求和公式：(首項 + 尾項) * 項數 / 2
return (k + (n / k * k)) * (n / k) / 2
}
}
複雜度分析：
- 時間複雜度：O(1)
- 空間複雜度：O(1)
Q3.滑動子數組的美麗值（Medium）
題目位址
https://leetcode.cn/problems/sliding-subarray-beauty/description/
題目描述
給你一個長度為 n 的整數數組 nums ，請你求出每個長度為 k 的子數組的 美麗值 。
一個子數組的 美麗值 定義為：如果子數組中第 x 小整數 是 負數 ，那麼美麗值為第 x 小的數，否則美麗值為 0 。
請你傳回一個包含 n - k + 1 個整數的數組，依次** 表示數組中從第一個下标開始，每個長度為 k 的子數組的 美麗值 。
- 子數組指的是數組中一段連續 非空 的元素序列。
示例 1：
輸入：nums = [1,-1,-3,-2,3], k = 3, x = 2
輸出：[-1,-2,-2]
解釋：總共有 3 個 k = 3 的子數組。
第一個子數組是[1, -1, -3] ，第二小的數是負數 -1 。
第二個子數組是[-1, -3, -2] ，第二小的數是負數 -2 。
第三個子數組是[-3, -2, 3] ，第二小的數是負數 -2 。
示例 2：
輸入：nums = [-1,-2,-3,-4,-5], k = 2, x = 2
輸出：[-1,-2,-3,-4]
解釋：總共有 4 個 k = 2 的子數組。
[-1, -2] 中第二小的數是負數 -1 。[-2, -3] 中第二小的數是負數 -2 。[-3, -4] 中第二小的數是負數 -3 。[-4, -5] 中第二小的數是負數 -4 。
示例 3：
輸入：nums = [-3,1,2,-3,0,-3], k = 2, x = 1
輸出：[-3,0,-3,-3,-3]
解釋：總共有 5 個 k = 2 的子數組。
[-3, 1] 中最小的數是負數 -3 。[1, 2] 中最小的數不是負數，是以美麗值為 0 。[2, -3] 中最小的數是負數 -3 。[-3, 0] 中最小的數是負數 -3 。[0, -3] 中最小的數是負數 -3 。
提示：
- n == nums.length
- 1 <= n <= 105
- 1 <= k <= n
- 1 <= x <= k
- 50 <= nums[i] <= 50
預備知識
求出每個長度為 k 的子數組的美麗值，容易想到可以用滑動視窗。
僞代碼為：
// 僞代碼
for (i in 0 until n) {
// 進入視窗
list.add(i)
// 離開視窗
if (i >= k) list.remove(i - k)
if (i >= k - 1) {
// 計算視窗答案
}
}
題解一（滑動視窗 + 快速選擇 · 超出時間限制）
在滑動視窗的基礎上，使用快速選擇查找視窗中第 x 小的數：
class Solution {
private val random = Random(0)
fun getSubarrayBeauty(nums: IntArray, k: Int, x: Int): IntArray {
val n = nums.size
val ret = LinkedList<Int>()
val list = ArrayList<Int>()
for (i in 0 until n) {
// 進入視窗
list.add(i)
// 離開視窗
if (i >= k) list.remove(i - k)
if (i >= k - 1) {
// 計算視窗答案
quickSelect(nums, list, x)
val num = nums[list[x - 1]]
ret.add(if (num < 0) num else 0)
}
}
return ret.toIntArray()
}
private fun quickSelect(nums: IntArray, list: ArrayList<Int>, x: Int) {
val target = x - 1
var left = 0
var right = list.size - 1
while (left < right) {
val pivot = partition(nums, list, left, right)
if (pivot == target) {
return
} else if (pivot < target) {
left = pivot + 1
} else {
right = pivot - 1
}
}
}
private fun partition(nums: IntArray, list: ArrayList<Int>, left: Int, right: Int): Int {
val random = random.nextInt(right - left + 1) + left
list.swap(random, right)
var p = left
for (i in left until right) {
if (nums[list[i]] < nums[list[right]]) list.swap(i, p++)
}
list.swap(p, right)
return p
}
private fun ArrayList<Int>.swap(i: Int, j: Int) {
val temp = this[i]
this[i] = this[j]
this[j] = temp
}
}
複雜度分析：
- 時間複雜度：O(n·k) 其中 n 是 nums 數組的長度，單次視窗快速選擇的時間複雜度是 O(k)；
- 空間複雜度：O(k) 滑動視窗空間。
題解二（滑動視窗 + 計數排序）
注意到題目的值域非常小，能否利用起來：
我們可以用計數排序代替快速選擇，用 cnts 計數數組計算視窗内每個元素的出現次數，再根據計數數組計算出第 x 小的數：
class Solution {
private val random = Random(0)
fun getSubarrayBeauty(nums: IntArray, k: Int, x: Int): IntArray {
val n = nums.size
val OFFSET = 50
val cnts = IntArray(OFFSET * 2 + 1)
val ret = IntArray(n - k + 1)
outer@ for (i in 0 until n) {
// 進入視窗
cnts[OFFSET + nums[i]]++
// 離開視窗
if (i >= k) cnts[OFFSET + nums[i - k]]--
if (i >= k - 1) {
// 計算視窗美麗值
var count = x
// for (num in -OFFSET .. -1) {
for (num in -OFFSET .. OFFSET) {
count -= cnts[num + 50]
if (count <= 0) {
// 找到第 x 小的數
// ret[i - k + 1] = num
ret[i - k + 1] = if(num < 0) num else 0
continue@outer
}
}
}
}
return ret
}
}
另外，由于題目要求美麗值是負數，是以在計算視窗美麗值時，我們隻需要枚舉 [-50, -1] 的元素值。
複雜度分析：
- 時間複雜度：O(n·U) 其中 n 是 nums 數組的長度，U 是值域大小 101。每次滑動視窗求第 x 小的元素時間是 O(U)；
- 空間複雜度：O(U) 計數數組空間。
Q4. 使數組所有元素變成 1 的最少操作次數（Medium）
題目位址
https://leetcode.cn/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/description/
題目描述
給你一個下标從 0 開始的 正 整數數組 nums 。你可以對數組執行以下操作 任意 次：
- 選擇一個滿足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 兩者之一替換成它們的最大公約數。
請你傳回使數組 nums 中所有元素都等于 1 的 最少 操作次數。如果無法讓數組全部變成 1 ，請你傳回 -1 。
兩個正整數的最大公約數指的是能整除這兩個數的最大正整數。
示例 1：
輸入：nums = [2,6,3,4]
輸出：4
解釋：我們可以執行以下操作：
- 選擇下标 i = 2 ，将 nums[2] 替換為 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
- 選擇下标 i = 1 ，将 nums[1] 替換為 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
- 選擇下标 i = 0 ，将 nums[0] 替換為 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
- 選擇下标 i = 2 ，将 nums[3] 替換為 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。
示例 2：
輸入：nums = [2,10,6,14]
輸出：-1
解釋：無法将所有元素都變成 1 。
提示：
- 2 <= nums.length <= 50
- 1 <= nums[i] <= 106
問題分析
分析目标結果：
使得數組中所有元素都變成 1 的最少操作次數。
分析題目示例：
- 由于在每次操作中最多隻能将一個數字修改為最大公約數，那麼将 1 個元素操作為 “1” 的最小操作次數（如果可行）不會低于 1 次，将 n 個大于 1 的元素操作為 “1” 的最小次數不會低于 n 次，例如樣例 [2,6,1,4]。
- 如果數組中至少存在 1 個 “1” 時，我們隻需要将每個 “1” 與相鄰的 “非 1” 元素組合操作，就能将所有元素，例如樣例 [2,6,1,4]。這說明，問題的最小操作次數正好就是數組中不是 “1” 的個數。
- 如果數組中不存在 “1”，需要先操作出原始的 “1”：如果數組中所有元素的最大公約數大于 1，那麼無論如何也無法操作出數字 1，例如樣例 [2, 10, 6, 14]；否則，我們總可以操作 x 次獲得原始 “1”，那麼問題就等于 count + n - 1；
至此，程式整體架構确定。僞代碼為：
if (所有元素的最大公約數 > 1) return -1
if (1 的個數 > 0) return n - (1 的個數)
操作 count 次得到原始的 “1”
return count + n - 1
接下來，我們需要思考如何計算出操作出原始 “1” 的最小次數：
回歸到原問題操作，我們在每次操作中可以将一個數修改為最大公約數，那麼對于連續的一段子數組（長度為 subSize），我們總可以用 subSize - 1 次操作将其中一個數變為整個子數組的最大公約數。如果這個最大公約數是 1，那麼操作次數正好是 subSize - 1，反之無法操作出 1。
至此，可以想出暴力解法：
題解一（暴力枚舉子數組）
在暴力解法中，我們枚舉所有子數組，記錄出所有子數組操作出原始 “1” 的最少操作次數。
class Solution {
fun minOperations(nums: IntArray): Int {
val n = nums.size
// 1 的個數
var cnt1 = 0
var gcbAll = 0
for (x in nums) {
gcbAll = gcb(gcbAll, x)
if (x == 1) cnt1++
}
// 所有數的最大公約數大于 1
if (gcbAll > 1) return -1
// 1 的個數大于 0
if (cnt1 > 0) return n - cnt1
// 操作出原始 “1” 的最小次數
var minCount = n
// 枚舉子數組
for (i in 0 until n) {
var gcb = 0
for (j in i until n) {
gcb = gcb(gcb, nums[j])
if (gcb == 1) {
minCount = Math.min(minCount, j - i /* 子數組長度 - 1 */)
break // 繼續枚舉 i 為起點的子數組不會得到更優解
}
}
}
return minCount + n - 1
}
// 求 x 和 y 的最大公約數（輾轉相除法）
private fun gcb(x: Int, y: Int): Int {
var a = x
var b = y
while (b != 0) {
val temp = a % b
a = b
b = temp
}
return a
}
}
複雜度分析：
- 時間複雜度：O(n·(n + logU)) 其中 n 是 nums 數組的長度，U 是數組元素的最大值。單次 GCD 計算的時間複雜度是 O(logU)，乍看起來算法整體的時間複雜度是 O(n^2·logU)，其實不對。因為在每層循環中，每次 GCD 計算并不是獨立的，而是貫穿整個内層循環的，是以 GCD 的總時間取決于資料的最大值 U，在輾轉相除中取餘的次數也取決于 U。
- 空間複雜度：O(1) 不考慮結果數組，僅使用常量級别空間。
題解一的複雜度是平方級别的，如果放大題目資料量到 10^5 要怎麼做？
問題抽象
在分析暴力解法的重複計算之前，我先向你抛出一個 “題外話”：
請你回答：“給定一個整數數組 nums 和目标和 k，如何求和為 k 的最短子數組？”
- 解法 1：暴力枚舉所有子數組，記錄出所有子數組和為 k 的最短子數組長度（這與題解一暴力枚舉子數組求操作出原始 “1” 的最少操作次數類似）；
- 解法 2：我們從左向右線性周遊，并維護以 num[j] 為右端點的字首和映射表 。在此基礎上，我們将目前位置 nums[i] 的字首和與字首和映射表中的每個元素取內插補點，就可以快速地獲得以 num[i] 為右端點所有子數組的和。另外，由于我們是從左向右周遊的，是以字首和映射表記錄的索引正好是可以構造最短子數組的索引，子數組長度為 i - j + 1（當然，我們可以直接 O(1) 查詢目标字首和出現時的索引，而不需要真的用字首和映射表的每個元素取內插補點）。
注：這個 “題外話” 與 LeetCode 560. 和為 K 的子數組 類似，如果你不熟悉可以先做做看。
那麼，這個 “題外話” 與今天這道題有什麼關系：
根據 GCB 運算的性質，當我們以 nums[i] 為左端點，不斷向右擴充子數組的右端點時，我們的目标是求 “GCB 為 1 的子數組” 對吧。與 “求和為 k 的最短子數組” 類似，我們可以維護以 nums[j] 為左端點的 GCB 映射表 <gcb to 左端點 index>。在此基礎上，我們将目前位置 nums[i] 與 GCB 映射表中的每個元素取 GCB，就可以快速的獲得以 nums[i] 為右端點的所有子數組的 GCB。
那聽起來這個算法依然是 O(n^2)？不對。
原因在題解一的時間複雜度分析中講到了，因為每次 GCD 計算并不是獨立的，而是貫穿整個循環的，GCB 映射表的大小取決于資料的最大值 U，而不是資料量，最多有 logU 種 GCB。是以優化後算法的時間複雜度是 O(n·lgU)，但增加了空間複雜度為 O(lgU)。
示意圖
題解二（有序集合）
至此，在題解一的基礎上修改 “枚舉子數組計算操作出原始 “1” 的最小次數” 不分代碼即可：
class Solution {
fun minOperations(nums: IntArray): Int {
// 略...
// 計算操作出原始 “1” 的最小次數
var minCount = n
// gcb 散清單 <gcd to 左端點 index>
var gcbMap = TreeMap<Int, Int>()
// 枚舉子數組
for (i in 0 until n) {
val newGcbMap = TreeMap<Int, Int>()
// 枚舉 gcb 映射表
for ((gcb, index) in gcbMap) {
newGcbMap[gcb(gcb, nums[i])] = index
}
newGcbMap[nums[i]] = i
// 檢查最小的 gcb 是否為 1
val minEntry = newGcbMap.firstEntry()
if (1 == minEntry.key) {
minCount = Math.min(minCount, i - minEntry.value /* 子數組長度 - 1 */)
}
gcbMap = newGcbMap
}
return minCount + n - 1
}
// 求 x 和 y 的最大公約數
private fun gcb(x: Int, y: Int): Int {
// 略...
}
}
複雜度分析：
- 時間複雜度：O(n·lgU·lg(lgU)) 由于使用了有序集合，是以每一輪疊代中要算上排序時間 O(lgU·lg(lgU))；
- 空間複雜度：O(lgU) GCB 映射表空間。
題解三（單調性優化）
思路參考：靈茶山艾府的題解
題解二的時間複雜度比我們分析的複雜度略要一些，如何尋找優化空間？
繼續分析 GCB 的資料特征，可以發現：當我們從左向右周遊時，随着子數組的長度增大，子數組的 GCB 要麼不變，要麼變小，存在 單調性。 是以，我們并不需要維護有序集合，GCB 清單中最靠前的元素一定是最小的 GCB。
class Solution {
fun minOperations(nums: IntArray): Int {
// 略...
// 計算操作出原始 “1” 的最小次數
var minCount = n
// gcb 清單 <gcd to 左端點 index>
var gcbs = ArrayList<IntArray>()
// 枚舉子數組
for (i in 0 until n) {
val newGcbs = ArrayList<IntArray>()
// 枚舉 gcb 清單
for (element in gcbs) {
val gcb = gcb(element[0], nums[i])
if (newGcbs.isEmpty() || newGcbs[newGcbs.size - 1][0] != gcb) {
// 增加 GCB
newGcbs.add(intArrayOf(gcb, element[1]))
} else {
// 原地去重
newGcbs[newGcbs.size - 1][1] = element[1]
}
}
newGcbs.add(intArrayOf(nums[i], i))
// 檢查最小的 gcb 是否為 1
val minEntry = newGcbs[0]
if (1 == minEntry[0]) {
minCount = Math.min(minCount, i - minEntry[1] /* 子數組長度 - 1 */)
}
gcbs = newGcbs
}
return minCount + n - 1
}
// 求 x 和 y 的最大公約數
private fun gcb(x: Int, y: Int): Int {
// 略...
}
}
複雜度分析：
- 時間複雜度：O(n·lgU)
- 空間複雜度：O(lgU)
相似題目：
- 560. 和為 K 的子數組
- 898. 子數組按位或操作
- 1521. 找到最接近目标值的函數值