lc-day19

763.划分字⺟区间

思路是找到之前出现的最大下标和，如果当前下标与它相等，就存入答案数组中

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function(s) {
    let ans = [];
    let nums = new Array(26);
    const A = 'a'.charCodeAt(0);
    for(let i = 0; i < s.length; i++){
        nums[s.charCodeAt(i) - A] = i;
    }
    let maxx = -1;
    for(let i = 0, j = 0; i < s.length; i++){
        if(maxx < nums[s.charCodeAt(i) - A]) maxx = nums[s.charCodeAt(i) - A];
        if(i == maxx) {
            ans.push(i - j + 1);
            j = i + 1;
        }
    }
    return ans;
};

合并区间

排序左区间, 然后比较右区间判断是否进行合并, 跟之前的弓箭射气球一题还是有区别的, 后面可以稍微总结一下

我不应该执着于用双指针解题, 研究了一下正确答案发现双指针不能确保第二个慢指针一直指向res的最后一个数组, j是随着i更新, 而不是res末尾

弓箭射气球题要求的是区间数量, 所以可以用右区间排序, 找右区间的交叉点贪心解决, 这题要合并区间就要左右端点同时考虑

class Solution {
public:
    static bool cmp(const vector<int>& a, const 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 intervals;
        sort(intervals.begin(), intervals.end(), cmp);

        res.push_back(intervals[0]);
        for(int i = 1; i < intervals.size(); i++){
            if(res.back()[1] >= intervals[i][0]) {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            }
            else {
                res.push_back(intervals[i]);
            } 
        }
        return res;
    }
};

附上js版本

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    if(intervals.length === 0) return intervals;
    intervals.sort((a, b) => a[0] - b[0]);
    let result = [];
    result.push(intervals[0]);
    for(let i = 1; i < intervals.length; i++){
        if(result[result.length - 1][1] < intervals[i][0]) {
            result.push(intervals[i]);
        }
        else {
            result[result.length - 1][1] = Math.max(
                result[result.length - 1][1], 
                intervals[i][1]);
        }
    }
    return result;
};

用最少数量的箭引爆气球

不断更新最大maxL, 每更新一次, 答案+1, 第一次更新是因为区间最少有一个, 再者这个循环比了n-1次, 最坏情况下我需要n支弓箭才行,所以+ 1

这题贪心在只要有两个以上的气球重叠, 就射爆它, 不用再考虑后面的情况

/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function(points) {
    if(points.length == 0) return 0;
    
    points.sort((a, b) => a[1] - b[1]);
    let cnt = 1;
    let maxL = points[0][1];
    for(let i = 1; i < points.length; i++){
        if(maxL < points[i][0]){
            cnt++;
            maxL = points[i][1];
        }
        
    } 
    return cnt;
};

无重叠区间

和上一题很相似,但是这题用了双指针

这题要考虑最后上一个区间对下一个的交叉情况, 并不断更新两个指针

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    if(intervals.length === 0) return 0;
    intervals.sort((a, b) => a[1] - b[1]);
    let ans = 0 ;
    for(let i = 1, j = 0; i < intervals.length; i++){
        if(intervals[j][1] > intervals[i][0]) ans++;
        else j = i;
    }
    return ans;
};