前言
思路及算法思维,指路 代码随想录。
题目来自 LeetCode。
day 37,周四,坚持~
题目详情
[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] 单调递增的数字
题目描述
解题思路
前提:求数字呈单调递增。
思路:从后往前遍历字符数组,判断单调递增, 标识赋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的位置,其后所有均赋9
flag = i;
numArray[i - 1] -= 1;
}
}
// 将标记位及其之后均赋字符9
for (int j = flag; j < arrLen; j++) {
numArray[j] = '9';
}
// 字符数组转数值
return atoi(numArray);
}
[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)
{
// 空节点返回有覆盖状态1
if (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;
}
今日收获
- 贪心算法:若有若无的贪心思维,不是很容易想到的解法。