@ 代码随想录算法训练营第6周（C语言）|Day36（贪心）

@ 代码随想录算法训练营第6周（C语言）|Day36（贪心）

Day36、贪心（包含题目 ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间 ）

435. 无重叠区间

题目描述

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

题目解答

int cmp(const void *p1,const void *p2){int *pp1=*(int**)p1;int*pp2=*(int**)p2;return pp1[0]-pp2[0];
}
int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {if(intervalsSize==0){return 0;}qsort(intervals,intervalsSize,sizeof(int*),cmp);int res=0;int end=intervals[0][1];for(int i=1;i<intervalsSize;i++){if(intervals[i][0]>=end){end=intervals[i][1];}else{end=end<intervals[i][1]?end:intervals[i][1];res++;}}return res;
}

题目总结

排序、重叠就加一并更新区间。

763.划分字母区间

题目描述

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

题目解答

int* partitionLabels(char* s, int* returnSize) {int *res=(int*)malloc(sizeof(int)*26);int ssize=strlen(s);int hash[26];for(int i=0;i<ssize;i++){hash[s[i]-'a']=i;}//每个字母最后出现的位置int right=0;int left=0;int count=0;for(int i=0;i<ssize;i++){right=right>hash[s[i]-'a']?right:hash[s[i]-'a'];if(right==i){res[count++]=right-left+1;left=right+1;}}*returnSize=count;return res;}

题目总结

用哈希表来记录字母最后出现位置，然后一旦遍历过的字母最大值与坐标值相同就是边界。

56. 合并区间

题目描述

给出一个区间的集合，请合并所有重叠的区间。

题目解答

 int cmp(const void *p1,const void *p2){int *pp1=*(int**)p1;int *pp2=*(int**)p2;return pp1[0]-pp2[0];}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {int**res=(int**)malloc(sizeof(int*)*intervalsSize);int count=0;qsort(intervals,intervalsSize,sizeof(int*),cmp);res[count]=intervals[0];for(int i=1;i<intervalsSize;i++){if( res[count][1]>=intervals[i][0]){res[count][1]= res[count][1]>intervals[i][1]? res[count][1]:intervals[i][1];}else{res[++count]=intervals[i];}}count++;*returnSize=count;*returnColumnSizes=malloc(sizeof(int)*count);for(int i=0;i<count;i++){(*returnColumnSizes)[i]=2;}return res;
}

题目总结

根扎气球相同，更新已经记录的数组区间。