大家好，我是小彭遇伞。
今天是 LeetCode 第 334 場周賽辙喂，你參加了嗎？這場周賽考察范圍比較基礎(chǔ)，整體難度比較平均巍耗，第一題難度偏高秋麸，第四題需要我們在算法里實現(xiàn) “反復(fù)橫跳”，非常有意思炬太。
2574. 左右元素和的差值（Easy）
題目地址
https://leetcode.cn/problems/left-and-right-sum-differences/
題目描述
給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 nums 灸蟆，請你找出一個下標(biāo)從 0 開始的整數(shù)數(shù)組 answer ，其中：
answer.length == nums.lengthanswer[i] = |leftSum[i] - rightSum[i]|
其中：
-
leftSum[i]是數(shù)組nums中下標(biāo)i左側(cè)元素之和亲族。如果不存在對應(yīng)的元素炒考，leftSum[i] = 0。 -
rightSum[i]是數(shù)組nums中下標(biāo)i右側(cè)元素之和孽水。如果不存在對應(yīng)的元素票腰，rightSum[i] = 0。
返回數(shù)組 answer 女气。
題解
簡單模擬題杏慰，使用兩個變量記錄前后綴和。
class Solution {
fun leftRigthDifference(nums: IntArray): IntArray {
var preSum = 0
var sufSum = nums.sum()
val n = nums.size
val result = IntArray(n)
for (index in nums.indices) {
sufSum -= nums[index]
result[index] = Math.abs(preSum - sufSum)
preSum += nums[index]
}
return result
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
炼鞠。
- 空間復(fù)雜度：
缘滥，不考慮結(jié)果數(shù)組。
2575. 找出字符串的可整除數(shù)組（Medium）
題目地址
https://leetcode.cn/problems/find-the-divisibility-array-of-a-string/
題目描述
給你一個下標(biāo)從 0 開始的字符串 word 谒主，長度為 n 朝扼，由從 0 到 9 的數(shù)字組成。另給你一個正整數(shù) m 霎肯。
word 的 可整除數(shù)組 div 是一個長度為 n 的整數(shù)數(shù)組擎颖，并滿足：
- 如果
word[0,...,i]所表示的 數(shù)值 能被m整除，div[i] = 1 - 否則观游，
div[i] = 0
返回 word 的可整除數(shù)組搂捧。
題解
這道題主要靠大數(shù)處理。
將前綴字符串 [0, i] 轉(zhuǎn)換為有 2 種方式：
- 1懂缕、使用
String#substring(0, i + 1)裁剪子串允跑，再轉(zhuǎn)換為數(shù)字； - 2搪柑、使用
前綴 * 10 + word[i]逐位計算聋丝。
但是，這 2 種方式在大數(shù) case 中會遇到整型溢出變?yōu)樨?fù)數(shù)工碾，導(dǎo)致判斷出錯的情況弱睦，我們想辦法保證加法運算不會整型溢出。我們發(fā)現(xiàn)： 在處理完 [i - 1] 位置后倚喂，不必記錄 [0, i-1] 的整段前綴每篷，而僅需要記錄前綴對 m 的取模結(jié)果瓣戚。
例如當(dāng) m 為 3 時，“11 * 10 + 1 = 111” 與 “(11 % 3) * 10 + 1 = 21” 都能夠?qū)?3 整除焦读。也可以這樣理解：前綴中能被 m 整除的加法因子在后續(xù)運算中乘以 10 后依然能夠被 m 整數(shù)子库，所以這部分加法因子應(yīng)該盡早消掉。
另外還有一個細(xì)節(jié)：由于 m 的最大值是 矗晃，前綴的取模結(jié)果的最大值為
仑嗅，而當(dāng)前位置的最大值是 9，加法后依然會溢出张症，因此我們要用 Long 記錄當(dāng)前位置仓技。
class Solution {
fun divisibilityArray(word: String, m: Int): IntArray {
val n = word.length
val div = IntArray(n)
var num = 0L
for (index in word.indices) {
num = num * 10 + (word[index] - '0')
num %= m
if (num == 0L) div[index] = 1
}
return div
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
2576. 求出最多標(biāo)記下標(biāo)（Medium）
題目地址
https://leetcode.cn/problems/find-the-maximum-number-of-marked-indices/
題目描述
給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 nums 。
一開始兆衅，所有下標(biāo)都沒有被標(biāo)記地沮。你可以執(zhí)行以下操作任意次：
- 選擇兩個 互不相同且未標(biāo)記 的下標(biāo)
i和j，滿足2 * nums[i] <= nums[j]羡亩，標(biāo)記下標(biāo)i和j摩疑。
請你執(zhí)行上述操作任意次，返回 nums 中最多可以標(biāo)記的下標(biāo)數(shù)目畏铆。
題解（排序 + 貪心 + 雙指針）
這道題的難度是找到貪心規(guī)律雷袋。
題目要求：選擇兩個互不相同且未標(biāo)記的下標(biāo) i 和 j ，滿足 2 * nums[i] <= nums[j] 辞居，標(biāo)記下標(biāo) i 和 j 楷怒。我們發(fā)現(xiàn)題目并不關(guān)心 [i] 和 [j] 的選擇順序，所以對排序不會影響問題結(jié)果瓦灶，而且排序能夠更方便地比較元素大小率寡，因此題目的框架應(yīng)該是往 排序 + [貪心 / 雙指針 / 二分 / DP] 的思路思考。
比賽過程中的思考過程記錄下來：
- 嘗試 1 - 排序 + 貪心雙指針：nums[i] 優(yōu)先使用最小值倚搬，nums[j] 優(yōu)先使用最大值，錯誤用例：[1 2 3 6]乾蛤；
- 嘗試 2 - 排序 + 貪心：nums[i] 優(yōu)先使用最小值每界，nums[j] 使用大于 nums[i] 的最小值，錯誤用例：[1 2 4 6]家卖；
- 嘗試 3- 排序 + 貪心：從后往前遍歷眨层，nums[i] 優(yōu)先使用較大值，nums[j] 使用大于 nums[i] 的最小值上荡，錯誤用例：[2 3 4 8]趴樱。
陷入僵局……
開始轉(zhuǎn)換思路：能否將數(shù)組拆分為兩部分馒闷，作為 nums[i] 的分為一組，作為 nums[j] 的分為一組叁征。 例如纳账，在用例 [1 2 | 3 6] 和 [1 2 | 4 6] 和 [2 3 | 4 8]中，將數(shù)組的前部分作為 nums[i] 而后半部分作為 nums[j] 時捺疼，可以得到最優(yōu)解疏虫，至此發(fā)現(xiàn)貪心規(guī)律。
設(shè)數(shù)組的長度為 n啤呼，最大匹配對數(shù)為 k卧秘。
- 貪心規(guī)律 1：從小到大排序后，使用數(shù)組的左半部分作為
nums[i]且使用數(shù)組的右半部分作為nums[j]總能取到最優(yōu)解官扣。反之翅敌，如果使用右半部分的某個數(shù)nums[t]作為nums[i]，相當(dāng)于占用了一個較大的數(shù)惕蹄，不利于后續(xù)nums[i]尋找配對蚯涮。
將數(shù)組拆分為兩部分后：
- 貪心規(guī)律 2：從小到大排序后，當(dāng)固定
nums[i]時焊唬，nums[j]越小越好恋昼，否則會占用一個較大的位置，不利于后續(xù)nums[i]尋找配對赶促。因此最優(yōu)解一定是使用左半部分的最小值與右半部分的最小值配對液肌。
可以使用雙指針求解：
class Solution {
fun maxNumOfMarkedIndices(nums: IntArray): Int {
nums.sort()
val n = nums.size
var count = 0
var j = (n + 1) / 2
outer@ for (i in 0 until n / 2) {
while (j < n) {
if (nums[i] * 2 <= nums[j++]) {
count += 2
continue@outer
}
}
}
return count
}
}
簡化寫法：
class Solution {
fun maxNumOfMarkedIndices(nums: IntArray): Int {
nums.sort()
val n = nums.size
var i = 0
for (j in (n + 1) / 2 until n) {
if (2 * nums[i] <= nums[j]) i++
}
return i * 2
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
其中
為
數(shù)組長度，排序時間
鸥滨，雙指針遍歷時間
- 空間復(fù)雜度：
排序遞歸棧空間婿滓。
2577. 在網(wǎng)格圖中訪問一個格子的最少時間（Hard）
題目地址
https://leetcode.cn/problems/minimum-time-to-visit-a-cell-in-a-grid/
題目描述
給你一個 m x n 的矩陣 grid 老速，每個元素都為 非負(fù) 整數(shù)，其中 grid[row][col] 表示可以訪問格子 (row, col) 的 最早 時間凸主。也就是說當(dāng)你訪問格子 (row, col) 時橘券，最少已經(jīng)經(jīng)過的時間為 grid[row][col] 。
你從 最左上角 出發(fā)卿吐，出發(fā)時刻為 0 旁舰，你必須一直移動到上下左右相鄰四個格子中的 任意 一個格子（即不能停留在格子上）。每次移動都需要花費 1 單位時間嗡官。
請你返回 最早 到達(dá)右下角格子的時間箭窜，如果你無法到達(dá)右下角的格子，請你返回 -1 衍腥。
前置知識
這道題是單源正權(quán)最短路的衍生問題磺樱，先回顧以一下類似的最短路問題解決方案：
- Dijkstra 算法（單源正權(quán)最短路）：
- 本質(zhì)上是貪心 + BFS纳猫；
- 負(fù)權(quán)邊會破壞貪心策略的選擇，無法處理含負(fù)權(quán)問題竹捉；
- 稀疏圖小頂堆的寫法更優(yōu)芜辕，稠密圖樸素寫法更優(yōu)。
- Floyd 算法（多源匯正權(quán)最短路）
- Bellman Ford 算法（單源負(fù)權(quán)最短路）
- SPFA 算法（單源負(fù)權(quán)最短路）
這道題是求從一個源點到目標(biāo)點的最短路徑活孩，并且這條路徑上沒有負(fù)權(quán)值物遇，符合 Dijkstra 算法的應(yīng)用場景。
Dijkstra 算法的本質(zhì)是貪心 + BFS憾儒，我們需要將所有節(jié)點分為 2 類询兴，在每一輪迭代中，我們從 “候選集” 中選擇距離起點最短路長度最小的節(jié)點起趾，由于該點不存在更優(yōu)解诗舰，所以可以用該點來 “松弛” 相鄰節(jié)點。
- 1训裆、確定集：已確定（從起點開始）到當(dāng)前節(jié)點最短路徑的節(jié)點眶根；
- 2、候選集：未確定（從起點開始）到當(dāng)前節(jié)點最短路徑的節(jié)點边琉。
現(xiàn)在属百，我們分析在題目約束下，如何將原問題轉(zhuǎn)換為 Dijkstra 最短路問題变姨。
題解一（樸素 Dijkstra 算法）
我們定義 dis[i][j] 表示到達(dá) (i, j) 的最短時間族扰，根據(jù)題目約束 “grid[row][col]表示可以訪問格子 (row, col) 最早時間” 可知，dis[i][j] 的最小值不會低于 grid[i][j]定欧。
現(xiàn)在需要思考如何推導(dǎo)出遞推關(guān)系：
假設(shè)已經(jīng)確定到達(dá)位置 (i, j) 的最短時間是 time渔呵，那么相鄰位置 (x, y) 的最短時間為：
- 如果
time + 1 ≥ grid[x][y]，那么不需要等待就可以進(jìn)入砍鸠，進(jìn)入(x, y)的最短時間就是 time + 1扩氢； - 如果
time + 1 < grid[x][y]，那么必須通過等待消耗時間進(jìn)入爷辱。由于題目不允許原地停留消耗時間录豺，因此只能使出回退 “反復(fù)橫跳 A→ B → A” 來消耗時。因此有dis[x][y] = Math.max(time + 1, grid[x][y])饭弓。 - 另外巩检，根據(jù)網(wǎng)格圖的性質(zhì)，到達(dá)
(x, y)點的最短時間dis[x][y]與x + y的奇偶性一定相同示启，如果不同必然需要 + 1。例如的最短路徑是 3 + 1= 4领舰，而
的最短路徑是 2夫嗓。
至此迟螺，我們可以寫出樸素版本的算法。
class Solution {
fun minimumTime(grid: Array<IntArray>): Int {
// 無解
if (grid[0][1] > 1 && grid[1][0] > 1) return -1
// 無效值
val INF = Integer.MAX_VALUE
val n = grid.size
val m = grid[0].size
// 最短路長度
val dis = Array(n) { IntArray(m) { INF } }.apply {
this[0][0] = 0
}
// 訪問標(biāo)記
val visit = Array(n) { BooleanArray(m) }
// 方向
val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
while (true) {
var x = -1
var y = -1
// 尋找候選集中的最短時間
for (i in 0 until n) {
for (j in 0 until m) {
if (!visit[i][j] && (-1 == x || dis[i][j] < dis[x][y])) {
x = i
y = j
}
}
}
val time = dis[x][y]
// 終止條件
if (x == n - 1 && y == m - 1) return time
// 標(biāo)記
visit[x][y] = true
// 枚舉相鄰位置
for (direction in directions) {
val newX = x + direction[0]
val newY = y + direction[1]
// 越界
if (newX !in 0 until n || newY !in 0 until m || visit[newX][newY]) continue
var newTime = Math.max(time + 1, grid[newX][newY])
newTime += (newTime - newX - newY) % 2
// 松弛相鄰點
if (newTime < dis[newX][newY]) {
dis[newX][newY] = newTime
}
}
}
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
其中
為網(wǎng)格的個數(shù)
舍咖，在這道題中會超時矩父；
- 空間復(fù)雜度：
題解二（Dijkstra 算法 + 最小堆）
樸素 Dijkstra 的每輪迭代中需要遍歷 N 個節(jié)點尋找候選集中的最短路長度排霉。
事實上窍株，這 N 個節(jié)點中有部分是 “確定集”，有部分是遠(yuǎn)離起點的邊緣節(jié)點攻柠，每一輪都遍歷所有節(jié)點顯得沒有必要球订。常用的套路是配合小頂堆記錄候選集，以均攤 時間找到深度最近的節(jié)點中的最短路長度：
class Solution {
fun minimumTime(grid: Array<IntArray>): Int {
// 無解
if (grid[0][1] > 1 && grid[1][0] > 1) return -1
// 無效值
val INF = Integer.MAX_VALUE
val n = grid.size
val m = grid[0].size
// 最短路長度
val dis = Array(n) { IntArray(m) { INF } }.apply {
this[0][0] = 0
}
// 小頂堆：三元組 <x, y, dis>
val heap = PriorityQueue<IntArray>() { e1, e2 ->
e1[2] - e2[2]
}.apply {
this.offer(intArrayOf(0, 0, 0))
}
// 方向
val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
while (true) {
// 尋找候選集中的最短時間
val node = heap.poll()
val x = node[0]
val y = node[1]
val time = node[2]
// 終止條件
if (x == n - 1 && y == m - 1) return time
// 枚舉相鄰位置
for (direction in directions) {
val newX = x + direction[0]
val newY = y + direction[1]
// 越界
if (newX !in 0 until n || newY !in 0 until m) continue
var newTime = Math.max(time + 1, grid[newX][newY])
newTime += (newTime - newX - newY) % 2
// 松弛相鄰點
if (newTime < dis[newX][newY]) {
dis[newX][newY] = newTime
heap.offer(intArrayOf(newX, newY, newTime))
}
}
}
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
每輪迭代最壞以
時間取堆頂瑰钮；
- 空間復(fù)雜度：
題解三（二分 + BFS）
這道題也有二分的做法。
為了能夠有充足的時間走到目標(biāo)點浪谴，我們可以考慮在起點進(jìn)行反復(fù)橫跳消耗時間 0/2/4/6/8/12 … MAX_VALUE开睡。極端情況下，只要我們在起點消耗足夠長的時間后苟耻，總能夠有充足的時間走到右下角篇恒。
我們發(fā)現(xiàn)在起點消耗時間對結(jié)果的影響具有單調(diào)性：
- 如果 fullTime 可以到達(dá)目標(biāo)點，那么大于 fullTime 的所有時間都充足時間到達(dá)目標(biāo)點凶杖；
- 如果 fullTime 不能到達(dá)目標(biāo)點胁艰，那么小于 fullTime 的所有時間都不足以到達(dá)目標(biāo)點。
因此我們的算法是：使用二分查找尋找滿足條件的最小 fullTime蝗茁，并在每輪迭代中使用 BFS 走曼哈頓距離寻咒，判斷是否可以走到目標(biāo)點，最后再修正 fullTime 與 m + n 的奇偶性毛秘。
class Solution {
// 方向
private val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
fun minimumTime(grid: Array<IntArray>): Int {
// 無解
if (grid[0][1] > 1 && grid[1][0] > 1) return -1
// 無效值
val INF = Integer.MAX_VALUE
val n = grid.size
val m = grid[0].size
var left = Math.max(grid[n - 1][m - 1], m + n - 2)
var right = 1e5.toInt() + m + n - 2
while (left < right) {
val mid = (left + right) ushr 1
if (checkBFS(grid, mid)) {
right = mid
} else {
left = mid + 1
}
}
// (left - m + n) % 2 確保奇偶性一致
return left + (left - m + n) % 2
}
// 檢查從 fullTime 開始是否可以等待能否到達(dá)左上角
private fun checkBFS(grid: Array<IntArray>, fullTime: Int): Boolean {
val n = grid.size
val m = grid[0].size
val visit = Array(n) { BooleanArray(m) }.apply {
this[n - 1][m - 1] = true
}
val queue = LinkedList<IntArray>().apply {
this.offer(intArrayOf(n - 1, m - 1))
}
var time = fullTime - 1
while (!queue.isEmpty()) {
// 層序遍歷
for (count in 0 until queue.size) {
val node = queue.poll()!!
val x = node[0]
val y = node[1]
for (direction in directions) {
val newX = x + direction[0]
val newY = y + direction[1]
// 越界
if (newX !in 0 until n || newY !in 0 until m) continue
// 已訪問
if (visit[newX][newY]) continue
// 不可訪問
if (time < grid[newX][newY]) continue
// 可訪問
if (newX == 0 && newY == 0) return true
queue.offer(intArrayOf(newX, newY))
visit[newX][newY] = true
}
}
// 時間流逝 1 個單位
time--
}
return false
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
其中
是數(shù)據(jù)的最大值叫挟；
- 空間復(fù)雜度：
這周的周賽題目就講到這里抹恳，我們下周見员凝。
