当前位置: 首页 > news >正文

leetcode 968 监控摄像头

监控摄像头

在这里插入图片描述
在这里插入图片描述

从下往上看,局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少!

此时,大体思路就是从低到上,先给叶子节点父节点放个摄像头,然后隔两个节点放一个摄像头,直至到二叉树头结点。

我们分别有三个数字来表示:

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

  • 情况1:左右节点都有覆盖
    左孩子有覆盖,右孩子有覆盖,那么此时中间节点应该就是无覆盖的状态了。

在这里插入图片描述

  • 情况2:左右节点至少有一个无覆盖的情况
    如果是以下情况,则中间节点(父节点)应该放摄像头:
    在这里插入图片描述
  • 情况3:左右节点至少有一个有摄像头
    如果是以下情况,其实就是 左右孩子节点有一个有摄像头了,那么其父节点就应该是2(覆盖的状态)
  • 情况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);  // 右// 情况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;// 情况4if (traversal(root) == 0) { // root 无覆盖result++;}return result;}
};

二刷

/*** 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 result = 0;int track_back(TreeNode* cur){if(cur==nullptr) return 2;//有覆盖int left = track_back(cur->left);int right = track_back(cur->right);if(left==2&&right==2) return 0;//无覆盖if(left==0||right==0) {result++;return 1;//放摄像头}if(left==1||right==1) return 2;return -1;}int minCameraCover(TreeNode* root) {if(track_back(root)==0) result++;return result;}
};

原文地址:https://blog.csdn.net/qq_44814825/article/details/127227170

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请将相关资料发送至 809451989@qq.com 进行投诉反馈,一经查实,立即处理!

相关文章:

  • 根据硬件ID查看摄像头型号方案,可查任何一款摄像头芯片来源
  • android查看摄像头信息,获取Android设备上的详细的摄像头信息
  • python获取摄像头型号_python opencv设置摄像头分辨率以及各个参数的方法_python
  • python获取摄像头型号,python3.6 opencv获取摄像头代码
  • 我的世界服务器自动被踢怎么可以进去,我的世界中国版服务器中如何解决玩家作弊的简单方法...
  • VS2019+WDK10编写xp平台的驱动
  • Windows XP中手动安装驱动程序的方法
  • xp驱动和Win7驱动的区别
  • windows XP 驱动开发环境搭建
  • 戴尔1420装XP方法和驱动
  • window XP驱动开发(一)如何下载WDK
  • Window XP驱动开发(十) 驱动程序的基本结构
  • (14)[驱动开发]配置环境 VS2019 + WDK10 写 xp驱动
  • Window XP驱动开发(二) 环境搭建(VS2008+WDK+DDKWzard)及示例源码分析
  • DBA必知的170张Oracle常用动态性能表介绍
  • Linux-tcpdump
  • 【Linux】定时任务crontab和at命令详解
  • Java8 通关攻略
  • taro小程序直播
  • 计蒜客--蒜头君的新游戏