共计 7790 个字符,预计需要花费 20 分钟才能阅读完成。
本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 发问。
大家好,我是小彭。
明天是 LeetCode 第 334 场周赛,你加入了吗?这场周赛考查范畴比拟根底,整体难度比拟均匀,第一题难度偏高,第四题须要咱们在算法里实现“重复横跳”,十分有意思。
小彭的 Android 交换群 02 群来了,公众号回复“加群”退出咱们~
2574. 左右元素和的差值(Easy)
题目地址
https://leetcode.cn/problems/…
题目形容
给你一个下标从 0 开始的整数数组 nums
,请你找出一个下标从 0 开始的整数数组 answer
,其中:
answer.length == nums.length
answer[i] = |leftSum[i] - rightSum[i]|
其中:
leftSum[i]
是数组nums
中下标i
左侧元素之和。如果不存在对应的元素,leftSum[i] = 0
。rightSum[i]
是数组nums
中下标i
右侧元素之和。如果不存在对应的元素,rightSum[i] = 0
。
返回数组 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
}
}
复杂度剖析:
- 工夫复杂度:$O(n)$。
- 空间复杂度:$O(1)$,不思考后果数组。
2575. 找出字符串的可整除数组(Medium)
题目地址
https://leetcode.cn/problems/…
题目形容
给你一个下标从 0 开始的字符串 word
,长度为 n
,由从 0
到 9
的数字组成。另给你一个正整数 m
。
word
的 可整除数组 div
是一个长度为 n
的整数数组,并满足:
- 如果
word[0,...,i]
所示意的 数值 能被m
整除,div[i] = 1
- 否则,
div[i] = 0
返回 word
的可整除数组。
题解
这道题次要靠大数解决。
将前缀字符串 [0, i] 转换为有 2 种形式:
- 1、应用
String#substring(0, i + 1)
裁剪子串,再转换为数字; - 2、应用
前缀 * 10 + word[i]
逐位计算。
然而,这 2 种形式在大数 case 中会遇到整型溢出变为正数,导致判断出错的状况,咱们想方法保障加法运算不会整型溢出。咱们发现:在解决完 [i – 1] 地位后,不用记录 [0, i-1] 的整段前缀,而仅须要记录前缀对 m 的取模后果。
例如当 m
为 3 时,“11 * 10 + 1 = 111”
与 “(11 % 3) * 10 + 1 = 21”
都可能对 3 整除。也能够这样了解:前缀中能被 m
整除的加法因子在后续运算中乘以 10 后仍然可能被 m
整数,所以这部分加法因子应该尽早消掉。
另外还有一个细节:因为 m
的最大值是 $10^9$,前缀的取模后果的最大值为 $10^9 – 1$,而以后地位的最大值是 9,加法后仍然会溢出,因而咱们要用 Long 记录以后地位。
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
}
}
复杂度剖析:
- 工夫复杂度:$O(n)$。
- 空间复杂度:$O(1)$,不思考后果数组。
2576. 求出最多标记下标(Medium)
题目地址
https://leetcode.cn/problems/…
题目形容
给你一个下标从 0 开始的整数数组 nums
。
一开始,所有下标都没有被标记。你能够执行以下操作任意次:
- 抉择两个 互不雷同且未标记 的下标
i
和j
,满足2 * nums[i] <= nums[j]
,标记下标i
和j
。
请你执行上述操作任意次,返回 nums
中最多能够标记的下标数目。
题解(排序 + 贪婪 + 双指针)
这道题的难度是找到贪婪法则。
题目要求:抉择两个互不雷同且未标记的下标 i 和 j,满足 2 * nums[i] <= nums[j],标记下标 i 和 j。咱们发现题目并不关怀 [i] 和 [j] 的抉择程序,所以对排序不会影响问题后果,而且排序可能更不便地比拟元素大小,因而题目的框架应该是往 排序 + [贪婪 / 双指针 / 二分 / DP] 的思路思考。
较量过程中的思考过程记录下来:
- 尝试 1 – 排序 + 贪婪双指针:nums[i] 优先应用最小值,nums[j] 优先应用最大值,谬误用例:[1 2 3 6];
- 尝试 2 – 排序 + 贪婪:nums[i] 优先应用最小值,nums[j] 应用大于 nums[i] 的最小值,谬误用例:[1 2 4 6];
- 尝试 3- 排序 + 贪婪:从后往前遍历,nums[i] 优先应用较大值,nums[j] 应用大于 nums[i] 的最小值,谬误用例:[2 3 4 8]。
陷入僵局……
开始转换思路:是否将数组拆分为两局部,作为 nums[i]
的分为一组,作为 nums[j]
的分为一组。例如,在用例 [1 2 | 3 6] 和 [1 2 | 4 6] 和 [2 3 | 4 8]中,将数组的前局部作为 nums[i] 而后半局部作为 nums[j] 时,能够失去最优解,至此发现贪婪法则。
设数组的长度为 n,最大匹配对数为 k。
- 贪婪法则 1:从小到大排序后,应用数组的左半局部作为
nums[i]
且应用数组的右半局部作为nums[j]
总能取到最优解。反之,如果应用右半局部的某个数nums[t]
作为nums[i]
,相当于占用了一个较大的数,不利于后续nums[i]
寻找配对。
将数组拆分为两局部后:
- 贪婪法则 2:从小到大排序后,当固定
nums[i]
时,nums[j]
越小越好,否则会占用一个较大的地位,不利于后续nums[i]
寻找配对。因而最优解肯定是应用左半局部的最小值与右半局部的最小值配对。
能够应用双指针求解:
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
}
}
复杂度剖析:
- 工夫复杂度:$O(nlgn + n)$ 其中 $n$ 为 $nums$ 数组长度,排序工夫 $O(nlgn)$,双指针遍历工夫 $O(n)$;
- 空间复杂度:$O(lgn)$ 排序递归栈空间。
2577. 在网格图中拜访一个格子的起码工夫(Hard)
题目地址
https://leetcode.cn/problems/…
题目形容
给你一个 m x n
的矩阵 grid
,每个元素都为 非负 整数,其中 grid[row][col]
示意能够拜访格子 (row, col)
的 最早 工夫。也就是说当你拜访格子 (row, col)
时,起码曾经通过的工夫为 grid[row][col]
。
你从 最左上角 登程,登程时刻为 0
,你必须始终挪动到上下左右相邻四个格子中的 任意 一个格子(即不能停留在格子上)。每次挪动都须要破费 1 单位工夫。
请你返回 最早 达到右下角格子的工夫,如果你无奈达到右下角的格子,请你返回 -1
。
前置常识
这道题是单源正权最短路的衍生问题,先回顾以一下相似的最短路问题解决方案:
-
Dijkstra 算法(单源正权最短路):
- 实质上是贪婪 + BFS;
- 负权边会毁坏贪婪策略的抉择,无奈解决含负权问题;
- 稠密图小顶堆的写法更优,浓密图奢侈写法更优。
- Floyd 算法(多源汇正权最短路)
- Bellman Ford 算法(单源负权最短路)
- SPFA 算法(单源负权最短路)
这道题是求从一个源点到指标点的最短门路,并且这条门路上没有负权值,合乎 Dijkstra 算法的利用场景。
Dijkstra 算法的实质是贪婪 + BFS,咱们须要将所有节点分为 2 类,在每一轮迭代中,咱们从“候选集”中抉择间隔终点最短路长度最小的节点,因为该点不存在更优解,所以能够用该点来“松弛”相邻节点。
- 1、确定集:已确定(从终点开始)到以后节点最短门路的节点;
- 2、候选集:未确定(从终点开始)到以后节点最短门路的节点。
当初,咱们剖析在题目束缚下,如何将原问题转换为 Dijkstra 最短路问题。
题解一(奢侈 Dijkstra 算法)
咱们定义 dis[i][j]
示意达到 (i, j)
的最短时间,依据题目束缚“grid[row][col]
示意能够拜访格子 (row, col)
最早工夫”可知,dis[i][j]
的最小值不会低于 grid[i][j]
。
当初须要思考如何推导出递推关系:
假如曾经确定达到地位 (i, j)
的最短时间是 time
,那么相邻地位 (x, y)
的最短时间为:
- 如果
time + 1 ≥ grid[x][y]
,那么不须要期待就能够进入,进入(x, y)
的最短时间就是 time + 1; - 如果
time + 1 < grid[x][y]
,那么必须通过期待耗费工夫进入。因为题目不容许原地停留耗费工夫,因而只能使出回退 “重复横跳 A→ B → A” 来耗费时。因而有dis[x][y] = Math.max(time + 1, grid[x][y])
。 - 另外,依据网格图的性质,达到
(x, y)
点的最短时间dis[x][y]
与x + y
的奇偶性肯定雷同,如果不同必然须要 + 1。例如 $\begin{bmatrix}
0 & 1 \
1 & 3
\end{bmatrix}$ 的最短门路是 3 + 1= 4,而 $\begin{bmatrix}
0 & 1 \
1 & 2
\end{bmatrix}$ 的最短门路是 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
}
// 拜访标记
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
// 标记
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
}
}
}
}
}
复杂度剖析:
- 工夫复杂度:$O(N^2)$ 其中 $N$ 为网格的个数 $nm$,在这道题中会超时;
- 空间复杂度:$O(N^2)$ 最短路数组的空间。
题解二(Dijkstra 算法 + 最小堆)
奢侈 Dijkstra 的每轮迭代中须要遍历 N 个节点寻找候选集中的最短路长度。
事实上,这 N 个节点中有局部是“确定集”,有局部是远离终点的边缘节点,每一轮都遍历所有节点显得没有必要。罕用的套路是配合小顶堆记录候选集,以均摊 $O(lgN)$ 工夫找到深度最近的节点中的最短路长度:
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))
}
}
}
}
}
复杂度剖析:
- 工夫复杂度:$O(NlgN)$ 每轮迭代最坏以 $O(lgN)$ 工夫取堆顶;
- 空间复杂度:$O(N^2)$ 最短路数组的空间。
题解三(二分 + BFS)
这道题也有二分的做法。
为了可能有短缺的工夫走到指标点,咱们能够思考在终点进行重复横跳耗费工夫 0/2/4/6/8/12 … MAX_VALUE。极其状况下,只有咱们在终点耗费足够长的工夫后,总可能有短缺的工夫走到右下角。
咱们发现在终点耗费工夫对后果的影响具备枯燥性:
- 如果 fullTime 能够达到指标点,那么大于 fullTime 的所有工夫都短缺工夫达到指标点;
- 如果 fullTime 不能到达指标点,那么小于 fullTime 的所有工夫都不足以达到指标点。
因而咱们的算法是:应用二分查找寻找满足条件的最小 fullTime,并在每轮迭代中应用 BFS 走曼哈顿间隔,判断是否能够走到指标点,最初再修改 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 开始是否能够期待是否达到左上角
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
}
}
复杂度剖析:
- 工夫复杂度:$O(N·lgU)$ 其中 $N$ 为网格的个数 $nm$,$U$ 是数据的最大值;
- 空间复杂度:$O(N^2)$ 最短路数组的空间。
这周的周赛题目就讲到这里,咱们下周见。