作者推荐
【动态规划】【字符串】【表达式】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;
}
};
