Day32- 贪心算法part06

发布时间:2024年01月18日

?一、单调递增的数字

题目一:738. 单调递增的数字?

738. 单调递增的数字

当且仅当每个相邻位数上的数字?x?和?y?满足?x <= y?时,我们称这个整数是单调递增的。

给定一个整数?n?,返回?小于或等于?n?的最大数字,且数字呈?单调递增?。

从高位到低位遍历整数 n 的每一位数字,当发现某一位数字大于其后一位数字时,将这一位数字减一,并将所有更低位的数字设置为 9,以确保结果是单调递增的。

/*
 * @lc app=leetcode.cn id=738 lang=cpp
 *
 * [738] 单调递增的数字
 */

// @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

二、监控二叉树

题目一:968. 监控二叉树

968. 监控二叉树

给定一个二叉树,我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

基本思路是从叶子节点开始向上,尽量在每个节点的父节点上安装摄像头,以覆盖尽可能多的节点。这样可以保证使用最少的摄像头覆盖所有节点。

可以定义三种状态:

  1. 0:这个节点尚未被覆盖。
  2. 1:这个节点有一个摄像头。
  3. 2:这个节点已被覆盖,但没有摄像头。
/*
 * @lc app=leetcode.cn id=968 lang=cpp
 *
 * [968] 监控二叉树
 */

// @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

文章来源:https://blog.csdn.net/m0_66690787/article/details/135685231
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。