【代码随想录】【算法训练营】【第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的位置,其后所有均赋9
            flag = i;
            numArray[i - 1] -= 1;
        }
    }
    // 将标记位及其之后均赋字符9
    for (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)
{
    // 空节点返回有覆盖状态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;
}

今日收获

1. 贪心算法：若有若无的贪心思维，不是很容易想到的解法。