?一、單調(diào)遞增的數(shù)字

題目一：738. 單調(diào)遞增的數(shù)字?

738. 單調(diào)遞增的數(shù)字

當(dāng)且僅當(dāng)每個(gè)相鄰位數(shù)上的數(shù)字?x?和?y?滿足?x <= y?時(shí)，我們稱這個(gè)整數(shù)是單調(diào)遞增的。

給定一個(gè)整數(shù)?n?，返回?小于或等于?n?的最大數(shù)字，且數(shù)字呈?單調(diào)遞增?。

從高位到低位遍歷整數(shù) n 的每一位數(shù)字，當(dāng)發(fā)現(xiàn)某一位數(shù)字大于其后一位數(shù)字時(shí)，將這一位數(shù)字減一，并將所有更低位的數(shù)字設(shè)置為 9，以確保結(jié)果是單調(diào)遞增的。

/*
 * @lc app=leetcode.cn id=738 lang=cpp
 *
 * [738] 單調(diào)遞增的數(shù)字
 */

// @lc code=start
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string str = to_string(n);
        int marker = str.size();

        for (int i = str.size() - 1; i > 0; i--) {
            if (str[i] < str[i - 1]) {
                marker = i;
                str[i - 1] = str[i - 1] - 1;
            }
        }

        for (int i = marker; i < str.size(); i++) {
            str[i] = '9';
        }

        return stoi(str);
    }
};
// @lc code=end

二、監(jiān)控二叉樹(shù)

題目一：968. 監(jiān)控二叉樹(shù)

968. 監(jiān)控二叉樹(shù)

給定一個(gè)二叉樹(shù)，我們?cè)跇?shù)的節(jié)點(diǎn)上安裝攝像頭。

節(jié)點(diǎn)上的每個(gè)攝影頭都可以監(jiān)視其父對(duì)象、自身及其直接子對(duì)象。

計(jì)算監(jiān)控樹(shù)的所有節(jié)點(diǎn)所需的最小攝像頭數(shù)量。

基本思路是從葉子節(jié)點(diǎn)開(kāi)始向上，盡量在每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)上安裝攝像頭，以覆蓋盡可能多的節(jié)點(diǎn)。這樣可以保證使用最少的攝像頭覆蓋所有節(jié)點(diǎn)。

可以定義三種狀態(tài)：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-815201.html

1. 0：這個(gè)節(jié)點(diǎn)尚未被覆蓋。
2. 1：這個(gè)節(jié)點(diǎn)有一個(gè)攝像頭。
3. 2：這個(gè)節(jié)點(diǎn)已被覆蓋，但沒(méi)有攝像頭。

/*
 * @lc app=leetcode.cn id=968 lang=cpp
 *
 * [968] 監(jiān)控二叉樹(shù)
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minCameraCover(TreeNode* root) {
        int cameras = 0;
        int top = dfs(root, cameras);
        return cameras + (top == 0 ? 1 : 0);
    }

private:
    int dfs(TreeNode* node, int& cameras) {
        if (!node) return 2;

        int left = dfs(node->left, cameras);
        int right = dfs(node->right, cameras);

        if (left == 0 || right == 0) {
            cameras++;
            return 1;
        }

        return (left == 1 || right == 1) ? 2 : 0;
    }
};
// @lc code=end

到了這里，關(guān)于Day32- 貪心算法part06的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！