每周一道算法题(四十四)
2018-02-04 本文已影响34人
CrazySteven
本周题目难度级别'Hard',使用语言C。话说一般都不做Hard题目的，但经过上周的题目，这周的题目难度级别实际上就是'Easy'
题目：给你一个集合，集合的每一个元素是一个区间，这个集合已经排序好，没有重复的(就是上周返回的集合)，然后给你一个新的区间，要求将这个区间插入到这个集合内，返回新的集合(去掉重复的部分)。eg：给你一个集合[1,3],[6,9]，新的区间[2,5]，插入后的集合是：[1,5],[6,9]
思路：这还需要思路么？初始化一个容器，将新的区间放到排序好的集合后面，打包放入新容器，不就成了上周一模一样的题目了？而且只需要考虑最后一个区间就行，更简单了有木有，看代码：
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* };
*/
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
struct Interval* insert(struct Interval* intervals, int intervalsSize, struct Interval newInterval, int* returnSize) {
//初始化新容器
struct Interval* temp = malloc(sizeof(intervals) * (intervalsSize+1));
struct Interval* result = malloc(sizeof(intervals) * (intervalsSize+1));
//将最新的区间放到集合的后面，一并打包放入新容器中（result跟着一起赋值）
for (int i = 0; i <= intervalsSize; i++) {
if (i == intervalsSize) {
temp[i].start = newInterval.start;
temp[i].end = newInterval.end;
}else {
temp[i].start = intervals[i].start;
temp[i].end = intervals[i].end;
result[i].start = intervals[i].start;
result[i].end = intervals[i].end;
}
}
//记录下标,处理最后一个新区间即可
int index = intervalsSize;
for (int i = intervalsSize; i <= intervalsSize; i++) {
//右相离(加到后面)
if (temp[i].start > result[index-1].end) {
result[index].start = temp[i].start;
result[index].end = temp[i].end;
index++;
//左相离(插到前面)
}else if (temp[i].end < result[index-1].start) {
if (index == 1) {
result[1].start = result[0].start;
result[1].end = result[0].end;
result[0].start = temp[i].start;
result[0].end = temp[i].end;
index++;
}else {
temp[i-1].start = temp[i].start;
temp[i-1].end = temp[i].end;
temp[i].start = result[index-1].start;
temp[i].end = result[index-1].end;
index--;
i -= 2;
}
//左相交
}else if (temp[i].start < result[index-1].start && temp[i].end <= result[index-1].end) {
if (index == 1) result[0].start = temp[i].start;
else {
temp[i].end = result[index-1].end;
i--;
index--;
}
//右相交
}else if (temp[i].start >= result[index-1].start && temp[i].end > result[index-1].end) {
result[index-1].end = temp[i].end;
//包含及相等
}else if (temp[i].start < result[index-1].start && temp[i].end > result[index-1].end) {
if (index == 1) {
result[0].start = temp[i].start;
result[0].end = temp[i].end;
}else {
index--;
i--;
}
}
}
*returnSize = index;
return result;
}
demo这样就可以了，但是如果真做项目的时候要记得把temp的内存释放掉。。。
