相机最小覆盖问题

简介: 相机最小覆盖问题

题目

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

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

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

二叉树递归套路

在这里插入图片描述
以x为头的树,返回值有3中情况:
1) x上面无相机,但是x是被覆盖的,而且x底下所有节点都被覆盖了在这种情况下,请问需要几个相机
2) x上面有相机,x是被覆盖的,而且x底下所有节点都被覆盖了在这种情况下,请问需要几个相机
3) x既无相机,也没被覆盖,x底下所有节点都被覆盖了在这种情况下,请问需要几个相机

在这里插入图片描述
二叉树递归套路是说,如果我们想以x为头的整棵树都被覆盖了,需要哪些可能性?
那就两种可能性。第1种可能性就是x上面有相机,但是它被覆盖了。
第2种可能就是x上面无相机,但它被覆盖了
会少一种可能性,这种情况下你的这个两种可能性是不够的,收集信息的时候,我确实需要我的左树告诉我,它没被覆盖,但它底下都被覆盖的相机数量,因为我这儿放一个相机是可以补救他们的

二叉树的递归套路意义是什么?
意义就在于,他起码能够给你一个最初始的想法,你去分析答案的过程中。你肯定是要画与指数之间的拓扑关系去分析答案的,如果你发现你的可能性不够,你就往里加信息

为啥我要求x下方都被覆盖?很显而易见。因为x如果没被覆盖,它至少有它的父能补救他。但如果x下方的点没被覆盖,你往上返回爷爷辈的节点就再也无法补救,没有被覆盖的节点了

    public static class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;
    }

    public static int minCameraCover1(TreeNode root) {
        Info data = process1(root);
        return (int) Math.min(data.uncovered + 1, Math.min(data.coveredNoCamera, data.coveredHasCamera));
    }

    // 潜台词:x是头节点,x下方的点都被覆盖的情况下
    public static class Info {
        public long uncovered; // x没有被覆盖,x为头的树至少需要几个相机
        public long coveredNoCamera; // x被相机覆盖,但是x没相机,x为头的树至少需要几个相机
        public long coveredHasCamera; // x被相机覆盖了,并且x上放了相机,x为头的树至少需要几个相机

        public Info(long un, long no, long has) {
            uncovered = un;
            coveredNoCamera = no;
            coveredHasCamera = has;
        }
    }

    // 所有可能性都穷尽了
    public static Info process1(TreeNode X) {
        if (X == null) { // base case
            return new Info(Integer.MAX_VALUE, 0, Integer.MAX_VALUE);
        }

        Info left = process1(X.left);
        Info right = process1(X.right);
        // x uncovered x自己不被覆盖,x下方所有节点,都被覆盖
        // 左孩子: 左孩子没被覆盖,左孩子以下的点都被覆盖
        // 左孩子被覆盖但没相机,左孩子以下的点都被覆盖
        // 左孩子被覆盖也有相机,左孩子以下的点都被覆盖
        long uncovered = left.coveredNoCamera + right.coveredNoCamera;

        // x下方的点都被covered,x也被cover,但x上没相机
        long coveredNoCamera = Math.min(
                // 1)
                left.coveredHasCamera + right.coveredHasCamera,
                Math.min(// 2)
                        left.coveredHasCamera + right.coveredNoCamera,
                        // 3)
                        left.coveredNoCamera + right.coveredHasCamera));
        // x下方的点都被covered,x也被cover,且x上有相机
        long coveredHasCamera = 
                Math.min(left.uncovered, Math.min(left.coveredNoCamera, left.coveredHasCamera))
                + Math.min(right.uncovered, Math.min(right.coveredNoCamera, right.coveredHasCamera))
                + 1;
        return new Info(uncovered, coveredNoCamera, coveredHasCamera);
    }
AI 代码解读

优化

在这里插入图片描述
对于空树
只有一种解,被覆盖了没相机
所以面对这种最简单的情况,我们其实就是不放相机,恐怕后续的解会最优
因此我们只需给父节点返回一种信息就够了
在这里插入图片描述
当左树和右树只返回一种结果给父节点,那么父节点也只用返回一种信息给爷爷节点

我们需要记录节点的状态,有3种
1)没被覆盖
2)被覆盖了有相机
3)被覆盖了没有相机

可能性分析
1)左树或者右树有一个没被覆盖的,父节点只能放相机
2)左树或者右树都被覆盖,且有一棵树有相机,父节点会被子树的相机覆盖,因此不放相机
3)左树或者右树都被覆盖,且都没放相机,父节点返回没被覆盖,留给爷爷节点放相机

