452.用最少数量的箭引爆气球
题目链接：452.用最少数量的箭引爆气球
文档讲解：代码随想录
状态：小小思考AC
思路
贪心规则：所有能重叠的全部叠在一起
如何判断重叠？排序，起始点依次递增，判断起点与前一个终点位置即可。
如果不重叠（包括不于前面重叠的重叠），都要再增加一次射击次数。
题解
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
int res = 1;
sort(points.begin(),points.end());
//后续可优化，通过points[i-1]与points[i]判断即可
int start = points[0][0], end = points[0][1];
for(int i = 1;i<points.size();i++)
{
if(points[i][0]>end)
{
res++;
start = points[i][0];
end = points[i][1];
}
else
{
start = points[i][0];
//注意此处min的思辨，取交集才有用，不然必须多射箭
end = min(end,points[i][1]);
}
}
return res;
}
};
435.无重叠区间
思路
与上题类似，同属于重叠区间问题，同样是排序+判断重叠的套路。
注意min(intervals[i-1][1],intervals[i][1])的思考，对于重叠，要去除一个范围大的才可以，因为i的起点一定大于i-1的起点，比的是i的起点与i-1的终点（越小越好，很贪心）。
题解
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int res = 0;
sort(intervals.begin(),intervals.end());
for(int i = 1;i<intervals.size();i++)
{
if(intervals[i][0]<intervals[i-1][1])
{
res++;
intervals[i][1] = min(intervals[i-1][1],intervals[i][1]);
}
}
return res;
}
};
763.划分字母区间
题目链接：763.划分字母区间
文档讲解：代码随想录
状态：看了思路AC
思路
思路：要找到字符第一次出现与最后一次出现的地方，并且包含在范围内的所有字符不可在范围外出现；否则呢？否则要扩大范围！
如何找到每个字母最后一次出现的地方？很简单很简单，大概率很常用，使用哈希表（数组与map皆可）.
在解题中知道了末尾不知道起点，是我太死板，加一个start变量记录不就得了。
题解
class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> res;
int hash[26] = {0};
for(int i = 0;i<s.size();i++)hash[s[i]-'a'] = i;
int last = hash[s[0]-'a'],start = 0;
for(int i = 0;i<s.size();i++)
{
if(hash[s[i]-'a']>last)last = hash[s[i]-'a'];
if(i == last)
{
res.push_back(last-start+1);
start = last+1;
//因为一直在循环中更新last的值，不需要特地再更新
//if(i+1<s.size())last = hash[s[i+1]-'a'];可被优化
}
}
return res;
}
};