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

Golang每日一练(leetDay0019)

目录

55. 跳跃游戏 Jump Game  🌟🌟

56. 合并区间 Mmerge Intervals  🌟🌟

57. 插入区间 Insert Interval  🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏


55. 跳跃游戏 Jump Game

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

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

判断你是否能够到达最后一个下标。

示例 1:

输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:

输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

提示:

  • 1 <= nums.length <= 3 * 10^4
  • 0 <= nums[i] <= 10^5

代码1:

贪心算法,记录每个位置能跳到的最远距离,如果当前位置已经超过了当前能跳到的最远距离,说明无法到达终点,返回 false。 

func canJump(nums []int) bool {n := len(nums)maxPos := 0for i := 0; i < n; i++ {if i > maxPos {return false}maxPos = max(maxPos, i+nums[i])}return true
}
func max(a, b int) int {if a > b {return a}return b
}

 代码2:

回溯算法,从第一个位置开始,依次尝试跳到后面的每一个位置,如果遇到无法跳到的位置,则回溯到上一个位置,直到跳到终点或无法回溯为止。

func canJump(nums []int) bool {return backtrack(nums, 0)
}
func backtrack(nums []int, pos int) bool {if pos == len(nums)-1 {return true}furthestJump := min(pos+nums[pos], len(nums)-1)for nextPos := furthestJump; nextPos > pos; nextPos-- {if backtrack(nums, nextPos) {return true}}return false
}
func min(a, b int) int {if a < b {return a}return b
}

 代码3:

动态规划,定义状态 dp[i] 表示能否从起点跳到第 i 个位置。转移方程为 dp[i] = dp[j] && j + nums[j] >= i,其中 j 为能够跳到的位置。

func canJump(nums []int) bool {n := len(nums)maxPos := 0for i := 0; i < n; i++ {if i > maxPos {return false}maxPos = max(maxPos, i+nums[i])}return true
}
func max(a, b int) int {if a > b {return a}return b
}

 代码4:

反向贪心算法,从终点开始向前遍历,记录能够跳到终点的最小位置,如果当前位置能够跳到这个最小位置,则更新最小位置,最后判断起点是否能够跳到这个最小位置即可。 

func canJump(nums []int) bool {n := len(nums)lastPos := n - 1for i := n - 2; i >= 0; i-- {if i+nums[i] >= lastPos {lastPos = i}}return lastPos == 0
}

56. 合并区间 Mmerge Intervals

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:

输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示:

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 10^4

代码1:

排序 + 双指针 首先将区间按照起始位置从小到大排序,然后使用双指针对区间进行合并。具体来说,定义左右指针 left 和 right,初始时 left 指向第一个区间的起始位置,right 指向第一个区间的结束位置。然后依次遍历每个区间,如果当前区间的起始位置小于等于 right,则将 right 更新为当前区间的结束位置,否则将当前区间的起始位置和结束位置作为一个新区间加入结果集,并将左右指针更新为当前区间的起始位置和结束位置。最后将最后一个区间加入结果集即可。

func merge(intervals [][]int) [][]int {sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] < intervals[j][0]})res := [][]int{}left, right := intervals[0][0], intervals[0][1]for i := 1; i < len(intervals); i++ {if intervals[i][0] <= right {if intervals[i][1] > right {right = intervals[i][1]}} else {res = append(res, []int{left, right})left, right = intervals[i][0], intervals[i][1]}}res = append(res, []int{left, right})return res
}

代码2:

排序 + 栈 首先将区间按照起始位置从小到大排序,然后使用栈对区间进行合并。具体来说,依次遍历每个区间,如果当前区间的起始位置小于等于栈顶区间的结束位置,则将栈顶区间的结束位置更新为当前区间的结束位置,否则将当前区间加入栈中。最后将栈中所有区间加入结果集即可。 

func merge(intervals [][]int) [][]int {sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] < intervals[j][0]})stack := [][]int{}for _, interval := range intervals {if len(stack) == 0 || interval[0] > stack[len(stack)-1][1] {stack = append(stack, interval)} else {stack[len(stack)-1][1] = max(stack[len(stack)-1][1], interval[1])}}return stack
}
func max(a, b int) int {if a > b {return a}return b
}

 代码3:

