贪心
1.贪心是 DP 处理的某些问题中的一个特例方法, 相比 DP, 使用 Greedy 需要满足更多的条件 (贪心选择性质), 但是效率高于 DP
2.一个算法用 BruteForce 可能需要指数级别的时间, 如果用 DP 能消除重叠子问题, 就可以降低到多项式级别时间, 如果满足贪心的性质, 那么可能进一步降低到 O(n)
3.什么是贪心选择性质? 每一步都作出一个局部最优的选择, 最终的结果就是全局最优; 这种性质只适合一部分问题, 很多问题是没有这个性质的; 经典例子: 假设有 100 张不同面额的人民币, 只能最多拿 10 张, 问如何拿使得面额的最大? 显然是每次都拿剩下的钞票里面面额最大的, 最终得到的结果就是最优的
4.贪心需要充分挖掘题目中的条件, 没有固定的模式, 解决贪心算法需要培养一定的直觉和经验
435.无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1: 输入: intervals = [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2: 输入: intervals = [[1,2],[1,2],[1,2]] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3: 输入: intervals = [[1,2],[2,3]] 输出: 0 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
分析:
1.题目问的是移除区间的最小的数量, 反着来看, 其实就是找最大的无重叠区间数量是多少? 然后用区间数-最大的无重叠区间数, 就可以得到移除区间的最小数量, 所以问题转化成了如何找到最大的无重叠区间数?
2.找最大的无重叠区间数需要以某种贪心的思想找, 怎样贪心的的策略呢? 假设我们按照对区间起点进行贪心, 但有可能区间的跨度非常长, 因此这种贪心无法得到最大的无重叠区间; 假设我们按照区间长度最短进行贪心, 但可能重叠的是很多的
3.这里贪心的思路建立在: 以 [结束时间最早] 进行贪心搜索最大无重叠区间数量, 这样可以保证每次在所有结束时间之前的无重叠区间数一定是最多的
4.因此本题目贪心思路如下: 按照结束时间排序, 从区间每次选择结束最早的一个区间记为 x, 然后把与x区间有重叠的区间通通从区间集合删除, 将 x 加入到已选区间集合; 继续执行该过程, 直到区间集合为空, 已选区间集合为最大无重叠区间的集合
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int n = intervals.size();
if (n <= 0) {
return 0;
}
sort(intervals.begin(), intervals.end(), cmp);
int curEnd = intervals[0][1];
int cnt = 1;
for (int i = 1; i < n; ++i) {
if (intervals[i][0] >= curEnd) {
++cnt;
curEnd = intervals[i][1];
}
}
return n - cnt;
}
};
452.用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。给你一个数组 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.理解题意: 需要求最小射箭数, 怎么才能最小? (也就是说贪心策略是什么) 一种思路就是区间只关心非射不可的箭数逐个累加起来, 那么就是最小的箭数
2.先对区间按照区间末尾进行排序, 我们让每次射箭都射在区间的末尾, 然后判断如果[下一个区间]的开头和当前的末尾存在重合的, 那么就不需要再多射一支箭, 直接找下一个末尾也就是下一个区间的末尾; 如果[下一个区间]和当前区间是不重合的, 那么就必须在多射出一支箭
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
int n = points.size();
if (n <= 0) {
return 0;
}
sort(points.begin(), points.end(), [](const auto &a, const auto& b){
return a[1] < b[1];
});
int ans = 1;
int shootPos = points[0][1];
for (int i = 1; i < n; ++i) {
if (points[i][0] > shootPos) {
++ans;
shootPos = points[i][1];
}
}
return ans;
}
};
55.跳跃游戏
给定一个非负整数数组 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.对每个可到达的位置 i, 都能延伸到 i + nums[i] 位置
2.实时维护一个最远可到达的位置, 遍历数组, 对于位置 i 如果在现有最远可到达的范围内, 那么我们就能把最远的位置扩展到更远的 x + nums[i] 位置; 最终能否到达最后一个下标, 就是看最终最远可到达的位置有没有 >= len - 1
class Solution {
public:
bool canJump(vector<int>& nums) {
int len = nums.size();
int farthestPos = 0; // 维护当前可达的最右位置
for (int i = 0; i < len; ++i) {
// 如果当前元素是在可到达范围内, 尝试扩展最右位置
if (i <= farthestPos) {
farthestPos = max(farthestPos, i + nums[i]) ;
if (farthestPos >= len - 1) {
return true;
}
}
}
return false;
}
};
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.要求最小的跳跃步数, 从贪心的思路上看, 我们每次在可跳范围内选择可以使得跳的更远的位置, 拿case分析一下
数组 [2,3,1,2,4,2,3]
idx [0,1,2,3,4,5,6]
我们在 0 , 可以跳的范围: [3,1] 3 可以跳到更远, 在里面选择可以跳的最远的位置 3, 更新下一次可跳的范围;
我们在 2 , 可以跳的范围: [1,2,4] 4 可以跳到更远, 在里面选择可以跳的最远的位置 4, 更新下一次可跳的范围;
我们在 4 , 可以跳的范围: [5,6] 6 可以跳到更远, 在里面选择可以跳的最远的位置 6, 更新下一次可跳的范围;
我们需要维护一个当前可跳跃范围的 curEnd 右边界, 在边界内我们都没真实在跳, 只是遍历元素并更新 farthestPos, 直到走到了这个边界, 我们在边界上选取最大的下一个边界 = farthestPos;
遍历的结果为
farPos=0, targetPos=0, steps=0
i=0, farPos=2, targetPos=2, steps=1
i=1, farPos=4, targetPos=2, steps=1
i=2, farPos=4, targetPos=4, steps=2
i=3, farPos=5, targetPos=4, steps=2
i=4, farPos=8, targetPos=8, steps=3
i=5, farPos=8, targetPos=8, steps=3
class Solution {
public:
int jump(vector<int>& nums) {
int farthestPos = 0;
int curEnd = 0; // 维护当前可跳跃范围的右边界
int steps = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
// 遍历位置 i, 迭代能跳到最远的位置
farthestPos = max(farthestPos, i + nums[i]);
// 如果 i 走到当前可跳跃范围的边界
// (i). 更新下一次边界为已探测到能跳的最远的位置
// (ii). 累计最小跳跃次数, step += 1
if (i == curEnd) {
// 每次跳跃边界按照最最远的来跳
curEnd = farthestPos;
++steps;
}
}
return steps;
}
};
630.课程表II
这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
返回你最多可以修读的课程数目。示例 1：输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] 输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。示例 2：
输入：courses = [[1,2]] 输出：1示例 3：输入：courses = [[3,2],[4,3]] 输出：0
class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
}
};
转载请注明来源, from goldandrabbit.github.io
