1. 单调递增的数字

代码随想录：原文

力扣题目：738.单调递增的数字

1.1 思路

• 一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9
• 只有从后向前遍历才能重复利用上次比较的结果

1.2 代码实现

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strNum = to_string(N);
        // flag用来标记赋值9从哪里开始
        // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
        int flag = strNum.size();
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i] ) {
                flag = i;
                strNum[i - 1]--;
            }
        }
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};

2. 监控二叉树

代码随想录：原文

力扣题目： 968.监控二叉树

2.1 思路

• 局部最优：让叶子节点的父节点安摄像头，所用摄像头最少
• 整体最优：全部摄像头数量所用最少

确定遍历顺序

• 使用后序遍历也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了

int traversal(TreeNode* cur) {

    // 空节点，该节点有覆盖
    if (终止条件) return ;

    int left = traversal(cur->left);    // 左
    int right = traversal(cur->right);  // 右

    逻辑处理                            // 中
    return ;
}

如何隔两个节点放一个摄像头

每个节点有三种状态，分别用三个数字来表示：

• 0：该节点无覆盖
• 1：本节点有摄像头
• 2：本节点有覆盖

空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了

1. 递归的终止条件

• 空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了

// 空节点，该节点有覆盖
if (cur == NULL) return 2;

2. 单层逻辑处理

• 左右节点都有覆盖，左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了

// 左右节点都有覆盖
if (left == 2 && right == 2) return 0;

• 左右节点至少有一个无覆盖的情况，父节点就应该放摄像头。
• 此时摄像头的数量要加一，并且return 1，代表中间节点放摄像头。

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

• 左右节点至少有一个有摄像头，那么其父节点就应该是2（覆盖的状态）

if (left == 1 || right == 1) return 2;

• 头结点没有覆盖！！！
• 递归结束之后，可能头结点 还有一个无覆盖的情况
• 递归结束之后，还要判断根节点，如果没有覆盖，result++

int minCameraCover(TreeNode* root) {
    result = 0;
    if (traversal(root) == 0) { // root 无覆盖
        result++;
    }
    return result;
}

2.2 代码实现

class Solution {
private:
    int result;
    int traversal(TreeNode* cur) {

        // 空节点，该节点有覆盖
        if (cur == NULL) return 2;

        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右

        // 情况1
        // 左右节点都有覆盖
        if (left == 2 && right == 2) return 0;

        // 情况2
        // left == 0 && right == 0 左右节点无覆盖
        // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
        // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
        // left == 0 && right == 2 左节点无覆盖，右节点覆盖
        // left == 2 && right == 0 左节点覆盖，右节点无覆盖
        if (left == 0 || right == 0) {
            result++;
            return 1;
        }

        // 情况3
        // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        // left == 1 && right == 1 左右节点都有摄像头
        // 其他情况前段代码均已覆盖
        if (left == 1 || right == 1) return 2;

        // 以上代码我没有使用else，主要是为了把各个分支条件展现出来，这样代码有助于读者理解
        // 这个 return -1 逻辑不会走到这里。
        return -1;
    }

public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        // 情况4
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};

3. 总结

• 贪心无套路，也没有框架之类的
• 如果找出局部最优并可以推出全局最优，就是贪心
• 手动模拟一下，如果找不出反例，就试试贪心
• 出现两个维度相互影响的情况时，两边一起考虑一定会顾此失彼，要先确定一个维度，再确定另一个一个维度