代码随想录算法训练营第三十一天|Day31 贪心算法

56. 合并区间

思路

int compare(const void *a, const void *b) {int *intervalA = *(int **)a;int *intervalB = *(int **)b;return intervalA[0] - intervalB[0]; 
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {if (intervalsSize == 0) {*returnSize = 0;return NULL;}qsort(intervals, intervalsSize, sizeof(int *), compare);int **mergedIntervals = (int **)malloc(intervalsSize * sizeof(int *));int count = 0; int start = intervals[0][0];int end = intervals[0][1];for (int i = 1; i < intervalsSize; i++) {if (intervals[i][0] <= end) { if (intervals[i][1] > end) {end = intervals[i][1]; }} else { mergedIntervals[count] = (int *)malloc(2 * sizeof(int));mergedIntervals[count][0] = start;mergedIntervals[count][1] = end;count++;start = intervals[i][0];end = intervals[i][1];}}mergedIntervals[count] = (int *)malloc(2 * sizeof(int));mergedIntervals[count][0] = start;mergedIntervals[count][1] = end;count++;*returnSize = count; *returnColumnSizes = (int *)malloc(count * sizeof(int));for (int i = 0; i < count; i++) {(*returnColumnSizes)[i] = 2; }return mergedIntervals; 
}

学习反思

实现了合并区间的功能。代码中的compare函数用于qsort函数的比较操作，按照区间的起始位置进行排序。merge函数将传入的区间数组进行排序，并且遍历数组进行合并操作。当当前区间的起始位置小于等于前一个区间的结束位置时，则合并区间；否则，将当前区间添加到mergedIntervals中，并更新start和end的值。最后，返回合并后的区间数组mergedIntervals。对于传入的参数，intervals是一个二维数组，表示需要合并的区间；intervalsSize表示区间的个数；intervalsColSize是一个一维数组，表示每个区间的列数；returnSize是一个指针，用于返回合并后的区间个数；returnColumnSizes是一个指针的指针，用于返回每个合并后区间的列数。

1. 在进行区间的排序时，使用了qsort函数，并自定义了比较函数compare。这样可以根据起始位置进行排序，方便后续的合并操作。
2. 在进行区间的合并时，使用了两个指针start和end来表示当前合并的区间的起始和结束位置。通过比较当前区间的起始位置和前一个区间的结束位置，来判断是否需要合并区间。
3. 在合并区间时，通过动态分配内存来创建新的区间，并将其添加到mergedIntervals数组中保存。在最后返回结果之前，还需要动态分配内存来保存每个合并后区间的列数。

int monotoneIncreasingDigits(int n) {char num[11]; sprintf(num, "%d", n);int len = strlen(num);int mark = len; for (int i = len - 1; i > 0; i--) {if (num[i] < num[i - 1]) {mark = i; num[i - 1]--; }}for (int i = mark; i < len; i++) {num[i] = '9';}return atoi(num);
}