LeetCode 周赛 353(2023/07/09)看似没考 LIS 最长递增子序列,好像又考了

leetcode,看似,lis,最长,递增,序列,好像 · 浏览次数 : 19

小编点评

**代码分析** 这三道题都使用差分数组或滑动窗口等技术来优化时间复杂度。 **1. 数组元素全部为零** - 问题:在 nums 数组中找到第一个不为 0 的元素作为起点。 - 解决方案:从左到右找到第一个不为 0 的元素并减去其值,直到无法构造出长为 k 的窗口。 **2. 区间更新** - 问题:对于区间在 nums[i, i + k - 1] 的元素减去 nums[i]。 - 解决方案:对 diff[i+k] += nums[i],而对 diff[i] -= nums[i]。 **3. 差分数组 + 线性扫描** - 问题:在滑动窗口中寻找元素的最小值。 - 解决方案:从左向右执行区间更新,边维护差分数组的前缀和。

正文

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

T1. 找出最大的可达成数字(Easy)

  • 标签:模拟

T2. 达到末尾下标所需的最大跳跃次数(Medium)

  • 标签:动态规划、动态开点线段树

T3. 构造最长非递减子数组(Medium)

  • 标签:动态规划

T4. 使数组中的所有元素都等于零(Medium)

  • 标签:贪心、差分数组、前缀和


T1. 找出最大的可达成数字(Easy)

https://leetcode.cn/problems/find-the-maximum-achievable-number/

题解(模拟)

简单模拟题,在每一轮操作中可以将 num 加一,而对 x 减一,因此最大 x 就是 num + 2 * t。

class Solution {
    fun theMaximumAchievableX(num: Int, t: Int): Int {
        return num + 2 * t
    }
}

复杂度分析:

  • 时间复杂度:$O(1)$
  • 空间复杂度:$O(1)$

T2. 达到末尾下标所需的最大跳跃次数(Medium)

https://leetcode.cn/problems/maximum-number-of-jumps-to-reach-the-last-index

题解一(动态规划)

「55. 跳跃游戏」 类似,但本题中每次操作可以跳转到的位置需要满足 nums[j] - nums[i] ≤ target,而跳跃游戏中可跳转的位置是 [i - nums[i], i + nums[i]],且每次只能向右跳(j > i)。容易想到,对于位置 nums[i] 来说,必然存在从 nums[0, i - 1] 中的某个位置跳转得来,即 dp[i] = dp[j] + 1,可以用动态规划实现。

class Solution {
    fun maximumJumps(nums: IntArray, target: Int): Int {
        // 跳转到差值绝对值不大于 target 的位置,不能返回
        val n = nums.size
        val dp = IntArray(n) { -1 }
        dp[0] = 0
        for (j in 1 until n) {
            for (i in 0 until j) {
                // 寻找合法子问题
                if (-1 != dp[i] && Math.abs(nums[j] - nums[i]) <= target) {
                    dp[j] = Math.max(dp[j], dp[i] + 1)
                }
            }
        }
        return dp[n - 1]
    }
}

复杂度分析:

  • 时间复杂度:$O(n^2)$ 总共有 n 个状态,每个状态需要枚举 $O(n)$ 个状态,因此整体时间复杂度是 $O(n^2)$;
  • 空间复杂度:$O(n)$ DP 数组空间。

题解二(动态开点线段树)

在题解一中,当枚举到每个元素 nums[i] 时,我们检查前驱元素中区间范围为 [nums[i] - target, nums[i] - target] 范围内的元素的最大跳转次数 j,使得 dp[i] = dp[j] + 1,这个过程可以抽象为两个动作:

  • 单点更新:dp[nums[i]] = 子状态 + 1
  • 区间查询:子状态 = max

这是一个涉及单点更新和区间查询的数据结构,可以使线段树(基于值域)实现,同时这与 「2407. 最长递增子序列 II」 问题是类似的。另外,由于输入数据值域非常大,我们需要先离散化或使用动态开点线段树,这里使用动态开点的方法。

class Solution {
    fun maximumJumps(nums: IntArray, target: Int): Int {
        // 值域线段树(动态开点)
        val tree = SegementTree(-1e9.toLong(), 1e9.toLong())
        tree.set(0L + nums[0], 0)
        for (i in 1 until nums.size) {
            val step = tree.query(0L + nums[i] - target, 0L + nums[i] + target) + 1 // 区间查询
            tree.set(0L + nums[i], step) // 单点更新
            if (i == nums.size - 1)  return if (step < 0) -1 else step // 终点
        }
        return -1
    }

