leetcode算法刷题的第二十六天

今天主要是要用贪心算法来解决重置区间的问题。

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

题目链接

class Solution {
public: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);//这里不加cmp函数也可以int result=1;//points不为空至少需要一支箭for(int i=1;i<points.size();i++){if(points[i][0]>points[i-1][1]){//气球i和气球i-1不挨着,所以注意这里不是>=result++;//需要再加上一支箭}else{//气球i和气球i-1挨着points[i][1]=min(points[i][1],points[i-1][1]);//更新重置气球的最小右边界}}return result;}
};

温馨提示:

注意题目中说的是：满足 xstart ≤ x ≤ xend，则该气球会被引爆。那么说明两个气球挨在一起不重叠也可以一起射爆，

所以代码中 if (points[i][0] > points[i - 1][1]) 不能是>=

思路总结:

局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。

这道题目贪心的思路很简单也很直接，就是重复的一起射了，但本题我认为是有难度的。

就算思路都想好了，模拟射气球的过程，很多同学真的要去模拟了，实时把气球从数组中移走，这么写的话就复杂了。

而且寻找重复的气球，寻找重叠气球最小右边界，其实都有代码技巧。

贪心题目有时候就是这样，看起来很简单，思路很直接，但是一写代码就感觉贼复杂无从下手。

这里其实是需要代码功底的，那代码功底怎么练？

多看多写多总结！

2.leetcode 435.无重叠区间

题目链接

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) {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]){end=intervals[i][1];count++;}}return intervals.size()-count;//记录有多少符合条件的,再用总长度减去符合条件的就是需要去除的}
};

思路总结:

相信很多同学看到这道题目都冥冥之中感觉要排序，但是究竟是按照右边界排序，还是按照左边界排序呢？

其实都可以。主要就是为了让区间尽可能的重叠。

我来按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

此时问题就是要求非交叉区间的最大个数。

大家此时会发现如此复杂的一个问题，代码实现却这么简单！

3.leetcode 763.划分字母区间

题目链接

class Solution {
public:vector<int> partitionLabels(string s) {int hash[27]={0};// i为字符，hash[i]为字符出现的最后位置for(int i=0;i<s.size();i++){// 统计每一个字符最后出现的位置hash[s[i]-'a']=i;}vector<int> result;int left=0;int right=0;for(int i=0;i<s.size();i++){right=max(right,hash[s[i]-'a']);// 找到字符出现的最远边界if(i==right){result.push_back(right-left+1);left=i+1;}}return result;}
};

思路总结:

一想到分割字符串就想到了回溯，但本题其实不用回溯去暴力搜索。

题目要求同一字母最多出现在一个片段中，那么如何把同一个字母的都圈在同一个区间里呢？

如果没有接触过这种题目的话，还挺有难度的。

在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

可以分为如下两步：

统计每一个字符最后出现的位置

从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

这道题目leetcode标记为贪心算法，说实话，我没有感受到贪心，找不出局部最优推出全局最优的过程。就是用最远出现距离模拟了圈字符的行为。

但这道题目的思路是很巧妙的，所以有必要介绍给大家做一做，感受一下。