【代码随想录】【算法训练营】【第36天】[452]用最少数量的箭引爆气球 [435]无重叠区间 [763]划分字母区间

前言

思路及算法思维，指路代码随想录。
题目来自 LeetCode。

day 36，周三，最难坚持的一天~

题目详情

[452] 用最少数量的箭引爆气球

题目描述

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

解题思路

前提：区间可能重叠
思路：贪心算法：按照起始位置排序，一支箭尽可能射多的气球。
重点：判断当前弓箭终止范围。

代码实现

C语言

贪心思维

局部最优：当气球出现重叠，一起射，所用弓箭最少。
全局最优：把所有气球射爆所用弓箭最少。
为了让气球尽可能的重叠，需要对数组进行排序。
如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。

int cmp(const void *p1, const void *p2)
{
    int *pp1 = *(int **)p1;
    int *pp2 = *(int **)p2;
    // 按照起始位置排序, 相同起始位置按终止位置排序
    if (pp1[0] > pp2[0]) {
        return 1;
    }
    else if (pp1[0] == pp2[0]) {
        if (pp1[1] > pp2[1]) {
            return 1;
        }
    }
    return 0;
}

int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){
    // 按照起始位置排序, 相同起始位置按终止位置排序
    qsort(points, pointsSize, sizeof(int *), cmp);
    
    // 至少需要一支箭
    int count = 1;
    int curRange = points[0][1];
    for (int i = 1; i < pointsSize; i++) {
        // 判断是否需要使用下一只弓箭：当前射箭范围是否与当前数组范围有交集
        if (curRange < points[i][0]) {
            count++;
            curRange = points[i][1];
        }
        // 判断当前数组范围是否会缩小当前射箭范围
        if (curRange > points[i][1]) {
            curRange = points[i][1];
        }
    }
    return count;
}

[435] 无重叠区间

题目描述

435 无重叠区间

解题思路

前提：区间可能重叠
思路：贪心算法：按照起始位置排序，判断区间是否重复，去除重复区间时去除更大的区间,留下较小的区间。
重点：判断当前区间终止范围。

代码实现

C语言

起始位置排序，判断重复区间

按照起始位置排序，起始位置相同按照终止位置排序，判断区间是否重复，去除重复区间时去除更大的区间,留下较小的区间

int cmp(const void *p1, const void *p2)
{
    int *pp1 = *(int **)p1;
    int *pp2 = *(int **)p2;
    return pp1[0] == pp2[0] ? pp1[1] - pp2[1] : pp1[0] - pp2[0];
}

int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {
    // 按照起始位置排序，起始位置相同按照终止位置排序
    qsort(intervals, intervalsSize, sizeof(int *), cmp);
    int count = 0;
    int endNum = intervals[0][1];
    // 判断区间是否重复，去除重复区间时去除更大的区间,留下较小的区间
    for (int i = 1; i < intervalsSize; i++) {
        // 判断起始位置与之前终止位置是否重叠
        if (endNum > intervals[i][0]) {
            count++;
        }
        else {
            endNum = intervals[i][1];
        }
        // 更新终止位置
        if (endNum > intervals[i][1]) {
            endNum = intervals[i][1];
        }
    }
    return count;
}

终止位置排序，判断非交叉区间

按照终止位置排序，终止位置相同按照起始位置排序，判断非重复区间的个数，需要移除区间数量即为重复区间个数，即总区间个数 - 非重复区间个数

int cmp(const void *p1, const void *p2)
{
    int *pp1 = *(int **)p1;
    int *pp2 = *(int **)p2;
    return pp1[1] == pp2[1] ? pp1[0] - pp2[0] : pp1[1] - pp2[1];
}

int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {
    // 按照终止位置排序，终止位置相同按照起始位置排序
    qsort(intervals, intervalsSize, sizeof(int *), cmp);
    int count = 1;
    int endNum = intervals[0][1];
    // 判断非重复区间的个数
    for (int i = 1; i < intervalsSize; i++) {
        // 判断起始位置与之前终止位置是否重叠
        if (endNum <= intervals[i][0]) {
            count++;
            endNum = intervals[i][1];
        }
    }
    // 需要移除区间数量即为重复区间个数，即总区间个数 - 非重复区间个数
    return intervalsSize - count;
}

[763] 划分字母区间

题目描述

763 划分字母区间

解题思路

前提：同一字母处于同一子字符串中
思路：要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点。
重点：确定分割点的位置，经过的每个字符串的最远位置。

代码实现

C语言

贪心思维

统计每个字母最后出现的位置；圈字符，找分割点；遍历到当前元素出现的最远位置，即为分割点。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

#define LETTERS_MAX_NUMS  (26)

int* partitionLabels(char* s, int* returnSize) {
    int sLen = strlen(s);
    int range[LETTERS_MAX_NUMS];
    // 统计每个字母最后出现的位置
    for (int i = 0; i < sLen; i++) {
        range[s[i] - 'a'] = i;   
    }
    // 输出初始化
    int *ans = (int *)malloc(sizeof(int) * LETTERS_MAX_NUMS);
    int ansSize = 0;
    // 划分尽可能多的片段, 每个片段尽可能短，但是要包含所有同一字母
    // 圈字符,找分割点
    int left = 0;
    int right = 0;
    for (int i = 0; i < sLen; i++) {
        // 缓存当前元素的最远位置
        if (right < range[s[i] - 'a']) {
            right = range[s[i] - 'a'];
        }
        // 遍历到当前元素出现的最远位置，即为分割点
        if (i == right) {
            ans[ansSize] = i - left + 1;
            ansSize++;
            left = i + 1;
        }
    }
    *returnSize = ansSize;
    return ans;
}