    // 动态开点线段树(单点更新没必要做 Lazy)
    private class SegementTree(private val from: Long, private val to: Long) {
        // 线段树根节点
        private val root = Node(from, to, Integer.MIN_VALUE)

        // 线段树节点(区间范围与区间最值)
        private class Node(val left: Long, val right: Long, var value: Int) {
            // 中位索引
            val mid : Long get() = (left + right) shr 1 // 存在负数,不能使用无符号右移
            // 左子树
            val l by lazy { Node(left, mid, Integer.MIN_VALUE) }
            // 右子树
            val r by lazy { Node(mid + 1, right, Integer.MIN_VALUE) }

            // 单点更新
            fun set(pos: Long, value: Int) {
                // println("[$left, $right] set=[$pos, $value]")
                // 1、当前节点不处于区间范围内
                if (left > pos || right < pos) return
                // 2、叶子节点
                if (left == right) {
                    this.value = Math.max(this.value, value)
                    return
                }
                // 3、更新左子树
                if (pos <= mid) l.set(pos, value)
                // 4、更新右子树
                if (pos > mid) r.set(pos, value)
                // 5、合并子节点的结果
                this.value = Math.max(l.value, r.value)
            }

            // 区间查询
            fun query(from: Long, to: Long): Int {
                // println("[$left, $right] query[$from, $to]")
                // 1、当前节点不处于区间范围内
                if (this.left > to || this.right < from) return Integer.MIN_VALUE
                // 2、当前节点完全处于区间范围之内
                if (this.left >= from && this.right <= to) return value
                // 3、合并子节点的结果
                return Math.max(l.query(from, to), r.query(from, to))
            }
        }

        // 单点更新
        fun set(pos: Long, value: Int) {
            root.set(pos, value)
        }

        // 区间查询
        fun query(from: Long, to: Long): Int {
            return root.query(from, to)
        }        
    }
}

复杂度分析:

  • 时间复杂度:$O(nlgU)$ 每次查询操作 $O(lgU)$ 整体的时间复杂度是 $O(nlgU)$;
  • 空间复杂度:$O(n)$ 散列表空间

T3. 构造最长非递减子数组(Medium)

https://leetcode.cn/problems/longest-non-decreasing-subarray-from-two-arrays/

题解一(动态规划)

讨论区多少人看成 LIS 最长递增子序列问题了呢?

对于每个位置 i,当且仅有选择 num1[i] 或 nums2[i] 两种选择,需要思考「选哪个」。

我们定义 dp[i][0/1] 表示以 i 位置为结尾的最长非递减子数组,那么对于位置 i 来说,有 2 种选择:

  • 如果 nums1[i] 能够与 nums1[i - 1] 和 nums2[i - 2] 构造非递减子序列,那么可以构造更长的子数组,dp[i][0] = max{dp[i-1][0], dp[i-1][1]} + 1;
  • 如果 nums2[i] 能够与 nums1[i - 1] 和 nums2[i - 2] 构造非递减子序列,那么可以构造更长的子数组,dp[i][1] = max{dp[i-1][0], dp[i-1][1]} + 1;
  • 否则,dp[i][0] = dp[i][1] = 1