排序 + 遍历 首先将区间按照起始位置从小到大排序,然后依次遍历每个区间,如果当前区间的起始位置小于等于结果集中最后一个区间的结束位置,则将结果集中最后一个区间的结束位置更新为当前区间的结束位置,否则将当前区间加入结果集。最后输出结果集即可。 

func merge(intervals [][]int) [][]int {sort.Slice(intervals, func(i, j int) bool {return intervals[i][0] < intervals[j][0]})res := [][]int{}for _, interval := range intervals {if len(res) == 0 || interval[0] > res[len(res)-1][1] {res = append(res, interval)} else {res[len(res)-1][1] = max(res[len(res)-1][1], interval[1])}}return res
}
func max(a, b int) int {if a > b {return a}return b
}


57. 插入区间 Insert Interval

给你一个 无重叠的 ,按照区间起始端点排序的区间列表。

在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

示例 1:

输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
输出:[[1,5],[6,9]]

示例 2:

输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]
解释:这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

示例 3:

输入:intervals = [], newInterval = [5,7]
输出:[[5,7]]

示例 4:

输入:intervals = [[1,5]], newInterval = [2,3]
输出:[[1,5]]

示例 5:

输入:intervals = [[1,5]], newInterval = [2,7]
输出:[[1,7]]

提示:

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= intervals[i][0] <= intervals[i][1] <= 10^5
  • intervals 根据 intervals[i][0] 按 升序 排列
  • newInterval.length == 2
  • 0 <= newInterval[0] <= newInterval[1] <= 10^5

代码1:

二分查找  先通过二分查找找到新区间需要插入的位置,然后按照方法一的方式插入新区间并合并重叠的区间。 

func insert(intervals [][]int, newInterval []int) [][]int {n := len(intervals)res := make([][]int, 0)// 找到新区间需要插入的位置left := 0right := n - 1for left <= right {mid := left + (right-left)/2if intervals[mid][1] < newInterval[0] {left = mid + 1} else {right = mid - 1}}insertIndex := left// 插入新区间i := 0for i < insertIndex {res = append(res, intervals[i])i++}if i < n && intervals[i][0] <= newInterval[1] {newInterval[0] = min(intervals[i][0], newInterval[0])newInterval[1] = max(intervals[i][1], newInterval[1])i++}res = append(res, newInterval)// 合并重叠的区间for i < n {if intervals[i][0] <= res[len(res)-1][1] {res[len(res)-1][1] = max(intervals[i][1], res[len(res)-1][1])} else {res = append(res, intervals[i])}i++}return res
}
func min(a, b int) int {if a < b {return a}return b
}
func max(a, b int) int {if a > b {return a}return b
}

 代码2:

双指针 由于区间列表是按照起始端点排序的,因此可以使用双指针的方法,分别找到新区间需要插入的位置和合并重叠的区间。 

func insert(intervals [][]int, newInterval []int) [][]int {n := len(intervals)res := make([][]int, 0)// 找到新区间需要插入的位置i := 0for i < n && intervals[i][1] < newInterval[0] {res = append(res, intervals[i])i++}// 合并重叠的区间for i < n && intervals[i][0] <= newInterval[1] {newInterval[0] = min(intervals[i][0], newInterval[0])newInterval[1] = max(intervals[i][1], newInterval[1])i++}res = append(res, newInterval)// 合并剩余的区间for i < n {res = append(res, intervals[i])i++}// 再次合并重叠的区间n = len(res)i = 1for i < n {if res[i][0] <= res[i-1][1] {res[i-1][1] = max(res[i][1], res[i-1][1])res = append(res[:i], res[i+1:]...)n--} else {i++}}return res
}
func min(a, b int) int {if a < b {return a}return b
}
func max(a, b int) int {if a > b {return a}return b
}

 代码3:

暴力插入 遍历区间列表,找到新区间需要插入的位置,然后插入新区间。再遍历一遍区间列表,合并重叠的区间。 

func insert(intervals [][]int, newInterval []int) [][]int {n := len(intervals)res := make([][]int, 0)// 找到新区间需要插入的位置i := 0for i < n && intervals[i][1] < newInterval[0] {res = append(res, intervals[i])i++}// 插入新区间if i < n && intervals[i][0] <= newInterval[1] {newInterval[0] = min(intervals[i][0], newInterval[0])newInterval[1] = max(intervals[i][1], newInterval[1])i++}res = append(res, newInterval)// 合并重叠的区间for i < n {if intervals[i][0] <= res[len(res)-1][1] {res[len(res)-1][1] = max(intervals[i][1], res[len(res)-1][1])} else {res = append(res, intervals[i])}i++}return res
}
func min(a, b int) int {if a < b {return a}return b
}
func max(a, b int) int {if a > b {return a}return b
}


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力! 

