452.用最少数量的箭引爆气球
题目链接452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
这道题是要求从下往上穿箭，把所有气球扎爆要的最少箭的数量
思路就是我们比较这个气球和上一个气球有没有重合的，重合我们一根箭一起就射了，不重合我们就要单独拿根箭射它，每个气球都有左边界points[i][0]，和右边界points[i][1]，我当前气球左边界都大于上一个气球的右边界，那就一点不挨边，箭加一，如果不是那就肯定挨着了，一根箭就够用（箭就不用加一），但是为了判断后面还有没有气球跟他俩连着，我直接更新气球的右边界来和后面的进行比较，以防我后面的气球万一也可以跟这俩一起射爆。
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;int result = 1;sort(points.begin(), points.end(), cmp);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], points[i - 1][1]);//更新右边界和后面进行比较}}return result;}
};435.无重叠区间
题目链接：435. 无重叠区间 - 力扣（LeetCode）
这道题感觉跟上一道题很相像，因为这道题是要去掉重叠区间，让剩下的区间都不重叠，思路就是我们进行先按左区间从小到大进行遍历，如果遍历到重叠的区间我们就要去掉一个重叠区间，所以定义的count++，为了判断后面还有没有区间跟他俩重合，我直接更新区间的右边界来和后面的进行比较。如果遍历到不重叠的区间，就啥也不用做，写代码只重合的区间就行。
class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];//按左区间从小到大进行排序}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0)return 0;int count = 0;sort(intervals.begin(), intervals.end(), cmp);for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < intervals[i - 1][1]) {//如果重叠count++;intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);//更新右区间}}return count;}
};763.划分字母区间
题目链接：763. 划分字母区间 - 力扣（LeetCode）
这道题问的是怎么把同一字母分到一个片段
思路是要分两步走：1、 就是要先定义一个数组里面存放着每个字母的最远边界，2、然后我遍历这个字符串，遍历到哪个字母我就去找相应字母的最远边界，如果我们遍历到了现存的最远边界了那就收集结果，继续遍历。
class Solution {
public:vector<int> partitionLabels(string s) {int hash[27] = {0};for (int i = 0; i < s.size(); i++) {hash[s[i] - 'a'] = i;//每个字符出现的最后位置}vector<int> result;int right = 0;int left = 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 = right + 1;//继续遍历}}return result;}
};最开始就一直不明白hash数组是怎么存放最远边界的，我觉得字母不一样的话hash数组不是东一个西一个的吗，然后手动遍历了大概懂了。
假设有字符串S = "abacabad"
-
当 i = 0, S[0] = 'a':
hash['a' - 'a'] = hash[0] = 0- 更新后的
hash:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-
当 i = 1, S[1] = 'b':
hash['b' - 'a'] = hash[1] = 1- 更新后的
hash:[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-
当 i = 2, S[2] = 'a':
hash['a' - 'a'] = hash[0] = 2- 更新后的
hash:[2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-
当 i = 3, S[3] = 'c':
hash['c' - 'a'] = hash[2] = 3- 更新后的
hash:[2, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-
当 i = 4, S[4] = 'a':
hash['a' - 'a'] = hash[0] = 4- 更新后的
hash:[4, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-
当 i = 5, S[5] = 'b':
hash['b' - 'a'] = hash[1] = 5- 更新后的
hash:[4, 5, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-
当 i = 6, S[6] = 'a':
hash['a' - 'a'] = hash[0] = 6- 更新后的
hash:[6, 5, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
-
当 i = 7, S[7] = 'd':
hash['d' - 'a'] = hash[3] = 7- 更新后的
hash:[6, 5, 3, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
这里的hash数组存的是26个英文字母所对应的最远边界，是按字母顺序进行排列的，然后遇到同样的字母会把该字母相同位置的hash数组进行更新所以不会东一个西一个hhh。