当前位置:网站首页>LeetCode刷题day49
LeetCode刷题day49
2022-07-07 15:35:00 【51CTO】
今日刷题重点—贪心
文章目录
- 55. 跳跃游戏
55. 跳跃游戏
题目描述
给定一个非负整数数组 nums
,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1:
示例 2:
思路分析
刚看到本题一开始可能想:当前位置元素如果是3,我究竟是跳一步呢,还是两步呢,还是三步呢,究竟跳几步才是最优呢?
其实跳几步无所谓,关键在于可跳的覆盖范围!
这个范围内,别管是怎么跳的,反正一定可以跳过来。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点!
每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围。
贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点。
局部最优推出全局最优,找不出反例,试试贪心!
如图:
i每次移动只能在cover的范围内移动,每移动一个元素,cover得到该元素新的覆盖范围的补充,让i继续移动下去。
而cover每次只取 max(该元素数值补充后的范围, cover本身范围)
。
如果cover大于等于了终点下标,直接return true就可以了。
参考代码
45. 跳跃游戏 II
题目描述
给你一个非负整数数组 nums
,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例 1:
示例 2:
思路分析
本题要计算最小步数,那么就要想清楚什么时候步数才一定要加一呢?
贪心的思路,局部最优:当前可移动距离尽可能多走,如果还没到终点,步数再加一。整体最优:一步尽可能多走,从而达到最小步数。
思路虽然是这样,但在写代码的时候还不能真的就能跳多远跳远,那样就不知道下一步最远能跳到哪里了。
所以真正解题的时候,要从覆盖范围出发,不管怎么跳,覆盖范围内一定是可以跳到的,以最小的步数增加覆盖范围.覆盖范围一旦覆盖了终点,得到的就是最小步数!
这里需要统计两个覆盖范围,当前这一步的最大覆盖和下一步最大覆盖。
如果移动下标达到了当前这一步的最大覆盖最远距离了,还没有到终点的话,那么就必须再走一步来增加覆盖范围,直到覆盖范围覆盖了终点。
如图:
参考代码
1005. K 次取反后最大化的数组和
题目描述
给你一个整数数组 nums
和一个整数 k
,按以下方法修改该数组:
- 选择某个下标
i
并将nums[i]
替换为-nums[i]
。
重复这个过程恰好 k
次。可以多次选择同一个下标 i
。
以这种方式修改数组后,返回数组 可能的最大和 。
示例 1:
示例 2:
示例 3:
思路分析
贪心的思路,局部最优:让绝对值大的负数变为正数,当前数值达到最大,整体最优:整个数组和达到最大。
那么如果将负数都转变为正数了,K依然大于0,此时的问题是一个有序正整数序列,如何转变K次正负,让 数组和 达到最大。
那么又是一个贪心:局部最优:只找数值最小的正整数进行反转,当前数值可以达到最大(例如正整数数组{5, 3, 1},反转1 得到-1 比 反转5得到的-5 大多了),全局最优:整个 数组和 达到最大。
那么本题的解题步骤为:
- 第一步:将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小
- 第二步:从前向后遍历,遇到负数将其变为正数,同时K–
- 第三步:如果K还大于0,那么反复转变数值最小的元素,将K用完
- 第四步:求和
参考代码
如果有收获!!! 希望老铁们来个三连,点赞、收藏、转发。
创作不易,别忘点个赞,可以让更多的人看到这篇文章,顺便鼓励我写出更好的博客
边栏推荐
猜你喜欢
Sort out several important Android knowledge and advanced Android development interview questions
面向接口编程
[image sensor] correlated double sampling CDs
[Seaborn] combination chart: facetgrid, jointgrid, pairgrid
字节跳动高工面试,轻松入门flutter
Talk about the realization of authority control and transaction record function of SAP system
Vs2019 configuration matrix library eigen
【视频/音频数据处理】上海道宁为您带来Elecard下载、试用、教程
Binary search tree (basic operation)
最新Android高级面试题汇总,Android面试题及答案
随机推荐
整理几个重要的Android知识,高级Android开发面试题
[designmode] facade patterns
Skimage learning (3) -- adapt the gray filter to RGB images, separate colors by immunohistochemical staining, and filter the maximum value of the region
一文读懂数仓中的pg_stat
node:504报错
LeetCode-SQL第一天
预售17.9万,恒驰5能不能火?产品力在线,就看怎么卖
LeetCode 1696. Jumping game VI daily question
AI来搞财富分配比人更公平?来自DeepMind的多人博弈游戏研究
typescript ts 基础知识之类型声明
ORACLE进阶(六)ORACLE expdp/impdp详解
skimage学习(1)
Inner monologue of accidental promotion
DAPP defi NFT LP single and dual currency liquidity mining system development details and source code
Master this promotion path and share interview materials
LeetCode 120. 三角形最小路径和 每日一题
LeetCode 120. Triangle minimum path and daily question
LeetCode 152. 乘积最大子数组 每日一题
LeetCode 1774. The dessert cost closest to the target price is one question per day
Skimage learning (2) -- RGB to grayscale, RGB to HSV, histogram matching