class Solution {
    fun maxNonDecreasingLength(nums1: IntArray, nums2: IntArray): Int {
        val n = nums1.size
        val dp = Array(n) { IntArray(2) { 1 } }
        var ret = 1
        for (i in 1 until n) {
            val x = nums1[i]
            val y = nums2[i]
            if (nums1[i] >= nums1[i - 1]) {
                dp[i][0] = Math.max(dp[i][0], dp[i - 1][0] + 1)
            }
            if (nums1[i] >= nums2[i - 1]) {
                dp[i][0] = Math.max(dp[i][0], dp[i - 1][1] + 1)
            }
            if (nums2[i] >= nums1[i - 1]) {
                dp[i][1] = Math.max(dp[i][1], dp[i - 1][0] + 1)
            }
            if (nums2[i] >= nums2[i - 1]) {
                dp[i][1] = Math.max(dp[i][1], dp[i - 1][1] + 1)
            }
            ret = Math.max(ret, dp[i][0])
            ret = Math.max(ret, dp[i][1])
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:$O(n)$ 总共有 n 个子问题,每个子问题需要枚举 4 个子状态,整体的时间复杂度是 $O(n)$;
  • 空间复杂度:$O(n)$ DP 数组空间。

题解二(动态规划 + 滚动数组)

由于 dp[i] 只会利用 dp[i - 1] 的信息,我们可以使用滚动数组优化空间复杂度:

class Solution {
    fun maxNonDecreasingLength(nums1: IntArray, nums2: IntArray): Int {
        val n = nums1.size
        var dp = IntArray(2) { 1 }
        var ret = 1
        for (i in 1 until n) {
            val x = nums1[i]
            val y = nums2[i]
            val newDp = IntArray(2) { 1 }
            if (nums1[i] >= nums1[i - 1]) {
                newDp[0] = Math.max(newDp[0], dp[0] + 1)
            }
            if (nums1[i] >= nums2[i - 1]) {
                newDp[0] = Math.max(newDp[0], dp[1] + 1)
            }
            if (nums2[i] >= nums1[i - 1]) {
                newDp[1] = Math.max(newDp[1], dp[0] + 1)
            }
            if (nums2[i] >= nums2[i - 1]) {
                newDp[1] = Math.max(newDp[1], dp[1] + 1)
            }
            ret = Math.max(ret, newDp[0])
            ret = Math.max(ret, newDp[1])
            dp = newDp
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:$O(n)$ 总共有 n 个子问题,每个子问题需要枚举 4 个子状态,整体的时间复杂度是 $O(n)$;
  • 空间复杂度:$O(1)$ DP 数组空间。

T4. 使数组中的所有元素都等于零(Medium)

https://leetcode.cn/problems/apply-operations-to-make-all-array-elements-equal-to-zero/

题解一(贪心)

这道题在周赛 T4 题中算很简单的题目了,放在 T2 比较合适。

我们发现窗口 K 是固定的,同时对于数组的首部或尾部元素来说,它们的约束是最强的,即:只能被从 nums[0] 为起点或 nums[n-1] 为终点的窗口消除。因此,为了实现将数组中所有元素重置为零的目标,我们从左到右找到第一个不为 0 的元素 nums[i] 为起点开始消除:

  • nums[i] == 0,跳过;
  • nums[i] < 0,不满足,说明在 nums[0, i - 1] 区间必然存在一个较大的整数导致 nums[i] 被过渡消除;
  • nums[i] > 0,如果 i > nums.size - k,那么无法构造出长为 k 的窗口,不满足;否则将 nums[i,i +k - 1] 的窗口减去 nums[i]。
class Solution {
    fun checkArray(nums: IntArray, k: Int): Boolean {
        for ((i, x) in nums.withIndex()) {
            if (x == 0) continue
            if (x < 0 || i > nums.size - k) return false
            for (j in i until i + k) {
                nums[j] -= x
            }
        }
        return true
    }
}

复杂度分析:

  • 时间复杂度:$O(n^2)$ 最坏情况下取 k = n/2,而 nums 数组为 [1,2,3,4,5…] 递增序列,那么时间复杂度是 $O(n^2/4)$;
  • 空间复杂度:$O(1)$ 仅使用常量级别空间。

题解二(差分数组)

题解一中的每次对操作相当于做区间更新,可以使用差分数组(使用标记代替减法操作)来优化时间复杂度:

  • 区间更新:对于区间在 nums[i, i + k - 1] 的元素减去 nums[i],则对 diff[i+k] += nums[i],而对 diff[i] -= nums[i],时间复杂度是 O(n);
  • 查询单点值:对于 nums[i] 的实际值的常规做法是求 diff[i] 的前缀和,时间复杂度是 O(n),这是无法满足要求的。
// 超出时间限制
class Solution {
    fun checkArray(nums: IntArray, k: Int): Boolean {
        val n = nums.size
        // 差分数组
        val diff = IntArray(n + 1)
        for (i in 0 until nums.size) {
            // 从差分数组还原真实值(求前缀和)
            var x = nums[i]
            for (j in 0 .. i) {
                x += diff[j] // (存在重复计算)
            }
            if (x < 0) return false
            if (x == 0) continue
            if (i > nums.size - k) return false
            // 区间更新
            diff[i] -= x
            diff[i + k] += x
        }
        return true
    }
}

复杂度分析:

  • 时间复杂度:$O(n^2)$ 在内层循环中,需要计算差分数组的前缀和还原数组值,整体时间复杂度是 $O(n^2)$;
  • 空间复杂度:$O(n)$ 差分数组空间。

题解三(差分数组 + 线性扫描)

由于我们是从左向右枚举数组元素,我们可以在做从左向右执行区间更新时,边维护差分数组的前缀和。

class Solution {
    fun checkArray(nums: IntArray, k: Int): Boolean {
        val n = nums.size
        // 差分数组
        val diff = IntArray(n + 1)
        // 差分前缀和
        var diffSum = 0
        for (i in 0 until nums.size) {
            // 边更新边维护差分数组的前缀和
            diffSum += diff[i]
            val x = nums[i] + diffSum
            if (x == 0) continue
            if (x < 0 || i > nums.size - k) return false
            // 区间更新
            diff[i] -= x
            diff[i + k] += x
            diffSum -= x
        }
        return true
    }
}

复杂度分析:

  • 时间复杂度:$O(n)$ 只需要一趟线性扫描;
  • 空间复杂度:$O(n)$ 差分数组空间。

往期回顾

与LeetCode 周赛 353(2023/07/09)看似没考 LIS 最长递增子序列,好像又考了相似的内容:

LeetCode 周赛 353(2023/07/09)看似没考 LIS 最长递增子序列,好像又考了

> **本文已收录到 [AndroidFamily](https://github.com/pengxurui/AndroidFamily),技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。** - 往期回顾:[LeetCode 单周赛第 352 场 · 一

LeetCode 周赛 332,在套路里摸爬滚打~

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,今天是 3T 选手小彭。 上周是 LeetCode 第 332 场周赛,你参加了吗?算法解题思维需要长时间锻炼,加入我们一起刷题吧~ 小彭的 Android 交流群 02 群已经建立啦,公众号回复 “

LeetCode 周赛 333,你管这叫 Medium 难度?

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周是 LeetCode 第 333 场周赛,你参加了吗?这场周赛质量很高,但难度标得不对,我真的会谢。算法解题思维需要长时间锻炼,加入我们一起刷题吧~ 小彭的 Android 交流群 0

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

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 今天是 LeetCode 第 334 场周赛,你参加了吗?这场周赛考察范围比较基础,整体难度比较平均,第一题难度偏高,第四题需要我们在算法里实现 “反复横跳”,非常有意思。 小彭的 And

LeetCode 周赛 335,纯纯手速场!

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 昨晚是 LeetCode 第 335 场周赛,你参加了吗?这场周赛整体难度不高,有两道模板题,第三题和第四题应该调换一下位置。 小彭的 Android 交流群 02 群来了,公众号回复 “

LeetCode 周赛 336,多少人直接 CV?

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 今天早上是 LeetCode 第 336 场周赛,你参加了吗?这场周赛整体质量比较高,但是最后一题是老题,CV 能过。但是输入数据范围被降低了,这操作也是没谁了。 2587. 统计范围内的

LeetCode 周赛 338,贪心 / 埃氏筛 / 欧氏线性筛 / 前缀和 / 二分查找 / 拓扑排序

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周末是 LeetCode 第 338 场周赛,你参加了吗?这场周赛覆盖的知识点很多,第四题称得上是近期几场周赛的天花板。 小彭的技术交流群 02 群来了,公众号回复 “加群” 加入我们~

LeetCode 周赛 340,质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周跟大家讲到小彭文章风格的问题,和一些朋友聊过以后,至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小,但却有很多像我一样的初学者,他们有兴趣参加但容易被题目难度和大神选

LeetCode 周赛 341 场,模拟 / 树上差分 / Tarjan 离线 LCA / DFS

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周末有单双周赛,双周赛我们讲过了,单周赛那天早上有事没参加,后面做了虚拟竞赛,然后整个人就不好了。前 3 题非常简单,但第 4 题有点东西啊,差点就放弃了。最后,被折磨了一个下午和一个大

LeetCode 周赛 342(2023/04/23)容斥原理、计数排序、滑动窗口、子数组 GCB

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 前天刚举办 2023 年力扣杯个人 SOLO 赛,昨天周赛就出了一场 Easy - Easy - Medium - Medium 的水场,不得不说 LeetCode 是懂礼数的 😁。 接