宁波企业网站制作哪家好,网络公司怎么优化网站,威海企业网站建设,软件通网站建设代码随想录算法训练营第6周#xff08;C语言#xff09;|Day36#xff08;贪心#xff09;
Day36、贪心#xff08;包含题目 ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间 #xff09;
435. 无重叠区间
题目描述
给定一个区间的集合#xff0c;找到需要… 代码随想录算法训练营第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(intervalsSize0){return 0;}qsort(intervals,intervalsSize,sizeof(int*),cmp);int res0;int endintervals[0][1];for(int i1;iintervalsSize;i){if(intervals[i][0]end){endintervals[i][1];}else{endendintervals[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 ssizestrlen(s);int hash[26];for(int i0;issize;i){hash[s[i]-a]i;}//每个字母最后出现的位置int right0;int left0;int count0;for(int i0;issize;i){rightrighthash[s[i]-a]?right:hash[s[i]-a];if(righti){res[count]right-left1;leftright1;}}*returnSizecount;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 count0;qsort(intervals,intervalsSize,sizeof(int*),cmp);res[count]intervals[0];for(int i1;iintervalsSize;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;*returnSizecount;*returnColumnSizesmalloc(sizeof(int)*count);for(int i0;icount;i){(*returnColumnSizes)[i]2;}return res;
}题目总结
根扎气球相同更新已经记录的数组区间。
