452. 用最少数量的箭引爆气球
题目描述
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4
示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2
示例 4：
输入：points = [[1,2]] 输出：1
示例 5：
输入：points = [[2,3],[2,3]] 输出：1
思路分析
如何使用最少的弓箭呢？
直觉上来看，貌似只射重叠最多的气球，用的弓箭一定最少，那么有没有当前重叠了三个气球，我射两个，留下一个和后面的一起射这样弓箭用的更少的情况呢？
尝试一下举反例，发现没有这种情况。
那么就试一试贪心吧！**局部最优：**当气球出现重叠，一起射，所用弓箭最少。**全局最优：**把所有气球射爆所用弓箭最少。
算法确定下来了，那么如何模拟气球射爆的过程呢？是在数组中移除元素还是做标记呢？
如果真实的模拟射气球的过程，应该射一个，气球数组就remove 一个元素，这样最直观，毕竟气球被射了。
但仔细思考一下就发现：如果把气球排序之后，从前到后遍历气球，被射过的气球仅仅跳过就行了，没有必要让气球数组remove气球，只要记录一下箭的数量就可以了。
以上为思考过程，现在已经确定下来使用贪心了，那么开始解题。
为了让气球尽可能的重叠，需要对数组进行排序。
那么按照气球起始位置排序，还是按照气球终止位置排序呢？
其实都可以！只不过对应的遍历顺序不同，我就按照气球的起始位置排序了。
既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重叠。
从前向后遍历遇到重叠的气球了怎么办？
例如当前气球B和上一个气球A发生了重叠,那么就满足B[0]<=A[1] ,同时重叠区域右边界就更新为 min(A[1],B[1]) .如果当前气球B的左边界B[0] > 重叠区域的右边界,则说明从当前气球开始,需要一支新的弓箭了.
以题目示例： [[10,16],[2,8],[1,6],[7,12]]为例，如图：（方便起见，已经排序）
参考代码
#include<bits/stdc++.h> using namespace std; static bool cmp(const vector<int>& a,const vector<int>& b){ return a[0]<b[0]; } int findMinArrowShots(vector<vector<int>>& points) { if(points.size()==0){ return 0; } sort(points.begin(),points.end(),cmp); int result = 1;//气球个数 > 0,至少需要一支箭 for(int i = 1; i < points.size(); i++) { if(points[i][0] > points[i-1][1]){//如果右边气球的 左边界 > 左边气球(重叠区域)的右边界,则 箭++ result++; }else{//左右两个气球重叠 ,更新当前气球的右边界为重叠区域的右边界.这样当下一个气球的左边界 < 重叠区右边界,则下一个气球也可以用当前箭...否则下一个气球将使用另外一支箭 points[i][1] = min(points[i-1][1],points[i][1]); } } return result; }
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，5，6都按照右边界排好序。
每次取非交叉区间的时候，都是右边界最小的来做分割点（这样留给下一个区间的空间就越大），所以第一条分割线就是区间1结束的位置。
接下来就是找大于区间1结束位置的区间，是从区间4开始。那有同学问了为什么不从区间5开始？别忘已经是按照右边界排序的了。
区间4结束之后，在找到区间6，所以一共记录非交叉区间的个数是三个。
总共区间个数为6，减去非交叉区间的个数3。移除区间的最小数量就是3。
参考代码
#include<bits/stdc++.h> using namespace std; static bool cmp(vector<int>& a,vector<int>& b){ return a[1]<b[1]; } int eraseOverlapIntervals(vector<vector<int>>& intervals) { if(intervals.size()==0){ return 0; } sort(intervals.begin(),intervals.end(),cmp); int count = 1;//记录非交叉区间个数 int end = intervals[0][1];//第一个区间的右边界为初始分割点 for(int i = 1; i < intervals.size();i++){ if(end <= intervals[i][0]){//如果区间的左边界> 分割点,则该区间是新的非交叉区间 count++;//数量++ end = intervals[i][1];//更新分割点 } } return intervals.size() - count; //移除区间的数量 }
763. 划分字母区间
题目描述
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
思路分析
题目要求同一字母最多出现在一个片段中，那么如何把同一个字母的都圈在同一个区间里呢？
如果没有接触过这种题目的话，还挺有难度的。
在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
可以分为如下两步：
统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
如图：
参考代码
#include<bits/stdc++.h> using namespace std; vector<int> partitionLabels(string s) { vector<int> res; int hash[27] = {0};//用于标记元素出现的最大下标. for(int i = 0; i < s.size(); i++){//65 26 91 98 hash[ch-97+1] = i; } int left = 0;//区间起始位置 int right = 0;//区间结束位置 for(int i = 0; i < s.size(); i++){ right = max(right,hash[s[i]-97+1]);//第一次一定会走max函数的.. if(right==i){//如果right=i,则说明该片段里面的字母最远位置就是此处.当前已经走到了片段的最终位置,下一个要开始新的片段了. res.push_back(right-left+1); left = i + 1;//更新下一个开始的起始位置. right下一轮max会自动进行更新.... } } return res; }
56. 合并区间
题目描述
以数组 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] 可被视为重叠区间。
思路分析
此题一定要排序，那么按照左边界排序，还是右边界排序呢？
都可以！
那么我按照左边界排序，排序之后**局部最优：**每次合并都取最大的右边界，这样就可以合并更多的区间了，**整体最优：**合并所有重叠的区间。
局部最优可以推出全局最优，找不出反例，试试贪心。
那有同学问了，本来不就应该合并最大右边界么，这和贪心有啥关系？
有时候贪心就是常识！哈哈
按照左边界从小到大排序之后，如果 intervals[i][0] < intervals[i - 1][1] 即intervals[i]左边界 < intervals[i - 1]右边界，则一定有重复，因为intervals[i]的左边界一定是大于等于intervals[i - 1]的左边界。
这么说有点抽象，看图：（注意图中区间都是按照左边界排序之后了）
知道如何判断重复之后，剩下的就是合并了，如何去模拟合并区间呢？
其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
参考代码
#include<bits/stdc++.h> using namespace std; static bool cmp(vector<int>& a,vector<int>& b){ return a[0]<b[0]; } vector<vector<int>> merge(vector<vector<int>>& intervals) { vector<vector<int>> res; if(intervals.size()==0){ return res; } bool flag = false;//标记最后一个是否被处理 (因为只有个数>=2才可能发生区间合并...) int len = intervals.size(); sort(intervals.begin(),intervals.end(),cmp) ; for(int i = 1;i < len; i++) { int start = intervals[i-1][0];//区间左边界 int end = intervals[i-1][1];//区间右边界 while(i<len && intervals[i][0] <= end) { end = max(end,intervals[i][1]);//更新合并区间的右边界 if(i==len - 1){//最后一个区间已经被处理了. flag = true; } i++; } res.push_back({start,end}) ; } if(!flag){//如果最后一个区间未被处理,将其添加到结果集.. res.push_back({intervals[len-1][0],intervals[len-1][1]}); } return res; }
738. 单调递增的数字
题目描述
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 10 输出: 9
示例 2:
输入: n = 1234 输出: 1234
示例 3:
输入: n = 332 输出: 299
思路分析
题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。
例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]–，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
这一点如果想清楚了，这道题就好办了。
局部最优： 遇到strNum[i - 1] > strNum[i] 的情况，让strNum[i - 1]-- ，然后strNum[i]=9 ，可以保证这两位变成最大单调递增整数。
全局最优： 得到小于等于N的最大单调递增的整数。
但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9。
此时是从前向后遍历还是从后向前遍历呢？
从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。
这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
所以从前向后遍历会改变已经遍历过的结果！
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299
确定了遍历顺序之后，那么此时局部最优就可以推出全局，找不出反例，试试贪心。
参考代码
#include<bits/stdc++.h> using namespace std; int monotoneIncreasingDigits(int n) { string str = to_string(n); int flag = str.size(); for(int i = str.size()-1;i > 0;i--){ if(str[i-1] > str[i]){//寻找前一位大于当前位的情况并进行记录. 由于是找小于当前数的最大递增数,所以str[i-1]--; str[i-1]--; flag = i; } } for(int i = flag; i < str.size();i++){//把标记后面的位数都变成最大数9 str[i] = '9'; } return stoi(str); }
714. 买卖股票的最佳时机含手续费
题目描述
给定一个整数数组prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意： 这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3 输出：6
思路分析
在贪心算法：122.买卖股票的最佳时机II 中使用贪心策略不用关心具体什么时候买卖，只要收集每天的正利润，最后稳稳的就是最大利润了。
而本题有了手续费，就要关系什么时候买卖了，因为计算所获得利润，需要考虑买卖利润可能不足以手续费的情况。
如果使用贪心策略，就是最低值买，最高值（如果算上手续费还盈利）就卖。
此时无非就是要找到两个点，买入日期，和卖出日期。
买入日期：其实很好想，遇到更低点就记录一下。
卖出日期：这个就不好算了，但也没有必要算出准确的卖出日期，只要当前价格大于（最低价格+手续费），就可以收获利润，至于准确的卖出日期，就是连续收获利润区间里的最后一天（并不需要计算是具体哪一天）。
所以我们在做收获利润操作的时候其实有三种情况：
情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
情况三：不作操作，保持原有状态（买入，卖出，不买不卖）
就那一行关键代码 minPrice = prices[i]-fee，太难理解了。举个例子profits=[1,3,7,5,10,3] fee=3帮助理解。手续费是3，在价格为1的时候买入股票，当价格为7 的时候，7-1（本金）-3（手续费）=3，这时候有利可得先记着，profit = 3。7卖出的时候，减去手续费，股票价格相当于是4。到了后面股票价格为10 的时候，减去手续费价格相当于是7。也就是说如果在10 的时候售出股票，比在7的时候售出股票还要多赚（7-4） = 3，所以profit = 6了。最后价格为3的时候，3<7，什么都不做。题目中的变量命名还有待商榷。
参考代码
#include<bits/stdc++.h> using namespace std; int maxProfit(vector<int>& prices, int fee) { int result = 0;//最后的受益 int minPrice = prices[0];//之前购买的最小价格 for(int i = 0;i < prices.size();i++){ //如果股票价格比最低价格还低,则更新minPrice if(prices[i] < minPrice){ minPrice = prices[i]; } if(prices[i] >= minPrice && prices[i]<= minPrice+fee) {//股票价格比之前最低的价格高,但是不足以支付交易费用 continue; } if(prices[i]>minPrice+fee) {//股票价格比之前最低的价格高,并且可以赚到钱... result += prices[i] - minPrice-fee; minPrice = prices[i]-fee;//表示如果获利,我先持有该股票,并不销售. } } return result; }
