修改数据范围,可以从「简单 BFS」变为「挖掘性质」的贪心 DP 题|Java 刷题打卡

简介: 修改数据范围,可以从「简单 BFS」变为「挖掘性质」的贪心 DP 题|Java 刷题打卡

题目描述



这是 LeetCode 上的 45. 跳跃游戏 II ,难度为 中等


Tag : 「贪心」、「线性 DP」、「双指针」


给定一个非负整数数组,你最初位于数组的第一个位置。


数组中的每个元素代表你在该位置可以跳跃的最大长度。


你的目标是使用最少的跳跃次数到达数组的最后一个位置。


假设你总是可以到达数组的最后一个位置。


示例 1:


输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
复制代码


示例 2:


输入: [2,3,0,1,4]
输出: 2
复制代码


提示:


  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 10510^5105


BFS



对于这一类问题,我们一般都是使用 BFS 进行求解。


本题的 BFS 解法的复杂度是 O(n2)O(n^2)O(n2),数据范围为 10310^3103,可以过。


代码:


class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int ans = 0;
        boolean[] st = new boolean[n];
        Deque<Integer> d = new ArrayDeque<>();
        st[0] = true;
        d.addLast(0);
        while (!d.isEmpty()) {
            int size = d.size();
            while (size-- > 0) {
                int idx = d.pollFirst();
                if (idx == n - 1) return ans;
                for (int i = idx + 1; i <= idx + nums[idx] && i < n; i++) {
                    if (!st[i]) {
                        st[i] = true;
                        d.addLast(i);
                    }
                }
            }
            ans++;
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:如果每个点跳跃的距离足够长的话,每次都会将当前点「后面的所有点」进行循环入队操作(由于 st 的存在,不一定都能入队,但是每个点都需要被循环一下)。复杂度为 O(n2)O(n^2)O(n2)
  • 空间复杂度:队列中最多有 n−1n - 1n1 个元素。复杂度为 O(n)O(n)O(n)


双指针 + 贪心 + 动态规划



本题数据范围只有 10310^3103,所以 O(n2)O(n^2)O(n2) 勉强能过。


如果面试官要将数据范围出到 10610^6106,又该如何求解呢?


我们需要考虑 O(n)O(n)O(n) 的做法。


其实通过 10610^6106 这个数据范围,就已经可以大概猜到是道 DP 题。


我们定义 f[i]f[i]f[i] 为到达第 iii 个位置所需要的最少步数,那么答案是 f[n−1]f[n - 1]f[n1]


学习过 路径 DP 专题 的同学应该知道,通常确定 DP 的「状态定义」有两种方法。


  • 一种是根据经验猜一个状态定义,会结合题目给定的维度,和要求的答案去猜。
  • 另外一种则是通过设计一个合理的 DFS 方法签名来确定状态定义。


这里我是采用第一种方法。


至于如何确定「状态定义」是否可靠,关键是看使用这个状态定义能否推导出合理的「状态转移方程」,来覆盖我们所有的状态。


不失一般性的考虑 f[n−1]f[n - 1]f[n1] 该如何转移:


我们知道最后一个点前面可能会有很多个点能够一步到达最后一个点。


网络异常,图片无法展示
|


也就是有 f[n−1]=min(f[n−k],...,f[n−3],f[n−2])+1f[n - 1] = min(f[n - k],...,f[n - 3],f[n - 2]) + 1f[n1]=min(f[nk],...,f[n3],f[n2])+1


然后我们再来考虑集合 f[n−k],...,f[n−3],f[n−2]f[n - k],...,f[n - 3],f[n - 2]f[nk],...,f[n3],f[n2] 有何特性。


不然发现其实必然有 f[n−k]<=...<=f[n−3]<=f[n−2]f[n - k] <= ...<= f[n - 3] <= f[n - 2]f[nk]<=...<=f[n3]<=f[n2]


推而广之,不止是经过一步能够到达最后一个点的集合,其实任意连续的区间都有这个性质。


举个🌰,比如我经过至少 5 步到达第 iii 个点,那么必然不可能出现使用步数少于 5 步就能达到第 i+1i + 1i+1 个点的情况。到达第 i+1i + 1i+1 个点的至少步数必然是 5 步或者 6 步。


搞清楚性质之后,再回头看我们的状态定义:f[i]f[i]f[i] 为到达第 iii 个位置所需要的最少步数。


因此当我们要求某一个 f[i]f[i]f[i] 的时候,我们需要找到最早能够经过一步到达 iii 点的 jjj 点。


即有状态转移方程:f[i]=f[j]+1f[i] = f[j] + 1f[i]=f[j]+1


也就是我们每次都贪心的取离 iii 点最远的点 jjj 来更新 f[i]f[i]f[i]


而这个找 jjj 的过程可以使用双指针来找。


因此这个思路其实是一个「双指针 + 贪心 + 动态规划」的一个解法。


代码:


class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] f = new int[n]; 
        for (int i = 1, j = 0; i < n; i++) {
            while (j + nums[j] < i) j++;
            f[i] = f[j] + 1;
        }
        return f[n - 1];
    }
}
复制代码


  • 时间复杂度:O(n)O(n)O(n)
  • 空间复杂度:O(n)O(n)O(n)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.45 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