🌟 收藏,你的青睐是我努力的方向! 

评论,你的意见是我进步的财富!  

 主页:https://hannyang.blog.csdn.net/ 

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

相关文章:

Golang每日一练(leetDay0019)

目录 55. 跳跃游戏 Jump Game &#x1f31f;&#x1f31f; 56. 合并区间 Mmerge Intervals &#x1f31f;&#x1f31f; 57. 插入区间 Insert Interval &#x1f31f;&#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Golang每日一练 专栏 Python每日一练…...

记录一次性能测试遇到的问题

零、压测指标问题 压测指标&#xff0c;一定要需求方定 啊&#xff0c;谁提压测需求&#xff0c;谁来定压测指标。 如果需求方&#xff0c;对压测指标没有概念&#xff0c;研发和测试&#xff0c;可以把历史压测指标、生产数据导出来给需求方看&#xff0c;引导他们来定指标&…...

C++运算符重载基础教程

所谓重载&#xff0c;就是赋予新的含义。函数重载&#xff08;Function Overloading&#xff09;可以让一个函数名有多种功能&#xff0c;在不同情况下进行不同的操作。运算符重载&#xff08;Operator Overloading&#xff09;也是一个道理&#xff0c;同一个运算符可以有不同…...

Git命令总结

全局配置 git config --global user.name ‘你的名字’ git config --global user.email ‘你的邮箱’ 当前仓库配置 git config --local user.name ‘你的名字’ git config --local user.email ‘你的邮箱’ 查看 global 配置 git config --global --list 查看当前仓库…...

【车载以太网】BCM89572A0BCFBG、BCM89559GB0BCFBG、BCM89559GA0BCFBG具有安全启动和安全通信功能

BCM89572A0BCFBG 设备是Broadcom第六代完全集成的L2多层开关解决方案&#xff0c;支持车载网络应用的汽车认证(AEC-Q100)和温度等级。BCM8956X系列产品为汽车行业提高了具有多种一流功能的交换机的标准&#xff0c;例如802.1AE MACsec等集成安全功能&#xff0c;增加了主机连接…...

Lighttpd入门教程

Lighttpd入门教程概述入门教程安装配置静态文件服务动态文件服务虚拟主机SSL启动服务器日志模块总结lighthttpd使用场景和原理使用场景原理概述 Lighttpd&#xff08;也称为轻量级HTTP服务器&#xff09;是一款快速、灵活、轻量级的Web服务器&#xff0c;旨在提供高性能和低资…...

Springboot 多线程分批切割处理 大数据量List集合 ,实用示例

前言 哲学提问镇贴&#xff1a; 不了解异步怎么使用的看官&#xff0c; 可阅&#xff1a; SpringBoot 最简单的使用异步线程案例 Async_小目标青年的博客-CSDN博客 Springboot Async异步扩展使用 结合 CompletableFuture_小目标青年的博客-CSDN博客 想了解更多关于批量list处…...

SQLMAP工具基础使用

本文用的是kali自带的sqlmap工具 我们通过常用命令来理解sqlmap的基本使用 目录 检测注入 获取敏感信息 获取表 获取表的字段 获取数据 --technique 使用指定的注入方式 使用基于时间的延时注入 支持多种注入检测 默认是全部 注入时使用随机的 HTTP User-Agent 设置超时时间 读…...

初学多线程爬虫

多线程在爬虫中应用非常广泛&#xff0c;对于中大型项目来说很有必要&#xff0c;今天我将以初学者的姿态来完成一个简单的多线程爬虫程序。 1、如何认识多线程 计算机完成一项或多项任务&#xff0c;往往可以存在很高的并行度&#xff1a;若是多核处理器则天然的可以同时处理…...

python-实验报告-3

