【动态规划】【树形dp】【C++算法】968监控二叉树

简介: 【动态规划】【树形dp】【C++算法】968监控二叉树

作者推荐

【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数

本文涉及知识点

动态规划汇总

LeetCode:968监控二叉树

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

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

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

示例 1:

输入:[0,0,null,0,0]

输出:1

解释:如图所示,一台摄像头足以监控所有节点。

示例 2:

输入:[0,0,null,0,null,0,null,null,0]

输出:2

解释:需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

提示:

给定树的节点数的范围是 [1, 1000]。

每个节点的值都是 0。

动态规划

动态规划的状态表示

Rec(root)返回int i1,i2,i3,表示后面三种情况需要的最少摄像头。 i1,表示此子树根节点有摄像头,且子树所有节点都被监控。i2,此子树根节没有摄像头,所有节点都被监控。i3,此子树根节点无摄像头,根节点无监控,除根节点外都被监控。

动态规划的转移方程

叶子节点见初始值,本部分只讨论,非叶子节点:

i3 = min(lefti2)+min(righti2)

i2 ,左节点i1,右节点i1或i2 。或右节点i1,左节点i1,i2不存在。如果右节点不存在,则左节点i1。如果左节点不存在,则右节点i1。

i1 1 + min(lefti1,lefti2,lefti3)+min(righti1,righti2,righti3)

如果当前节点增加摄像头,则左右子树,无轮是否存在,i1,i2,i3 全部是i1。

如果当前节点没摄像头

a,一个子树i1,另外一个子树i1,i2或不存在,都是i2。

b,一个字树i1,另外一个字树i3不合法。

c,没有子树i1。两者都i2。就是i3。

动态规划的初始值

叶子节点i1,i2,i3分别为:1, 1000,0 。 1000或更大的数,表示这种可能不存在。

动态规划的填表顺序

树的先序遍历

动态规划的返回值

root的i1。

代码

核心代码

