当前位置: 首页 > 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节省运维…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

spring:实例工厂方法获取bean

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

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...