首页 计算机科学 算法 LeetCode

# 单调递增的数字

题目链接🔗

一旦出现 strNum[i - 1] > strNum[i] 的情况（非单调递增），首先想让 strNum [i - 1]--，然后 strNum [i] 给为 9。

从后向前遍历，重复利用上次比较的结果，此时局部最优可以推出全局最优。

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);
    }
};

# 监控二叉树

题目链接🔗

摄像头可以覆盖上中下三层，如果放在叶子节点上会浪费一层，并且不放在叶子节点上能省下指数级的数量。

树从下往上看。局部最优：让叶子节点的父节点安摄像头，所用摄像头最少。全局最优：全部摄像头数量所用最少。

大体思路就是从下到上的后序遍历，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。

此时需要状态转移方程来放摄像头。

用三个数字表示节点的三种状态：

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

空节点的状态为有覆盖，这样就能在叶子节点的父节点放摄像头了。

因为空节点如果是无覆盖状态，叶子节点就要放摄像头。如果是有摄像头状态，叶子节点的父节点就没必要放摄像头了。

那么树的节点将会有四类情况：

  1. 左右子节点都有覆盖，那么本节点无覆盖。
  2. 左右子节点有一个无覆盖，那么本节点放摄像头。
    • left == 0 && right == 0 左右节点无覆盖
    • left == 1 && right == 0 左节点有摄像头，右节点无覆盖
    • left == 0 && right == 1 左节点有无覆盖，右节点摄像头
    • left == 0 && right == 2 左节点无覆盖，右节点覆盖
    • left == 2 && right == 0 左节点覆盖，右节点无覆盖
  3. 左右子节点至少有一个摄像头，那么本节点有覆盖。
    • left == 1 && right == 2 左节点有摄像头，右节点有覆盖
    • left == 2 && right == 1 左节点有覆盖，右节点有摄像头
    • left == 1 && right == 1 左右节点都有摄像头
  4. 根节点无覆盖，放摄像头。
class Solution {
private:
    int result;
    int traversal(TreeNode* cur) {
        if (cur == NULL) return 2;  // 空节点为有覆盖
        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右
        if (left == 2 && right == 2) return 0;  // 左右子节点都有覆盖
        else if (left == 0 || right == 0) {     // 左右子节点有一个无覆盖
            result++;
            return 1;
        } else return 2;    // 左右子节点至少有一个摄像头
    }
public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) { //root 无覆盖
            result++;
        }
        return result;
    }
};