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

这篇具有很好参考价值的文章主要介绍了LeetCode 周赛 340,质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

大家好,我是小彭。

上周跟大家讲到小彭文章风格的问题,和一些朋友聊过以后,至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小,但却有很多像我一样的初学者,他们有兴趣参加但容易被题目难度和大神选手的题解劝退。

考虑到这些跟我一样的小白,我决定算法题解风格会向这些初学者倾斜,我们不会强调最优解法,而是强调从题意分析到问题抽象,再从暴力解法一步步升级到最优解法的推导过程,希望能帮到喜欢算法的朋友,向 Guardian 出发。

好一波强行自证价值? 😁


今天讲 LeetCode 单周赛第 340 场,今天状态不好,掉了一波大分。

2614. 对角线上的质数(Easy)

这道题是最近第 2 次出现质数问题,注意 1 不是质数!

  • 质数判断:$O(n·\sqrt(U))$

2615. 等值距离和(Medium)

这道题是标准的前缀和数组题目,我们有从暴力到前缀和的解法,最后有消除前缀和数组的最优解法,理解从暴力解法到最优解法的推导过程非常重要。

  • 题解 1:暴力 $O(n^2)$
  • 题解 2:前缀和数组 $O(n) + O(n)$
  • 题解 3:前缀和 + DP $O(n) + O(1)$

2616. 最小化数对的最大差值(Medium)

这道题是 “极大化最小值” 问题,与以前我们讲过的 “高楼丢鸡蛋” 问题属于同一种类型,理解 “极大化最小值” 中的单调性与二分查找的思路非常重要。

  • 贪心 + 二分查找 $O(nlgn + nlgU)$

2617. 网格图中最少访问的格子数(Hard)

这道题是经典题目 45. 跳跃游戏 II 的二维版本,我创新性地从图的最短路视角理解 跳跃游戏 II,再迁移到这道二维数组问题上,难度降低为 Medium。

  • 最短路 BFS + 平衡二叉树 + 队列 $O(nm·(lgn + lgm))$

2614. 对角线上的质数(Easy)

题目地址

https://leetcode.cn/problems/prime-in-diagonal

题目描述

给你一个下标从 0 开始的二维整数数组 nums 。

返回位于 nums 至少一条 对角线 上的最大 质数 。如果任一对角线上均不存在质数,返回 0 。

注意:

  • 如果某个整数大于 1 ,且不存在除 1 和自身之外的正整数因子,则认为该整数是一个质数。
  • 如果存在整数 i ,使得 nums[i][i] = val 或者 nums[i][nums.length - i - 1]= val ,则认为整数 val 位于 nums 的一条对角线上。

题解(质数)

遍历两条对角线上的元素,如果是质数则更新答案。注意 1 不是质数!

另外再检查数据量,数组的长度 n 最大为 300,而数据最大值为 4*10^6,所以用朴素的质数判断算法能满足要求。

class Solution {
    fun diagonalPrime(nums: Array<IntArray>): Int {
        var ret = 0
        val n = nums.size
        for (i in 0 until n) {
            val num1 = nums[i][i]
            val num2 = nums[i][n - 1 - i]
            if (num1 > ret && isPrime(num1)) ret = num1
            if (num2 > ret && isPrime(num2)) ret = num2
        }
        return ret
    }

    private fun isPrime(num: Int): Boolean {
        if (num == 1) return false
        var x = 2
        while (x * x <= num) {
            if (num % x == 0) {
                return false
            }
            x++
        }
        return true
    }
}

复杂度分析:

  • 时间复杂度:$O(n·\sqrt(U))$ 其中 n 是 nums 二维数组的长度,U 是输入数据的最大值;
  • 空间复杂度:$O(1)$ 仅使用常量级别空间。

近期周赛质数问题:

  • 2600. 质数减法运算(Medium)

2615. 等值距离和(Medium)

题目地址

https://leetcode.cn/problems/sum-of-distances/

题目描述

给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ,arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ,则令 arr[i] 等于 0 。

返回数组 **arr 

问题分析

