侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 127 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

代码随想录算法训练营第三十七天 | 单调递增的数字;监控二叉树 ;总结

thinkTV
2023-05-26 / 0 评论 / 0 点赞 / 108 阅读 / 1,157 字 / 正在检测是否收录...

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;

  1. 单层逻辑处理
  • 左右节点都有覆盖,左孩子有覆盖,右孩子有覆盖,那么此时中间节点应该就是无覆盖的状态了

图片1

// 左右节点都有覆盖
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++

图片2

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. 总结

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

评论区