LeetCode 周赛 353（2023/07/09）看似没考 LIS 最长递增子序列，好像又考了-六虎

⭐️ 本文已收录到 AndroidFamily，技能和职场问题，请关注大众号 [彭旭锐] 和 [BaguTree Pro] 常识星球提问。

学习数据结构与算法的关键在于把握问题背后的算法思想结构，你的考虑越抽象，它能掩盖的问题域就越广，理解难度也更杂乱。在这个专栏里，小彭与你共享每场 LeetCode 周赛的解题陈述，一起体会上分之旅。

本文是 LeetCode 上分之旅系列的第 32 篇文章，往期回忆请移步到文章结束~

T1. 找出最大的可达成数字（Easy）

标签：模拟

T2. 到达结束下标所需的最大跳动次数（Medium）

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

T3. 结构最长非递减子数组（Medium）

标签：动态规划

T4. 使数组中的一切元素都等于零（Medium）

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

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

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{nums[i] – k, nums[i] – 1}

这是一个触及单点更新和区间查询的数据结构，能够使线段树（基于值域）完成，一起这与「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 (n l gU)$ 每次查询操作 $O (l gU)$ 全体的时刻杂乱度是 $O (n l gU)$ ；
空间杂乱度： $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 上分之旅系列往期回忆：

LeetCode 单周赛第 352 场一场关于子数组的专题周赛

LeetCode 单周赛第 350 场滑动窗口与离散化模板题

LeetCode 双周赛第 107 场很有意思的 T2 题

LeetCode 双周赛第 104 场流水的动态规划，铁打的结构化考虑

⭐️ 永远信任夸姣的工作即将产生，欢迎加入小彭的 Android 沟通社群~

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

T1. 找出最大的可达成数字（Easy）

题解（模拟）

T2. 到达结束下标所需的最大跳动次数（Medium）

题解一（动态规划）

题解二（动态开点线段树）

T3. 结构最长非递减子数组（Medium）

题解一（动态规划）

题解二（动态规划 + 翻滚数组）

T4. 使数组中的一切元素都等于零（Medium）

题解一（贪心）

题解二（差分数组）

题解三（差分数组 + 线性扫描）

引荐阅览

相关文章

Glide 原理探索

家庭资产管理助手（end）

LeetCode 双周赛 102（2023/04/15）模拟、BFS、Dijkstra、Floyd

强大而灵活的RecyclerView Adapter——BRVAH（框架引入与BaseQuickAdapter使用篇）

作者信息