今日总结
用最少数量的箭引爆气球
题目链接：452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
整体思路：
1、统一度量 ：
将所有区间按照左端点进行排序：
用到了二维的sort，在类中需要定义静态成员函数cmp，从小到大排列
2、进行区间合并
（1）如果没有气球，就是0箭
（2）如果有气球，至少1箭
（3）按照排序从小到大遍历，比较当前位置的左端点是否在前边位置的范围内（<=前边位置的最小右端点）
如果在，就不加箭，只更新最小的右端点（前边的最小右与当前的右 比较取最小）
如果不在，就加箭，更新右端点为当前气球的右端点
整体代码：
class Solution {
public:
static bool cmp(const vector<int>&a,vector<int>&b)
{
if(a[0]<b[0])return true;
else return false;
}
int findMinArrowShots(vector<vector<int>>& points) {
//进行排序：按照起始坐标排序：
//在类中，两个维度，使用sort需要自己定义静态比较函数cmp
sort(points.begin(),points.end(),cmp);
//进行比较：
//1、如果没有气球就是0支箭
if(points.size()==0)return 0;
//2、要是有气球至少一支箭
int sum =1;
//定义右边端点位置
int res = points[0][1];
//有气球需要判断后边的箭的起点是不是在前边的范围的之内，在就不需要加箭，更新右边的端点位置为最小
for(int i=1;i<points.size();i++)
{
if(points[i][0]<=res)
{
//不加箭，只更新右端点
res = min(res,points[i][1]);
}
else{//超过了右端点，
//加一支箭
sum ++;
//更新右端点
res = points[i][1];
}
}
return sum;
}
};无重叠区间
题目链接：435. 无重叠区间 - 力扣（LeetCode）
整体思路：
1、统一度量：
将所有的区间按照第一个维度从小到大排列，如果第一个维度相同，按照第二维度小的排在前边(第二维度大的一定是一个舍掉的区间)
2、进行区间遍历，舍弃重叠区间
如果当前区间的左端点在上一个区间的范围内（小于右端点，没有等）说明这两个区间重叠了：所以舍弃数量+1，更新右端点为小的右端点，相当于舍掉了右端点大的区间
如果当前区间的左端点不在上一个区间的范围内，说明没有重叠，舍弃数量不变，更新右端点为当前区间的右端点
整体代码：
class Solution {
public:
//移除最小数量的区间，所以区间所占位置越小越好：
//[1,3],[2,3]这种，舍掉[1,3],因为战空间大， 可能存在[0,2]
//1、对所有区间，按照第一维度进行从小到大排序，第一维度相同，排列第二维度小的在前边（大的一定是舍弃的）
//2、从左到右进行遍历，如果当前的区间的左端点在前一个区间内，说明重叠了，比较两者的右端点，谁的右端点小，要谁，舍弃数量+1
//如果当前区间的左端点不在前一个区间内，说明没有重叠，记录右端点位置便于下一个区间的比较,舍弃数量不变
//定义sort的静态比较函数
static bool cmp(const vector<int>&a,const vector<int>&b)
{
if(a[0]<b[0])//比较第一维度
return true;
else if(a[0]<=b[0])
{
if(a[1]<b[1])return true;
else return false;
}
else return false;
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
//排序
sort(intervals.begin(),intervals.end(),cmp);
//如果没有区间
if(intervals.size()==0)return 0;
//如果有区间
int rm =0;//如果只有一个区间，不需要舍弃
//定义第一个区间的右端点 ，便于后边进行比较
int right_point = intervals[0][1];
//遍历，从第二个区间开始
for(int i=1;i<intervals.size();i++)
{
//判断当前区间的起点是否在上一个区间中,注意如果在在一个点上是不重叠的，所以没有等号
if(intervals[i][0]<right_point)
{
//此时说明当前区间与上一个区间有重叠，需要舍弃加1，同时更新小的右区间，相当于删掉了右端点大的区间
rm ++;
right_point = min(right_point,intervals[i][1]);
}
//如果没有重叠
else
{
//不需要舍弃区间，rm不变化
//更新右端点为当前区间的右端点
right_point = intervals[i][1];
}
}
return rm;
}
};划分字母区间
题目链接：763. 划分字母区间 - 力扣（LeetCode）
整体思路：
unordered_map记录：
1、插入元素可以使用insert、下标操作符[]赋值
（1）insert插入限制：
mmap.insert({1,2})如果键1不存在插入{1，2};但是键 1存在就不会重复插入了
（2）[]插入
mmap[1]=2,如果键1不存在，就插入{1,2}如果键1存在，就更新键1的value为2
2、不能先判断是否到了长度lengthh，再进行没有到达长度时加当前段的长度，因为会出现第一个坐标0时，本身就是一段 ，此时却不能进行额外判断
需要先将当前位置加入之后，再判断当前位置是不是符合写入要求
3、使用unordered_map进行记录每个元素的最远位置，之后通过判断当前元素是不是有更远的位置，更新最远的位置，当到达最远位置时进行记录，并将距离恢复为0
整体代码：
class Solution { public: //最大的困难在于同一个字母必须出现在同一个片段中，这会导致分段一定是唯一解 //所以需要统计每个字母最后出现的位置，只要在这个区间中，没有其他字母最后出现的位置大于这个字母的最后位置，就可以将这个字母的最后位置当作分段点 vector<int> partitionLabels(string s) { //1、统计所有字母的最后出现位置为一个数组,使用unordered_map进行记录i unordered_map <char,int> mmap; for(int i=0;i<s.size();i++) { mmap[s[i]] = i; } //2、遍历所有元素，记录当前区间的最远出现位置，判断在这个位置范围内是否存在更远的位置 int lengthh =0; //记录当前的段的大小 int vec=0; //记录总的分段情况 vector<int>res; if(s.size()==0)return {0}; for(int i=0;i<s.size();i++) { //如果当前没有到达最远的位置，就判断当前需不需要更新最远位置 lengthh = max(mmap[s[i]],lengthh); //同时当前段的大小+1 vec++; //判断当前是否到了最远位置 if(i==lengthh) { //到了最远位置,记录 res.push_back(vec); vec =0;//更新距离为0，进行下一个元素 } } return res; } };