1、编写程序&#xff0c;用户输入一个五位整数&#xff0c;输出其千位和十位数字之和。 num int(input()) # 12345 s1 (num//1000)%10 s2 (num//10)%10sum s1 s2 print(sum)心得&#xff1a; 首先&#xff0c;程序通过 input() 函数获取用户输入的整数&#xff0c;保存在…...

00_托管网站在Tor网络上_Ubuntu主机

title: 托管网站在Tor网络上 urlname: 00_托管网站在Tor网络上_Ubuntu主机 date: 2017-04-24 03:03:03 tags: 小技巧 categories: [小技巧] 托管网站在Tor网络上&#xff08;Ubuntu主机&#xff09;https://www.t00ls.net/thread-44040-1-1.html 大部分人接触Tor网络是由Tor …...

个人练习-Leetcode-659. Split Array into Consecutive Subsequences

题目链接&#xff1a;https://leetcode.cn/problems/split-array-into-consecutive-subsequences/ 题目大意&#xff1a;给出一个非递减数列nums[]&#xff0c;判断其是否能被分割成若干个满足以下条件的子列&#xff1a; 长度大于等于3元素严格递增且只相差1 子列的含义是&…...

OTA升级差分包签名

制作差分包时添加-k <key_path>参数 ./build/tools/releasetools/ota_from_target_files -k <key_path> -i old.zip new.zip update.zip<key_path>如何取值&#xff1f;查看ProjectConfig.mk 如果MTK_SIGNATURE_CUSTOMIZATIONyes并且MTK_INTERNALno&#xf…...

使用Buildroot制作根文件系统

寒暄几句 学习了uboot、内核、busybox根文件系统&#xff0c;想着做一个音频播放器。最后发现好像busybox好像没有带aplay架构&#xff0c;这就很麻烦需要自己移植。为了简便我就找大佬沟通了一下&#xff0c;大佬推荐了Buildroot工具来制作根文件系统。 平台 开发板&#x…...

Java_Spring:5. 基于注解的 IOC 配置

目录 1 环境搭建 1.1 第一步&#xff1a;拷贝必备 jar 包到工程的 lib 目录。 1.2 第二步&#xff1a;使用Component 注解配置管理的资源 1.3 第三步&#xff1a;创建 spring 的 xml 配置文件并开启对注解的支持 2 常用注解 2.1 用于创建对象的注解 2.1.1 Component 2.1…...

Git下的.gitignore文件

.gitignore .gitignore是一个文件&#xff0c;这个文件用来指定哪些文件提交到 git 管理&#xff0c;也就是 git commit 不会提交这些文件 .gitignore文件的语法 注释 "#" 表示注释 # 注释 忽略指定文件/文件夹 直接写入文件或文件夹名即可&#xff0c;指定文…...

Unity集成GPT

GPT想必是最近互联网最火的话题了&#xff0c;作为一个Unity开发者&#xff0c;今天来介绍一下如何在Unity中使用GPT。 一、API 密钥 使用GPT的API首先要获得密钥&#xff0c;如下进入OpenAI官网(https://platform.openai.com/account/api-keys)–>选择自己的账号–>查…...

Xilinx FPGA Multiboot设计与实现(Spartan-6和Kintex-7为例)

文章目录 1. FPGA固件升级方案2. Golden镜像和Multiboot镜像简介3. ISE环境下实现(XC6SLX9)4. Vivado环境下实现(XC7K325T)5. Golden镜像Header分析6. 参考资料7. 示例工程ISE、Vivado、MicroBlaze系列教程 1. FPGA固件升级方案 FPGA的硬件可编程性给设计带来了很高的灵活…...

14、SpringMVC执行流程

文章目录14、SpringMVC执行流程14.1、SpringMVC常用组件1 DispatcherServlet&#xff08;前端控制器&#xff09;2 HandlerMapping&#xff08;处理器映射器&#xff09;3 Handler&#xff08;处理器&#xff09;4 HandlerAdapter&#xff08;处理器适配器&#xff09;5 ViewRe…...

2步搞定拼版!AD通用拼版技巧分享!

你是不是也看过很多拼版教程&#xff0c;一整篇文章全部都是文字说明和各种图示&#xff0c;照着一步步去做&#xff0c;都需要一些时间才能勉强搞定。 之前我用过AD20的自带拼版工具&#xff0c;功能上比较简单&#xff0c;而且菜单没有全部汉化&#xff0c;对于新手来说&…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...