当前位置: 首页 > news >正文

跳跃游戏 + 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 &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输…...

在Django中使用多语言(i18n)

在Django中使用多语言 配置中间件 MIDDLEWARE [......django.contrib.sessions.middleware.SessionMiddleware,django.middleware.locale.LocaleMiddleware, # 此行重点django.middleware.common.CommonMiddleware,...... ]配置翻译文件目录 根目录下创建目录locale # 国…...

高性价比AWS Lambda无服务体验

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

【物联网】EMQX(二)——docker快速搭建EMQX 和 MQTTX客户端使用

一、前言 在上一篇文章中&#xff0c;小编向大家介绍了物联网必然会用到的消息服务器EMQ&#xff0c;相信大家也对EMQ有了一定的了解&#xff0c;那么接下来&#xff0c;小编从这篇文章正式开始展开对EMQ的学习教程&#xff0c;本章节来记录一下如何对EMQ进行安装。 二、使用…...

2023 亚马逊云科技 re:lnvent 大会探秘: Amazon Connect 全渠道云联络中心

2023 亚马逊云科技 re:lnvent 大会探秘: Amazon Connect 全渠道云联络中心 前言一. Amazon Connect 介绍 &#x1f5fa;️二. Amazon Connect 使用教程 &#x1f5fa;️1.我们打开URl链接找到对应服务2.输入Amazon Connect选中第一个点击进入即可&#xff1b;3.在进入之后我们就…...

鸿蒙开发之用户隐私权限申请

一、简介 鸿蒙开发过程中可用于请求的权限一共有两种&#xff1a;normal和system_basic。以下内容摘自官网&#xff1a; normal权限 normal 权限允许应用访问超出默认规则外的普通系统资源。这些系统资源的开放&#xff08;包括数据和功能&#xff09;对用户隐私以及其他应用带…...

Docker笔记:简单部署 nodejs 项目和 golang 项目

docker 简单的维护 nodejs 项目容器 1 &#xff09;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语言提供了许多内置的数据结构&#xff0c;包括&#xff1a; 1. 数组&#xff08;Array&#xff09;&#xff1a;数组是最基本的数据结构之一&#xff0c;它是一个有序的元素集合&#xff0c;每个元素都有一个对应的索引。在Java中&#xff0c;数组可以通过声明和初始化来创…...

轻松搭建FPGA开发环境:第三课——Vivado 库编译与设置说明

工欲善其事必先利其器&#xff0c;很多人想从事FPGA的开发&#xff0c;但是不知道如何下手。既要装这个软件&#xff0c;又要装那个软件&#xff0c;还要编译仿真库&#xff0c;网上的教程一大堆&#xff0c;不知道到底应该听谁的。所以很多人还没开始就被繁琐的开发环境搭建吓…...

【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 可以查看当前主机网络情况&#xff0c;包括端口监听情况和网络连接情况。 netstat -an | more 可以分页显示。 要求在dos控制台下执行。 说明&#xff1a;&#xff08;1&#xff09;Listening表示某个端口在监听&#xff1b;&#xff08;2&#xf…...

Redhat LINUX 9.3 + PG 16.1 搭建主备流复制

一直想搭建一个PG流复制&#xff0c;最近正好有一个新环境&#xff0c;操作系统是最新的,rhel 9.3&#xff0c;数据库是最新的 pg 16.1,借鉴了网上的步骤&#xff0c;尤其是小工到专家的内容&#xff0c;在此谢过。 1.安装环境 1&#xff09;IP: 主&#xff1a;192.168.133.151…...

kafka设置消费者组

安装部署后 consumer.properties group.idtest-group 单机测试&#xff0c;自己开俩窗口&#xff0c;一个测试消费者&#xff0c;一个测试生产者&#xff08;创建消息那步&#xff09; 创建主题 bin/kafka-topics.sh --create --bootstrap-server localhost:9092 --replica…...

Worker-Thread设计模式

Worker-Thread模式类似于工厂流水线&#xff0c;有时也称为流水线设计模式。线程池在某种意义上也算是Worker-Thread模式的一种实现&#xff0c;线程池初始化时创建线程类似于在流水线等待工作的工人&#xff0c;提交给线程池的Runnable接口类似于需要加工的产品&#xff0c;Ru…...

npm 安装包遇到问题的常用脚本(RequestError: socket hang up)

前言 最近在给一个基于 Electron 的开源项目做贡献&#xff0c;需要去安装一些 npm 库&#xff0c;由于众所周知的原因&#xff0c;经常会出现报错&#xff1a; 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 通行证&#xff0c;将在 2024 年 1 月份启动限时铸造活动。今天这篇文章会着重向大家介绍即将举办的 MintPass 活动的基础信息。 MintPass 有 2 种类型&#xff1a; 类型 1&#xff1a;Mint Genesis NFT Mint…...

Android动画(四)——属性动画ValueAnimator的妙用

目录 介绍 效果图 代码实现 xml文件 介绍 ValueAnimator是ObjectAnimator的父类&#xff0c;它继承自Animator。ValueAnimaotor同样提供了ofInt、ofFloat、ofObject等静态方法&#xff0c;传入的参数是动画过程的开始值、中间值、结束值来构造动画对象。可以将ValueAnimator看…...

C语言飞机大战

一、前言 [设计难度 : ★☆☆☆☆ [参考书籍&#xff1a;《C语言课程设计与游戏开发实践教程》 [主要涉及知识&#xff1a;函数封装 循环判断语句 [程序运行效果图&#xff1a; [主要的游戏功能&#xff1a; 通过按键’w’,‘s’,‘a’,d’分别实现飞机的上下左右移动 按空格…...

js 原型 和 原型链

function Person(name,age){ this.name name this.age age } var p new Person(张三,11) //创建构造函数的时候&#xff0c;解析器会自动为构造函数创建prototype属性&#xff0c;prototype属性对应的对象就是原型对象 // prototype 翻译为 原…...

如何利用SD-WAN节省运维成本和简化运维工作?

在当今数字化时代&#xff0c;企业对于网络的要求越来越高&#xff0c;需要保障网络的安全性、可靠性和灵活性。同时&#xff0c;随着企业的上云和远程办公等需求的增加&#xff0c;传统的WAN网络已经无法满足企业的需求。因此&#xff0c;SD-WAN技术应运而生。 SD-WAN节省运维…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

Python 高级应用10:在python 大型项目中 FastAPI 和 Django 的相互配合

无论是python&#xff0c;或者java 的大型项目中&#xff0c;都会涉及到 自身平台微服务之间的相互调用&#xff0c;以及和第三发平台的 接口对接&#xff0c;那在python 中是怎么实现的呢&#xff1f; 在 Python Web 开发中&#xff0c;FastAPI 和 Django 是两个重要但定位不…...

Linux基础开发工具——vim工具

文章目录 vim工具什么是vimvim的多模式和使用vim的基础模式vim的三种基础模式三种模式的初步了解 常用模式的详细讲解插入模式命令模式模式转化光标的移动文本的编辑 底行模式替换模式视图模式总结 使用vim的小技巧vim的配置(了解) vim工具 本文章仍然是继续讲解Linux系统下的…...