直缝钢管网站建设,百度官网下载安装免费,医疗网页设计,上海谷歌seo推广公司前言
思路及算法思维#xff0c;指路 代码随想录。 题目来自 LeetCode。
day 36#xff0c;周三#xff0c;最难坚持的一天~
题目详情
[452] 用最少数量的箭引爆气球
题目描述
452 用最少数量的箭引爆气球
解题思路
前提#xff1a;区间可能重叠 思路#xff1a;…前言
思路及算法思维指路 代码随想录。 题目来自 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;
}今日收获
贪心算法不太能想到的思路。
