LeetCode 周赛 334，在算法的世界里反复横跳-六虎

我正在参与「启航计划」

大家好，我是小彭。

今天是 LeetCode 第 334 场周赛，你参与了吗？这场周赛考察规模比较根底，全体难度比较均匀，第一题难度偏高，第四题需求咱们在算法里完成 “重复横跳”，非常有意思。

小彭的 Android 沟通群 02 群来了，大众号回复 “加群” 加入咱们~

2574. 左右元素和的差值（Easy）

标题地址

leetcode.cn/problems/le…

标题描绘

给你一个下标从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）

标题地址

leetcode.cn/problems/fi…

标题描绘

给你一个下标从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）

标题地址

leetcode.cn/problems/fi…

标题描绘

给你一个下标从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 (n l g n + n)$ 其间 $n$ 为 $n u m s$ 数组长度，排序时刻 $O (n l g n)$ ，双指针遍历时刻 $O (n)$ ；
空间复杂度： $O (l g n)$ 排序递归栈空间。

2577. 在网格图中拜访一个格子的最少时刻（Hard）

标题地址

leetcode.cn/problems/mi…

标题描绘

给你一个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。例如 $[0113]\begin{bmatrix} 0 & 1 \\ 1 & 3 \end{bmatrix}$ 的最短途径是 3 + 1= 4，而 $[0112]\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 (l g N)$ 时刻找到深度最近的节点中的最短路长度：

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 (Nl g N)$ 每轮迭代最坏以 $O (l g N)$ 时刻取堆顶；
空间复杂度： $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 \cdot l gU)$ 其间 $N$ 为网格的个数 $nm$ ， $U$ 是数据的最大值；
空间复杂度： $O(N^2)$ 最短路数组的空间。

这周的周赛标题就讲到这儿，咱们下周见。

本文已收录到 AndroidFamily，技能和职场问题，请重视大众号 [彭旭锐] 发问。

LeetCode 周赛 334，在算法的世界里反复横跳

2574. 左右元素和的差值（Easy）

标题地址

标题描绘

题解

2575. 找出字符串的可整除数组（Medium）

标题地址

标题描绘

题解

2576. 求出最多符号下标（Medium）

标题地址

标题描绘

题解（排序 + 贪心 + 双指针）

2577. 在网格图中拜访一个格子的最少时刻（Hard）

标题地址

标题描绘

前置知识

题解一（朴素 Dijkstra 算法）

题解二（Dijkstra 算法 + 最小堆）

题解三（二分 + BFS）

相关文章

【Kotlin回顾】22.Kotlin协程—Flow原理

在mac开发一个脚本执行FFMpeg编译

2022年Python顶级自动化特征工程框架

一种基于柔性事务的分布式事务解决方案设计探究

作者信息