LeetCode刷题day19—

LeetCode刷题day19——贪心

- 55. 跳跃游戏
- - 分析：
- 45. 跳跃游戏Ⅱ
- - 分析：
- 452. 用最少数量的箭引爆气球
- - 分析：
  - - - **总结**

55. 跳跃游戏

给你一个非负整数数组 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 ， 所以永远不可能到达最后一个下标。

提示：

1 <= nums.length <= 104
0 <= nums[i] <= 105

分析：

怎么跳不重要，我站在i这里，nums[i]=3,其实我跳1，2，3都不重要，重要的是我究竟能覆盖多远的范围。想明白了这个，就不难了，秒掉。

class Solution {
public:bool canJump(vector<int>& nums) {int Max = 0;int i = 0;int len = nums.size();while (i != len) {if (i <= Max) {//我正处于覆盖的范围里Max = max(Max, nums[i] + i);//范围取大i++;} else//不能走，失败break;}if (Max >= len - 1)//下标大于等于最后一个位置return true;elsereturn false;}
};

45. 跳跃游戏Ⅱ

给定一个长度为 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 curReach_Max = 0;int nextReach_Max = 0;int next = 0;//下一步跳到哪里int i = 0;int jump = 1;int len = nums.size();if (1 == len )//输入nums=[0]，i==len-1其实起点就是终点了return 0;while (i < len) {curReach_Max = nums[i] + i;//现在能覆盖的范围if(curReach_Max>=len-1)//如果直接能到，就successreturn jump;for (int j = i + 1; j <= curReach_Max&&j<len; j++) {//在现在能覆盖的范围中，查找下一步可能到达的最大范围，记录下标；也就是下一步要跳到的地方if (nums[j] + j > nextReach_Max) {nextReach_Max = nums[j] + j;next = j;}}//明确下一步跳到哪里了jump++;i = next;//do jump}return  jump;}
};

452. 用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end，且满足 xstart ≤ x ≤ x``end，则该气球会被引爆。可以射出的弓箭的数量 没有限制 。弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示:

1 <= points.length <= 105
points[i].length == 2
-231 <= xstart < xend <= 231 - 1

分析：

我写出来了，是的！值得庆祝。

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {//先对数组按x0排序，找重叠区间，其中的右边界最小值必须得放一支箭sort(points.begin(), points.end(),[](vector<int>& a, vector<int>& b) { return a[0] < b[0]; });vector<bool> visited(points.size(), false);//记录是否已经被处理int line = INT_MAX;int count = 0;//放箭数for (int i = 0; i < points.size(); i++) {if (visited[i])//被处理就跳过continue;if (i > 0 && !visited[i - 1])//不是第一个，并且前一个没被处理，加入最小右边界的比较line = min(points[i][1], line);else//都被处理光了，新开一条线line = points[i][1];int j = i;while (j < points.size() && points[j][0] <= line) {//重叠区间出现了，坚持不懈寻找最小右边界line = min(points[j][1], line);visited[j] = true;j++;}count++;}return count;}
};

但是gpt说给我优化，优化得关键部位只剩四行代码了！那我辛辛苦苦写这么多，我算什么啊，呜呜~

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b) {return a[1] < b[1];  // 按右边界排序});int count = 0;long long arrow = (long long)INT_MIN - 1; // 使用更小的初始值避免冲突for (const auto& point : points) {if (point[0] > arrow) {  // 当前区间起点在箭的范围之外，需要新箭arrow = point[1];count++;}}return count;}
};

而且，按照右边界排序更好，按右边界排序的优点