代码随想录算法训练营第三十一天|Day31 贪心算法
56. 合并区间
https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html
思路
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是一个指针的指针,用于返回每个合并后区间的列数。
- 在进行区间的排序时,使用了qsort函数,并自定义了比较函数compare。这样可以根据起始位置进行排序,方便后续的合并操作。
- 在进行区间的合并时,使用了两个指针start和end来表示当前合并的区间的起始和结束位置。通过比较当前区间的起始位置和前一个区间的结束位置,来判断是否需要合并区间。
- 在合并区间时,通过动态分配内存来创建新的区间,并将其添加到mergedIntervals数组中保存。在最后返回结果之前,还需要动态分配内存来保存每个合并后区间的列数。
738.单调递增的数字
https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html
思路
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);
}
学习反思
实现了将一个非负整数变为一个单调递增的整数的功能。代码中的monotoneIncreasingDigits函数接收一个非负整数n作为参数,并返回变换后的单调递增的整数。首先定义了一个长度为11的字符数组num,用于保存整数n的每一位数字。使用sprintf函数将整数n转换为字符串,并存储在num中。然后使用strlen函数获取字符串的长度len。接下来,使用一个变量mark来标记需要递减的位置。从后往前遍历字符串num,如果当前位置的数字小于前一个位置的数字,则将mark设置为当前位置,并将当前位置的数字减一。然后,从mark位置开始,将后面所有的数字都设置为9,以保证整数递增。最后,使用atoi函数将字符串num转换为整数,并返回结果。
总结
加油!!!