容易想到,不同数值之间互不影响,所以先对数组元素分组,再依次计算组内元素之间的距离差绝对值之和。

题解一(暴力 · 超出时间限制)

暴力解法是计算每个位置与其他组内元素的距离差绝对值。

class Solution {
    fun distance(nums: IntArray): LongArray {
        val n = nums.size
        // 分组
        val map = HashMap<Int, ArrayList<Int>>()
        for (index in nums.indices) {
            map.getOrPut(nums[index]) { ArrayList<Int>() }.add(index)
        }
        val ret = LongArray(n)
        // 暴力
        for ((_, indexs) in map) {
            for (i in indexs.indices) {
                for (j in indexs.indices) {
                    ret[indexs[i]] += 0L + Math.abs(indexs[i] - indexs[j])
                }
            }
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:$O(n^2)$ 其中 n 为 nums 数组的长度
  • 空间复杂度:$O(1)$ 不考虑分组的数据空间。

题解二(前缀和数组)

分析计算元素 x 与组内元素距离差绝对值之和的过程:

以组内下标为 [0, 1, 2, 3, 4, 5] 为例,下标 [2] 位置的距离和计算过程为:

  • (x - 0) + (x - 1) + (x - x) + (3 - x) + (4 - x) + (5 - x)

我们以 [2] 为分割点将数组分为两部分,则发现:

  • (x - 0) - (x - 1) 正好等于 (左边元素个数 * x) - 左边元素之和
  • (3 - x) + (4 - x) + (5 - x) 正好等于 (右边元素之和) - (右边元素个数 * x)

数组区间和有前缀和的套路做法,可以以空间换时间降低时间复杂度。

  • 细节:x * i 是 Int 运算会溢出,需要乘以 1 转换为 Long 运算
class Solution {
    fun distance(nums: IntArray): LongArray {
        val n = nums.size
        // 分组
        val map = HashMap<Int, ArrayList<Int>>()
        for (index in nums.indices) {
            map.getOrPut(nums[index]) { ArrayList<Int>() }.add(index)
        }
        val ret = LongArray(n)
        // 分组计算
        for ((_, indexs) in map) {
            val m = indexs.size
            // 前缀和
            val preSums = LongArray(m + 1)
            for (i in indexs.indices) {
                preSums[i + 1] = preSums[i] + indexs[i]
            }
            for ((i, x) in indexs.withIndex()) {
                // x * i 是 Int 运算会溢出,需要乘以 1 转换为 Long 运算
                val left = 1L * x * i - preSums[i]
                val right = (preSums[m] - preSums[i + 1]) - 1L * x * (m - 1 - i)
                ret[x] = left + right
            }
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:$O(n)$ 其中 n 为 nums 数组的长度,分组、前缀和的时间是 $O(n)$,每个位置的距离和计算时间为 $O(1)$;
  • 空间复杂度:$O(n)$ 不考虑分组空间,需要前缀和数组 $O(n)$。

题解三(前缀和 + DP)

将 left + right 的计算公式合并,则有

ret[x] = x * i - preSums[i] + (preSums[m] - preSums[i + 1]) - x * (m - 1 - i)

化简得:

ret[x] = (preSums[m] - preSums[i + 1]) - preSums[i] + x (2 * i - m + 1)

发现可以直接维护元素左右两边的元素之和,省去前缀和数据空间。

class Solution {
    fun distance(nums: IntArray): LongArray {
        val n = nums.size
        // 分组
        val map = HashMap<Int, ArrayList<Int>>()
        for (index in nums.indices) {
            map.getOrPut(nums[index]) { ArrayList<Int>() }.add(index)
        }
        val ret = LongArray(n)
        // 前缀和 DP
        for ((_, indexs) in map) {
            val m = indexs.size
            var leftSum = 0L
            var rightSum = 0L
            for (element in indexs) {
                rightSum += element
            }
            for ((i, x) in indexs.withIndex()) {
                rightSum -= x
                ret[x] = rightSum - leftSum + 1L * x * (2 * i - m + 1)
                leftSum += x
            }
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:$O(n)$ 其中 n 为 nums 数组的长度,分组时间是 $O(n)$,每个位置的距离和计算时间为 $O(1)$;
  • 空间复杂度:$O(1)$ 不考虑分组空间。

相似题目:

  • 1685. 有序数组中差绝对值之和

2616. 最小化数对的最大差值(Medium)

题目地址

https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/description/

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对,每个下标对对应数值取差值,你需要使得这 p 个差值的 最大值 最小。同时,你需要确保每个下标在这 p 个下标对中最多出现一次。

对于一个下标对 i 和 j ,这一对的差值为 |nums[i] - nums[j]| ,其中 |x| 表示 x 的 绝对值 。

请你返回 p 个下标对对应数值 最大差值 的 最小值 。

问题分析

二分思路:“极大化最小值” 和 “极小化最小值” 存在单调性,是典型的二分查找问题。

  • 二分的值越大,越能 / 越不能满足条件;
  • 二分的值越小,越不能 / 越能满足条件。

贪心思路:由于元素位置不影响结果,可以先排序,尽量选相邻元素。

题解(二分 + 贪心)

如何二分?

  • 二分的 left:0,无法构造出更小的差值;
  • 二分的 right:数组的最大值 - 数组的最小值,无法构造出更大的差值;
  • 我们可以选择一个差值 max,再检查差值 max 是否能够构造出来:
    • 如果存在差值为 max 的方案:那么小于 max 的差值都不能构造(无法构造出更小的差值);
    • 如果不存在差值为 max 的方案:那么大于 max 的差值都能构造(任意调整数对使得差值变大即可);

如何判断 “差值为 max 的方案”,即 “存在至少 p 个数对,它们的最大差值为 max 的方案” 存在?

这里需要思维转换,由于我们希望差值尽可能小,所谓我们不需要真的去构造差值为 max 的方案,而是尽可能构造出差值不超过 max 的方案,只要差值不超过 max 的方案数大于等于 p 个,那么至少有不高于 max 的差值方案存在。

举个例子,在数列 [1, 1, 2, 3, 7, 10] 中,p = 2,检查的差值 max = 5。此时我们构造数列对 {1, 1} {2, 3} 满足差值不超过 max 且方案数大于等于 p 个,那么 max 就是可构造的,且存在比 max 更优的方案。

所以,现在的问题转换为如何构造出尽可能多的数列数,使得它们的差值不超过 max?

如果当前元素 x 参与配对,那么配对相邻数的差值是最小的,否则 x 与不相邻数匹配无法得到更优解。

class Solution {
    fun minimizeMax(nums: IntArray, p: Int): Int {
        if (p == 0) return 0
        // 排序
        nums.sort()
        val n = nums.size
        // 二分查找
        var left = 0
        var right = nums[n - 1] - nums[0]
        while (left < right) {
            val mid = (left + right) ushr 1
            if (check(nums, p, mid)) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }

    // 检查
    private fun check(nums: IntArray, p: Int, max: Int): Boolean {
        var cnt = 0
        var i = 0
        while (i < nums.size - 1) {
            if (nums[i + 1] - nums[i] <= max) {
                // 选
                i += 2
                cnt += 1
            } else {
                i += 1
            }
            if (cnt == p) return true
        }
        return false
    }
}

复杂度分析:

  • 时间复杂度:$O(nlgn + nlgU)$ 其中 n 是 nums 数组的长度,U 是数组的最大差值。预排序时间为 $O(nlgn)$,二分次数为 $lgU$,每轮检查时间为 $O(n)$;
  • 空间复杂度:$O(lgn)$ 排序递归栈空间。

2617. 网格图中最少访问的格子数(Hard)

题目地址

https://leetcode.cn/problems/minimum-number-of-visited-cells-in-a-grid/

题目描述

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。

当你在格子 (i, j) 的时候,你可以移动到以下格子之一:

  • 满足 j < k <= grid[i][j] + j 的格子 (i, k) (向右移动),或者
  • 满足 i < k <= grid[i][j] + i 的格子 (k, j) (向下移动)。

请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数,如果无法到达右下角格子,请你返回 -1 。

问题分析

分析 1 - 题意:这道题的题意可能有点小绕,其实就是说站在 [i][j] 位置上,且 grid[i][j] = x,则最远可以走到向右 [i][j + x] 或向下 [i + x][j] 的位置上。现在求从左上角到右下角的最少移动次数,显然,这是一个在二维空间上的最短路问题,将格子之间的可达关系视为图的边,也可以视为图上的最短路问题。

初看之下这道题与经典题 45. 跳跃游戏 II 非常相似,简直是二维上的跳跃游戏问题。在 45. 这道题中,有时间复杂度 O(n) 且空间复杂度 O(1) 的动态规划解法,我也可以用图的思路去思考 45. 题(当然它的复杂度不会由于动态规划)

45. 跳跃游戏 II(最短路思路)

定义 dst[i] 表示到达 i 位置的最少跳跃次数,那么对于 i 位置可以到达的区间 (i+1, i + nums[i]),它们的最少跳跃次数最多不会高于 dst[i] + 1。

参考 Dijkstra 最短路算法的思路,我们将数组分为 “已确定集合” 和 “候选集合” 两组,那么对于已确定集合中最短路长度最小的节点 j,由于该点不存在更优解,所以可以用该点来确定其它店的最短路长度。

而且由于这道题中图的边权是 1,所以只要越早进入 “已确定集合” 中的点的最短路长度越低,不需要使用小顶堆来搜索 “已确定集合中最短路长度最小的节点”

class Solution {
    fun jump(nums: IntArray): Int {
        val n = nums.size
        val INF = Integer.MAX_VALUE
        // 候选集
        val unVisitSet = HashSet<Int>(n).apply {
            // 排除 0
            for (i in 1 until n) {
                this.add(i)
            }
        }
        // 最短路长度
        val dst = IntArray(n) { INF }
        dst[0] = 0
        // 队列
        val queue = LinkedList<Int>()
        queue.offer(0)
        while (!queue.isEmpty()) {
            // 由于边权为 1,队列中最先访问的节点一定是最短路长度最短的节点
            val from = queue.poll()
            // 更新可达范围
            for (to in from + 1..Math.min(from + nums[from], n - 1)) {
                if (!unVisitSet.contains(to)) continue
                // 最短路
                queue.offer(to)
                dst[to] = dst[from] + 1
                // 从候选集移除
                unVisitSet.remove(to)
                // 到达终点
                if (to == n - 1) break
            }
        }
        return dst[n - 1]
    }
}

复杂度分析:

  • 时间复杂度:$O(n^2)$ 其中 n 是 nums 数组的长度,每个节点最多入队一次,每次出队最多需要扫描 n - 1 个节点
  • 空间复杂度:$O(n)$

在内层循环更新可达范围时,会重复检查已经确定最短路长度的点,我们可以使用平衡二叉树优化,这就类似于上一场周赛中第 4 题 2612. 最少翻转操作数 的思路。

class Solution {
    fun jump(nums: IntArray): Int {
        val n = nums.size
        val INF = Integer.MAX_VALUE
        // 候选集(平衡二叉树)
        val unVisitSet = TreeSet<Int>().apply {
            // 排除 0
            for (i in 1 until n) {
                this.add(i)
            }
        }
        // 最短路长度
        val dst = IntArray(n) { INF }
        dst[0] = 0
        // 队列
        val queue = LinkedList<Int>()
        queue.offer(0)
        while (!queue.isEmpty()) {
            // 由于边权为 1,队列中最先访问的节点一定是最短路长度最短的节点
            val from = queue.poll()
            // 更新可达范围
            val max = Math.min(from + nums[from], n - 1)
            while (true) {
                // 大于等于 from 的第一个元素
                val to = unVisitSet.ceiling(from) ?: break
                if (to > max) break
                // 最短路
                queue.offer(to)
                dst[to] = dst[from] + 1
                // 从候选集移除
                unVisitSet.remove(to)
                // 到达终点
                if (to == n - 1) break
            }
        }
        return dst[n - 1]
    }
}

复杂度分析:

  • 时间复杂度:$O(nlgn)$ 其中 n 是 nums 数组的长度,每个节点最多入队一次,每次寻找左边界的时间是 O(lgn);
  • 空间复杂度:$O(n)$ 平衡二叉树空间。

题解(BFS + 平衡二叉树 + 队列)

理解了用最短路思路解决一维数组上的跳跃游戏 II,很容易推广到二维数组上:

  • 1、由于题目每个位置有向右和向下两个选项,所以我们需要建立 m + n 个平衡二叉树;
  • 2、由于存在向右和向下两种可能性
class Solution {
    fun minimumVisitedCells(grid: Array<IntArray>): Int {
        val n = grid.size
        val m = grid[0].size
        if (n == 1 && m == 1) return 1
        // 每一列的平衡二叉树
        val rowSets = Array(n) { TreeSet<Int>() }
        val columnSets = Array(m) { TreeSet<Int>() }
        for (row in 0 until n) {
            for (column in 0 until m) {
                if (row + column == 0) continue
                rowSets[row].add(column)
                columnSets[column].add(row)
            }
        }
        // 队列(行、列、最短路长度)
        val queue = LinkedList<IntArray>()
        queue.offer(intArrayOf(0, 0, 1))

        while (!queue.isEmpty()) {
            val node = queue.poll()
            val row = node[0]
            val column = node[1]
            val dst = node[2]
            val step = grid[row][column]

            // 向右
            var max = Math.min(column + step, m - 1)
            while (true) {
                val to = rowSets[row].ceiling(column) ?: break
                if (to > max) break
                // 最短路
                queue.offer(intArrayOf(row, to, dst + 1))
                // 从候选集移除(行列都需要移除)
                rowSets[row].remove(to)
                columnSets[column].remove(row)
                // 到达终点
                if (row == n - 1 && to == m - 1) return dst + 1
            }

            // 向下
            max = Math.min(row + step, n - 1)
            while (true) {
                val to = columnSets[column].ceiling(row) ?: break
                if (to > max) break
                // 最短路
                queue.offer(intArrayOf(to, column, dst + 1))
                // 从候选集移除(行列都需要移除)
                rowSets[row].remove(row)
                columnSets[column].remove(to)
                // 到达终点
                if (to == n - 1 && column == m - 1) return dst + 1
            }
        }
        return -1
    }
}

复杂度分析:

  • 时间复杂度:$O(nm·(lgn + lgm))$ 其中 n 是行数,m 是列数,每个点最多入队一次,每次出队需要 O(lgn + lgm) 时间确定左边界;
  • 空间复杂度:$O(nm)$ 平衡二叉树空间。

近期周赛最短路问题:

  • 2612. 最少翻转操作数(Hard)
  • 2608. 图中的最短环(Hard)
  • 2577. 在网格图中访问一个格子的最少时间(Hard)

为了 Guardian 加油!文章来源地址https://www.toymoban.com/news/detail-413345.html

到了这里,关于LeetCode 周赛 340,质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第二章 Electron自定义界面(最大化、最小化、关闭、图标等等)

    Electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 嵌入 Chromium 和 Node.js 到 二进制的 Electron 允许您保持一个 JavaScript 代码代码库并创建 在Windows上运行的跨平台应用 macOS和Linux——不需要本地开发经验(这段话是来自官网)。 这里我已经搭建好了项目 👉👉👉 快

    2024年02月05日
    浏览(55)
  • 【LeetCode周赛】LeetCode第358场周赛

    给你一个下标从0开始的整数数组nums。请你从nums中找出和最大的一对数,且这两个数数位上最大的数字相等。 返回最大和,如果不存在满足题意的数字对,返回 -1 。 示例 1: 输入:nums = [51,71,17,24,42] 输出:88 解释: i = 1 和 j = 2 ,nums[i] 和 nums[j] 数位上最大的数字相等,且这

    2024年02月12日
    浏览(45)
  • 【LeetCode周赛】LeetCode第370场周赛

    一场比赛中共有 n 支队伍,按从 0 到 n - 1 编号。 给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 = i, j = n - 1 且 i != j 的所有 i, j :如果 grid[i][j] == 1,那么 i 队比 j 队 强 ;否则,j 队比 i 队 强 。 在这场比赛中,如果不存在某支强于 a 队的队伍,则认为

    2024年02月05日
    浏览(53)
  • 【LeetCode周赛】LeetCode第359场周赛

    给你一个字符串数组 words 和一个字符串 s ,请你判断 s 是不是 words 的 首字母缩略词 。 如果可以按顺序串联 words 中每个字符串的第一个字符形成字符串 s ,则认为 s 是 words 的首字母缩略词。例如,“ab” 可以由 [“apple”, “banana”] 形成,但是无法从 [“bear”, “aardvark”

    2024年02月10日
    浏览(42)
  • Python中最全的窗口操作,如窗口最大化、最小化、窗口置顶、获取缩放比例等

    本文记录在Python中操作 Windows 应用窗口的操作。 这里的操作都是自己摸索+借助强大的搜索引擎整理出来的,我真棒!!! 名称 解释名称 ctypes Python 的外部函数库。它提供了与 C 兼容的数据类型,并允许调用 DLL 或共享库中的函数。 pywin32 是Win32(PYWIN32)扩展的 Python 的ream

    2024年01月16日
    浏览(38)
  • 使用串口烧写程序到STM32F103C8T6最小板(CH340)

    商家没给ST‐LINK V2下载器,故使用串口将程序烧录到最小板,使用仿真软件Flymcu进行。(默认安装过CH340的驱动) 联机下载时的程序文件:编译生成的.hex文件; 编程前重装文件:当选中该项后,flymcu会在每次编程之前将Hex文件重新装载一遍,这对于代码调试的时候比较有用

    2024年02月01日
    浏览(58)
  • 204. 计数质数 (埃式筛法详解)——【Leetcode每日一题】

    素数最朴素判断思路:(一般会超时) 对正整数 n ,如果用 2 到 n sqrt{n} n ​ 之间的所有整数去除,均无法整除,则 n 为素数又称为质数。 为什么到 n sqrt{n} n ​ 就可以了,因为因数如果存在一定是成对出现的,如果存在小于根号n的因数,那么n除以它一定大于根号n。 首先

    2023年04月08日
    浏览(35)
  • C# winform窗体UI美化后实现最大化、最小化、还原、关闭、窗体移动等等-2023/1/11

    在做winform窗体UI美化时,一般都需要将窗体的FormBorderStyle属性设为None,之后窗体就会没有最上面的标题栏,然后按照UI进行界面的设计。美化的代价就是窗体本来标题栏的相关操作,例如双击自动最大化,再次双击又恢复正常大小,以及上窗体关闭、最小化等功能就都需要自

    2024年02月08日
    浏览(55)
  • [LeetCode108双周赛&LeetCode353周赛] 学习用记忆化搜索解决 DP 问题

    参考灵神直播和代码 @cache 装饰器的作用:将传入不同参数得到的函数值存储到缓存,避免下次传递相同参数重复计算结果,可用于解决递归函数重复计算问题,比如递归求斐波那契问题。 https://leetcode.cn/problems/maximum-number-of-jumps-to-reach-the-last-index/ 记忆化搜索 dfs(i) 表示以

    2024年02月13日
    浏览(38)
  • [LeetCode周赛复盘] 第 348场周赛20230604

    这场可惜了。 T1 模拟。 T2 模拟。 T3 倒序计算。 T4 同时限制上下界的数位DP。 6462. 最小化字符串长度 1. 题目描述 2. 思路分析 题意仔细想一下就会发现,其实会将每个字符仅留1个。 3. 代码实现 6424. 半有序排列 1. 题目描述 2. 思路分析 由于只能相邻交换来移动,因此每次只能

    2024年02月08日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包