代码

    public static int minCameraCover2(TreeNode root) {
        Data data = process2(root);
        return data.cameras + (data.status == Status.UNCOVERED ? 1 : 0);
    }

    // 以x为头,x下方的节点都是被covered,x自己的状况,分三种
    public static enum Status {
        UNCOVERED, COVERED_NO_CAMERA, COVERED_HAS_CAMERA
    }

    // 以x为头,x下方的节点都是被covered,得到的最优解中:
    // x是什么状态,在这种状态下,需要至少几个相机
    public static class Data {
        public Status status;
        public int cameras;

        public Data(Status status, int cameras) {
            this.status = status;
            this.cameras = cameras;
        }
    }

    public static Data process2(TreeNode X) {
        if (X == null) {
            return new Data(Status.COVERED_NO_CAMERA, 0);
        }
        Data left = process2(X.left);
        Data right = process2(X.right);
        int cameras = left.cameras + right.cameras;
        
        // 左、或右,哪怕有一个没覆盖
        if (left.status == Status.UNCOVERED || right.status == Status.UNCOVERED) {
            return new Data(Status.COVERED_HAS_CAMERA, cameras + 1);
        }

        // 左右孩子,不存在没被覆盖的情况
        if (left.status == Status.COVERED_HAS_CAMERA || right.status == Status.COVERED_HAS_CAMERA) {
            return new Data(Status.COVERED_NO_CAMERA, cameras);
        }
        // 左右孩子,不存在没被覆盖的情况,也都没有相机
        return new Data(Status.UNCOVERED, cameras);
    }
AI 代码解读
相关文章
一张图的七十二变——阿里云OSS图片处理实践
      小张是某视频网站的新入职的UED,日常工作就是创作各式各样的海报banner。踌躇满志的小张,上了三天班就蔫了。因为他在完成一张图的创作后,还需要考虑:• 同一张图会以不同的形式应用于网站各处:有时候需裁剪成不同形状,有时需要加水印,有时需转换格式....• 为了风格统一,不同的图需要保持样式统一:不同图片排列组成成一组,每组图片风格(
2611 0
Apache Doris 巨大飞跃:存算分离新架构
Apache Doris 巨大飞跃:全新的存算分离架构正式推出,SeiectDB 未来将贡献至 Apache Doris 社区
Apache Doris 巨大飞跃:存算分离新架构
独家 | 蚂蚁金服TRaaS技术风险防控平台解密
蚂蚁金服技术风险防控平台TRaaS的前世今生。
5935 0
【mycat】mycat在windows环境下的安装和启动
安装mycat前需要先安装jdk和mysql。mycat1.6版本建议使用的jdk是1.7以上版本,mysql建议使用5.6版本。安装玩jdk和mysql后,进入mycat解压目录下的bin目录,如本文的路径如下: D:\Program Files (x86)\mycat\bin 安装shift键,点击鼠标右键,选择"在此处打开命令窗口"打开命令行窗口(注意需要管理员账户登录,如果不是请使用管理员身份运行cmd打开命令行窗口)。在打开的命令行窗口中执行如下命令安装mycat: mycat.bat install
890 1
TTS语音合成技术
一, 语音合成技术原理 语音合成(test to speech),简称TTS。将文字转化为语音的一种技术,类似于人类的嘴巴,通过不同的音色说出想表达的内容。
6620 0
阿里云商标注册流程步骤
本文详细介绍阿里云商标注册流程步骤及阿里云商标注册价格
3747 0
阿里云商标注册流程步骤
阿里云配置审计 - 规则篇
阿里云配置审计提供了持续的合规审计功能,以审计规则作为落地合规审计的具体策略,基于自动化的手段帮助企业用户完善资源合规审计制度,确保“等级2.0”具体实施的快速落地。它一方面提供了丰富的托管审计规则,提供基础的合规审计功能,开箱即用,可以满足绝大部分用户需求;另外用户可以开发自定义的审计规则,完善内部最佳实践和指南。
5908 0
如何在技术团队中推行OKR
如何在技术团队中推行OKR OKR(Objectives & Key Results)是一种行之有效的目标管理方法,最早由Intel提出,后来被Google运用的炉火纯青,最终取得斐然成就。最近几年,越来越多的硅谷创业公司把OKR作为团队文化的基石。
8926 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问