27天前
|
Java API 开发工具
【Azure Developer】Java代码实现获取Azure 资源的指标数据却报错 "invalid time interval input"
在使用 Java 调用虚拟机 API 获取指标数据时,因本地时区设置非 UTC,导致时间格式解析错误。解决方法是在代码中手动指定时区为 UTC,使用 `ZoneOffset.ofHours(0)` 并结合 `withOffsetSameInstant` 方法进行时区转换,从而避免因时区差异引发的时间格式问题。
135 3
|
1月前
|
算法 Java
Java多线程编程:实现线程间数据共享机制
以上就是Java中几种主要处理多线程序列化资源以及协调各自独立运行但需相互配合以完成任务threads 的技术手段与策略。正确应用上述技术将大大增强你程序稳定性与效率同时也降低bug出现率因此深刻理解每项技术背后理论至关重要.
92 16
|
2月前
|
数据采集 JSON Java
Java爬虫获取1688店铺所有商品接口数据实战指南
本文介绍如何使用Java爬虫技术高效获取1688店铺商品信息,涵盖环境搭建、API调用、签名生成及数据抓取全流程,并附完整代码示例,助力市场分析与选品决策。
|
2月前
|
数据采集 存储 前端开发
Java爬虫性能优化:多线程抓取JSP动态数据实践
Java爬虫性能优化:多线程抓取JSP动态数据实践
|
传感器 分布式计算 安全
Java 大视界 -- Java 大数据在智能安防入侵检测系统中的多源数据融合与分析技术(171)
本文围绕 Java 大数据在智能安防入侵检测系统中的应用展开,剖析系统现状与挑战,阐释多源数据融合及分析技术,结合案例与代码给出实操方案,提升入侵检测效能。
|
6月前
|
自然语言处理 Java 关系型数据库
Java|小数据量场景的模糊搜索体验优化
在小数据量场景下,如何优化模糊搜索体验?本文分享一个简单实用的方案,虽然有点“土”,但效果还不错。
93 0
|
7月前
|
前端开发 Cloud Native Java
Java||Springboot读取本地目录的文件和文件结构,读取服务器文档目录数据供前端渲染的API实现
博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
Java||Springboot读取本地目录的文件和文件结构,读取服务器文档目录数据供前端渲染的API实现
|
21天前
|
数据采集 存储 弹性计算
高并发Java爬虫的瓶颈分析与动态线程优化方案
高并发Java爬虫的瓶颈分析与动态线程优化方案
Java 数据库 Spring
59 0
|
2月前
|
缓存 并行计算 安全
关于Java多线程详解
本文深入讲解Java多线程编程,涵盖基础概念、线程创建与管理、同步机制、并发工具类、线程池、线程安全集合、实战案例及常见问题解决方案,助你掌握高性能并发编程技巧,应对多线程开发中的挑战。

热门文章

最新文章