【代码随想录】【算法训练营】【第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;
}

今日收获

1. 贪心算法：不太能想到的思路。