class Solution {
public:
  int minCameraCover(TreeNode* root) {    
    const auto [i1,i2,i3] =  Rec(root);
    return max(1, min(i1, i2));
  }
  std::tuple<int, int,int> Rec(TreeNode* root)
  {
    if ((nullptr == root->left) && (nullptr == root->right))
    {
      return std::make_tuple(1, 1000, 0);
    }
    int i3 = 0;
    int i21 = 1000,i22=1000;
    int i1 = 1;// 
    int iLeftMin = -1, iRightMin = -1;
    if (nullptr != root->left)
    {
      auto [t1, t2,t3] = Rec(root->left);
      iLeftMin = min(t1, t2);
      i3 += t2;
      i21 = t1;
      i1 += min(t1, min(t2, t3));
    }
    if (nullptr != root->right)
    {
      auto [t1, t2, t3] = Rec(root->right);
      iRightMin = min(t1, t2);
      i3 += t2;
      i22 = t1;
      i1 += min(t1,min(t2, t3));
    } 
    if (nullptr != root->left)
    { 
      i22 += iLeftMin;
    }
    if (nullptr != root->right)
    {     
      i21 += iRightMin;
    }
    const int i2 = min(i21, i22);
    //assert((i1 >= i3) && (i2 >= i3 ));
    std::cout << "val: " << root->val << " i1: " << i1 << " i2:" << i2 << " i3: " << i3 << std::endl;
    return std::make_tuple(i1, i2,i3);
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  int x,  target;
  const int null = 10000;
  {
    vector<int> nodes = { 1, null, 3, null, 5, null, 7, null, 9, 10, 11, null, null, 14, 15 };
    auto root = NTree::Init(nodes);
    Solution sln;
    auto res = sln.minCameraCover(root);
    Assert(res, 3);
  }
  {
    vector<int> nodes = { 1, 2, null, 4, null, 6, null, null, 9 };
    auto root = NTree::Init(nodes);
    Solution sln;
    auto res = sln.minCameraCover(root);
    Assert(res, 2);
  }
  {
    vector<int> nodes = { 1, 2, null, 3, 4 };
    auto root = NTree::Init(nodes);
    Solution sln;
    auto res = sln.minCameraCover(root);
    Assert(res, 1);
  }
  
  
}

优化

空节点为边界条件,更简洁。

class Solution {
public:
  int minCameraCover(TreeNode* root) {    
    const auto [i1,i2,i3] =  Rec(root);
    return max(1, min(i1, i2));
  }
  std::tuple<int, int,int> Rec(TreeNode* root)
  {
    if (nullptr == root )
    {
      return std::make_tuple(1000,0,0);
    }
    auto [l1,l2,l3] = Rec(root->left);
    auto [r1, r2, r3] = Rec(root->right);
    int i1 = 1 + min(min(l1,l2),l3) + min(min(r1, r2), r3);
    int i2 = min(l1 + r2, r1 + l2);
    i2 = min(i2, l1 + r1);
    int i3 = l2 + r2;
    return std::make_tuple(i1, i2,i3);
  }
};

2023年1月版

struct CStatus

{

int m_iFillAndRootHas;// 覆盖所有节点且根节点有监控

int m_iFill;// 覆盖所有节点,根节点不一定有监控

int m_iFillChild;//覆盖子节点,不一定覆盖根节点

};

class Solution {

public:

int minCameraCover(TreeNode* root) {

CStatus stuatu = dfs(root);

return stuatu.m_iFill;

}

CStatus dfs(TreeNode* root)

{

if (nullptr == root)

{

return{ INT_MAX / 2, 0, 0 };

}

CStatus left = dfs(root->left);

CStatus right = dfs(root->right);

CStatus ret;

ret.m_iFillAndRootHas = 1 + left.m_iFillChild + right.m_iFillChild;

ret.m_iFill = min(ret.m_iFillAndRootHas, min(left.m_iFillAndRootHas+right.m_iFill,right.m_iFillAndRootHas+left.m_iFill));

ret.m_iFillChild = min(ret.m_iFillAndRootHas,left.m_iFill + right.m_iFill);

std::cout << ret.m_iFillAndRootHas << " " << ret.m_iFill << " " << ret.m_iFillChild << std::endl;

return ret;

}

};


目录
打赏
0
1
1
1
36
分享
相关文章
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
27 15
|
26天前
|
内网监控系统之 Go 语言布隆过滤器算法深度剖析
在数字化时代,内网监控系统对企业和组织的信息安全至关重要。布隆过滤器(Bloom Filter)作为一种高效的数据结构,能够快速判断元素是否存在于集合中,适用于内网监控中的恶意IP和违规域名筛选。本文介绍其原理、优势及Go语言实现,提升系统性能与响应速度,保障信息安全。
28 5
深度洞察内网监控电脑:基于Python的流量分析算法
在当今数字化环境中,内网监控电脑作为“守城卫士”,通过流量分析算法确保内网安全、稳定运行。基于Python的流量分析算法,利用`scapy`等工具捕获和解析数据包,提取关键信息,区分正常与异常流量。结合机器学习和可视化技术,进一步提升内网监控的精准性和效率,助力企业防范潜在威胁,保障业务顺畅。本文深入探讨了Python在内网监控中的应用,展示了其实战代码及未来发展方向。
|
30天前
|
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
50 5
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
46 10
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
61 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
48 12
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
51 2
探秘局域网桌面监控:深入剖析 Java 语言核心算法
在数字化办公时代,局域网桌面监控如同企业的“智慧鹰眼”,确保工作效率与数据安全。本文以Java为载体,揭示哈希表在监控中的关键应用。通过高效的数据结构和算法,哈希表能快速索引设备连接信息,大幅提升监控的时效性和响应速度。代码示例展示了如何用Java实现设备网络连接监控,结合未来技术如AI、大数据,展望更智能的监控体系,助力企业在数字化浪潮中稳健前行。
企业局域网监控软件中 Java 优先队列算法的核心优势
企业局域网监控软件是数字化时代企业网络安全与高效运营的基石,犹如一位洞察秋毫的卫士。通过Java实现的优先队列算法,它能依据事件优先级排序,确保关键网络事件如异常流量、数据泄露等被优先处理,保障系统稳定与安全。代码示例展示了如何定义网络事件类并使用PriorityQueue处理高优先级事件,尤其在面对疑似风险时迅速启动应急措施。这一核心技术助力企业在复杂网络环境中稳健前行,护航业务腾飞。
65 32
AI助理

你好,我是AI助理

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