跳跃游戏 + 45. 跳跃游戏 II
给你一个非负整数数组 nums
,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true
;否则,返回 false
。
示例 1:
输入:nums = [2,3,1,1,4] 输出:true 解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4] 输出:false 解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
解析:
每次遍历,只需要贪心跳到最远即可。
class Solution {
public:bool canJump(vector<int>& nums) {int len = nums[0];for(int i = 1;i < nums.size();i++){if(len >= i){len = max(len,nums[i]+i);}}return len >= nums.size()-1;}
};
时间复杂度为O(n)
45. 跳跃游戏 II
给定一个长度为 n
的 0 索引整数数组 nums
。初始位置为 nums[0]
。
每个元素 nums[i]
表示从索引 i
向前跳转的最大长度。换句话说,如果你在 nums[i]
处,你可以跳转到任意 nums[i + j]
处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1]
的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]
。
示例 1:
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是2
。从下标为 0 跳到下标为 1 的位置,跳1
步,然后跳3
步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4] 输出: 2
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
- 题目保证可以到达
nums[n-1]
解析:
这个是跳到最后一个位置的最小次数。
反向思想,从后向前,当前位置可以是哪个最先的下标跳跃而来的。
class Solution {
public:int jump(vector<int>& nums) {int p = nums.size()-1;int ans = 0;while(p > 0){for(int i = 0;i < p;i++){if(i+nums[i] >= p){p = i;ans++;break;}}}return ans;}
};
时间复杂度为O(n*n);
在进行优化,我们可以这么想。我们每次跳到最远的。在从当前位置遍历到的第一次跳到最远的。
在这个最远的区间内,我们又可以更行更远的。以此类推,贪心正向遍历,时间复杂度为O(n)
class Solution {
public:int jump(vector<int>& nums) {int m = 0,r = 0;int ans = 0;for(int i = 0;i < nums.size()-1;i++) //最后一步不用跳{m = max(m,i+nums[i]);if(i == r) // r为区间的左端点{r = m;ans++;}}return ans;}
};
2580. 统计将重叠区间合并成组的方案数
给你一个二维整数数组 ranges
,其中 ranges[i] = [starti, endi]
表示 starti
到 endi
之间(包括二者)的所有整数都包含在第 i
个区间中。
你需要将 ranges
分成 两个 组(可以为空),满足:
- 每个区间只属于一个组。
- 两个有 交集 的区间必须在 同一个 组内。
如果两个区间有至少 一个 公共整数,那么这两个区间是 有交集 的。
- 比方说,区间
[1, 3]
和[2, 5]
有交集,因为2
和3
在两个区间中都被包含。
请你返回将 ranges
划分成两个组的 总方案数 。由于答案可能很大,将它对 109 + 7
取余 后返回。
示例 1:
输入:ranges = [[6,10],[5,15]] 输出:2 解释: 两个区间有交集,所以它们必须在同一个组内。 所以有两种方案: - 将两个区间都放在第 1 个组中。 - 将两个区间都放在第 2 个组中。
示例 2:
输入:ranges = [[1,3],[10,20],[2,5],[4,8]] 输出:4 解释: 区间 [1,3] 和 [2,5] 有交集,所以它们必须在同一个组中。 同理,区间 [2,5] 和 [4,8] 也有交集,所以它们也必须在同一个组中。 所以总共有 4 种分组方案: - 所有区间都在第 1 组。 - 所有区间都在第 2 组。 - 区间 [1,3] ,[2,5] 和 [4,8] 在第 1 个组中,[10,20] 在第 2 个组中。 - 区间 [1,3] ,[2,5] 和 [4,8] 在第 2 个组中,[10,20] 在第 1 个组中。
提示:
1 <= ranges.length <= 105
ranges[i].length == 2
0 <= starti <= endi <= 109
解析:
区间要不重和,所以不重和的区间有两种选择,去第一个还是去第二个。我们对左端点进行排排序。当前区间右端点判断是否和下一个区间的左端的有重合。如果没有,则可以看错新的全,他可以去第一个也可以去第二个。
class Solution {
public:
const int MOD = 1e9 + 7;int countWays(vector<vector<int>>& ranges) {sort(ranges.begin(),ranges.end(),[](auto &a,auto &b){return a[0] < b[0];});int ans = 2,max_r = ranges[0][1];for(auto &p : ranges){if(p[0] > max_r){ans = ans*2%MOD;}max_r = max(max_r,p[1]);}return ans;}
};
时间复杂度为O(n*logn)
相关文章:
跳跃游戏 + 45. 跳跃游戏 II
给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 示例 1: 输…...
在Django中使用多语言(i18n)
在Django中使用多语言 配置中间件 MIDDLEWARE [......django.contrib.sessions.middleware.SessionMiddleware,django.middleware.locale.LocaleMiddleware, # 此行重点django.middleware.common.CommonMiddleware,...... ]配置翻译文件目录 根目录下创建目录locale # 国…...

高性价比AWS Lambda无服务体验
前言 之前听到一个讲座说到AWS Lambda服务,基于Serverless无服务模型,另外官网还免费提供 100 万个请求 按月,包含在 AWS 免费套餐中是真的很香,对于一些小型的起步的网站或者用户量不大的网站,简直就是免费ÿ…...

【物联网】EMQX(二)——docker快速搭建EMQX 和 MQTTX客户端使用
一、前言 在上一篇文章中,小编向大家介绍了物联网必然会用到的消息服务器EMQ,相信大家也对EMQ有了一定的了解,那么接下来,小编从这篇文章正式开始展开对EMQ的学习教程,本章节来记录一下如何对EMQ进行安装。 二、使用…...

2023 亚马逊云科技 re:lnvent 大会探秘: Amazon Connect 全渠道云联络中心
2023 亚马逊云科技 re:lnvent 大会探秘: Amazon Connect 全渠道云联络中心 前言一. Amazon Connect 介绍 🗺️二. Amazon Connect 使用教程 🗺️1.我们打开URl链接找到对应服务2.输入Amazon Connect选中第一个点击进入即可;3.在进入之后我们就…...
鸿蒙开发之用户隐私权限申请
一、简介 鸿蒙开发过程中可用于请求的权限一共有两种:normal和system_basic。以下内容摘自官网: normal权限 normal 权限允许应用访问超出默认规则外的普通系统资源。这些系统资源的开放(包括数据和功能)对用户隐私以及其他应用带…...
Docker笔记:简单部署 nodejs 项目和 golang 项目
docker 简单的维护 nodejs 项目容器 1 )Nodejs 程序 const express require(express) const app express()app.get(/, (req, res) > {res.send(首页) })app.get(/news, (req, res) > {res.send(news) })// dokcer 做端口映射不要指定ip app.listen(3000)2…...

java内置的数据结构
Java语言提供了许多内置的数据结构,包括: 1. 数组(Array):数组是最基本的数据结构之一,它是一个有序的元素集合,每个元素都有一个对应的索引。在Java中,数组可以通过声明和初始化来创…...

轻松搭建FPGA开发环境:第三课——Vivado 库编译与设置说明
工欲善其事必先利其器,很多人想从事FPGA的开发,但是不知道如何下手。既要装这个软件,又要装那个软件,还要编译仿真库,网上的教程一大堆,不知道到底应该听谁的。所以很多人还没开始就被繁琐的开发环境搭建吓…...
【PostgreSQL】从零开始:(十一)PostgreSQL-Dropdb命令删除数据库
dropdb命令删除数据库 命令 [postgrespostgre-sql bin]$ dropdb --help dropdb removes a PostgreSQL database.Usage:dropdb [OPTION]... DBNAMEOptions:-e, --echo show the commands being sent to the server-f, --force try to terminate …...
UDP网络编程其他相关事项
netstat指令 netstat -an 可以查看当前主机网络情况,包括端口监听情况和网络连接情况。 netstat -an | more 可以分页显示。 要求在dos控制台下执行。 说明:(1)Listening表示某个端口在监听;(2…...
Redhat LINUX 9.3 + PG 16.1 搭建主备流复制
一直想搭建一个PG流复制,最近正好有一个新环境,操作系统是最新的,rhel 9.3,数据库是最新的 pg 16.1,借鉴了网上的步骤,尤其是小工到专家的内容,在此谢过。 1.安装环境 1)IP: 主:192.168.133.151…...
kafka设置消费者组
安装部署后 consumer.properties group.idtest-group 单机测试,自己开俩窗口,一个测试消费者,一个测试生产者(创建消息那步) 创建主题 bin/kafka-topics.sh --create --bootstrap-server localhost:9092 --replica…...
Worker-Thread设计模式
Worker-Thread模式类似于工厂流水线,有时也称为流水线设计模式。线程池在某种意义上也算是Worker-Thread模式的一种实现,线程池初始化时创建线程类似于在流水线等待工作的工人,提交给线程池的Runnable接口类似于需要加工的产品,Ru…...
npm 安装包遇到问题的常用脚本(RequestError: socket hang up)
前言 最近在给一个基于 Electron 的开源项目做贡献,需要去安装一些 npm 库,由于众所周知的原因,经常会出现报错: npm ERR! path D:\Projects\project\node_modules\electron npm ERR! command failed npm ERR! command C:\Windo…...

活动 | Mint Blockchain 将于 2024 年 1 月 10 号启动 MintPass 限时铸造活动
MintPass 是由 Mint Blockchain 官方发行的 Mint 网络和社区的 NFT 通行证,将在 2024 年 1 月份启动限时铸造活动。今天这篇文章会着重向大家介绍即将举办的 MintPass 活动的基础信息。 MintPass 有 2 种类型: 类型 1:Mint Genesis NFT Mint…...

Android动画(四)——属性动画ValueAnimator的妙用
目录 介绍 效果图 代码实现 xml文件 介绍 ValueAnimator是ObjectAnimator的父类,它继承自Animator。ValueAnimaotor同样提供了ofInt、ofFloat、ofObject等静态方法,传入的参数是动画过程的开始值、中间值、结束值来构造动画对象。可以将ValueAnimator看…...
C语言飞机大战
一、前言 [设计难度 : ★☆☆☆☆ [参考书籍:《C语言课程设计与游戏开发实践教程》 [主要涉及知识:函数封装 循环判断语句 [程序运行效果图: [主要的游戏功能: 通过按键’w’,‘s’,‘a’,d’分别实现飞机的上下左右移动 按空格…...
js 原型 和 原型链
function Person(name,age){ this.name name this.age age } var p new Person(张三,11) //创建构造函数的时候,解析器会自动为构造函数创建prototype属性,prototype属性对应的对象就是原型对象 // prototype 翻译为 原…...
如何利用SD-WAN节省运维成本和简化运维工作?
在当今数字化时代,企业对于网络的要求越来越高,需要保障网络的安全性、可靠性和灵活性。同时,随着企业的上云和远程办公等需求的增加,传统的WAN网络已经无法满足企业的需求。因此,SD-WAN技术应运而生。 SD-WAN节省运维…...

微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent
安全大模型训练计划:基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标:为安全大模型创建高质量、去偏、符合伦理的训练数据集,涵盖安全相关任务(如有害内容检测、隐私保护、道德推理等)。 1.1 数据收集 描…...