【代码随想录】【算法训练营】【第37天】 [56]合并区间 [738]单调递增的数字 [968]监控二叉树

本文主要是介绍【代码随想录】【算法训练营】【第37天】 [56]合并区间 [738]单调递增的数字 [968]监控二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

思路及算法思维，指路代码随想录。
题目来自 LeetCode。

day 37，周四，坚持~

题目详情

[56] 合并区间

题目描述

56 合并区间

解题思路

前提：判断区间是否重合。
思路：按照左边界从小到大排序，遍历区间，判断区间是否有重叠，重叠区间合并。
重点：判断区间重合。

代码实现

C语言

贪心思维

按照左边界从小到大排序，遍历区间，判断区间是否有重叠，重叠区间合并。

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/int cmp(const void *p1, const void *p2)
{int *pp1 = *(int **)p1;int *pp2 = *(int **)p2;// 按照左边界从小到大排序，左边界相同按右边界从小到大排序return (pp1[0] == pp2[0]) ? (pp1[1] - pp2[1]) : (pp1[0] - pp2[0]);
}int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {// 按照左边界从小到大排序，左边界相同按右边界从小到大排序qsort(intervals, intervalsSize, sizeof(int *), cmp);for (int k = 0; k < intervalsSize; k++) {}//输出初始化int **ans = (int **)malloc(sizeof(int *) * intervalsSize);int ansSize = 0;// 遍历区间，重叠区间合并int curStart = intervals[0][0];int curEnd = intervals[0][1];for (int i = 1; i < intervalsSize; i++) {// 判断区间是否有重叠if (intervals[i][0] <= curEnd) {if (curEnd < intervals[i][1]) {curEnd = intervals[i][1];}} else {// 不重叠部分，保存上一段区间ans[ansSize] = (int *)malloc(sizeof(int) * (*intervalsColSize));ans[ansSize][0] = curStart;ans[ansSize][1] = curEnd;ansSize++;// 保存当前区间起始位置curStart = intervals[i][0];curEnd = intervals[i][1];}}// 保存当前区间ans[ansSize] = (int *)malloc(sizeof(int) * (*intervalsColSize));ans[ansSize][0] = curStart;ans[ansSize][1] = curEnd;ansSize++;// 输出*returnSize = ansSize;*returnColumnSizes = (int *)malloc(sizeof(int) * ansSize);for (int j = 0; j < ansSize; j++) {(*returnColumnSizes)[j] = *intervalsColSize;}return ans;
}

[738] 单调递增的数字

题目描述

738 单调递增的数字

解题思路

前提：求数字呈单调递增。
思路：从后往前遍历字符数组，判断单调递增，标识赋9的位置，将标记位及其之后均赋字符9，最后字符数组转数值输出。
重点：贪心思维。

代码实现

C语言

贪心思维

从后往前遍历字符数组，判断单调递增，标识赋9的位置，将标记位及其之后均赋字符9，字符数组转数值输出。

#define MAX_NUM_LEN  (11)int monotoneIncreasingDigits(int n) {char numArray[MAX_NUM_LEN];int arrLen = 0;// 数字转换字符arrLen = sprintf(numArray, "%d", n);// 从后往前遍历数组int flag = arrLen;for (int i = arrLen - 1; i > 0; i--) {// 判断单调递增if (numArray[i - 1] > numArray[i]) {// 标识赋9的位置,其后所有均赋9flag = i;numArray[i - 1] -= 1;}}// 将标记位及其之后均赋字符9for (int j = flag; j < arrLen; j++) {numArray[j] = '9';}// 字符数组转数值return atoi(numArray);
}

[968] 监控二叉树

题目描述

968 监控二叉树

解题思路

前提：二叉树遍历
思路：局部最优：让叶子节点的父节点安摄像头，所用摄像头最少；整体最优：全部摄像头数量所用最少。
重点：二叉树遍历方式；如果标识结点是否需要安装摄像头。

代码实现

C语言

贪心算法

局部最优：让叶子节点的父节点安摄像头，所用摄像头最少；整体最优：全部摄像头数量所用最少。
从叶子结点向根节点遍历，使用后序（左右中）遍历二叉树结点。
标识结点的3种状态：0 - 无覆盖（初始状态）， 1 - 有覆盖， 2 - 安装摄像头

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int count = 0;// 返回值标识当前root结点 0 - 无覆盖， 1 - 有覆盖， 2 - 有摄像头
int travsel(struct TreeNode *root)
{// 空节点返回有覆盖状态1if (root == NULL) {return 1;}// 后序遍历，左右中int left = travsel(root->left);int right = travsel(root->right);// 判断当前根节点状态int mid = 0;if ((left == 1) && (right == 1)) {// 左右子节点均有覆盖时，该节点无覆盖mid = 0;} else if ((left == 0) || (right == 0)) {// 左右结点至少有一个无覆盖时，该节点需要安装摄像头mid = 2;count++;}else {// 其他情况：左右结点至少有一个有摄像头时，该结点有覆盖mid = 1;}return mid;
}int minCameraCover(struct TreeNode* root) {// 全局变量初始化count = 0;// 后序遍历二叉树，判断当前结点是否无覆盖，需要安装摄像头// 根节点if (travsel(root) == 0) {count++;}return count;
}