企业官网建设流程全解析

建设股公司网站,十个最好的网站,龙岗区建设工程交易服务中心,公司部门网站设计模板哈喽各位#xff0c;我是前端小L。 欢迎来到贪心算法专题的大结局#xff01; 题目背景很简单#xff1a;给定一棵二叉树#xff0c;我们在节点上安装摄像头。 一个摄像头可以监控它自己、它的父节点、它的子节点。 目标#xff1a;计算监控整棵树所需的最少摄像头数量。…哈喽各位我是前端小L。欢迎来到贪心算法专题的大结局 题目背景很简单给定一棵二叉树我们在节点上安装摄像头。一个摄像头可以监控它自己、它的父节点、它的子节点。目标计算监控整棵树所需的最少摄像头数量。力扣 968. 监控二叉树https://leetcode.cn/problems/binary-tree-cameras题目分析输入二叉树的根节点root。输出摄像头的最小数量。核心思维自底向上的贪心直觉问题摄像头放在哪最划算如果放在叶子节点它只能监控自己和父节点最多 2 个。如果放在叶子节点的父节点它可以监控父节点、自己、两个子节点最多 4 个。贪心策略绝对不要把摄像头放在叶子节点上这样太浪费了。 我们要让叶子节点的父节点去放摄像头这样能“以此保三”保住父、自、子。既然要从叶子节点开始考虑那我们的遍历顺序必须是后序遍历左右根即自底向上推导。状态定义每个节点可能有三种状态我们需要用数字标记0无覆盖(该节点没被监控等着别人来救它)。1有摄像头(该节点自己装了摄像头)。2有覆盖(该节点被监控了但不是自己装的是被子节点或父节点照亮的)。状态转移逻辑核心对于当前节点我们检查它的左右孩子情况一左右孩子都有覆盖 (State 2)孩子都安全了那当前节点需要装摄像头吗不需要。为了贪心省摄像头当前节点最好别装等着它的父节点装摄像头来监控它。所以当前节点状态设为0 (无覆盖)。情况二左右孩子至少有一个无覆盖 (State 0)只要有一个孩子在呼救当前节点作为父亲必须挺身而出必须装摄像头。cameras。当前节点状态设为1 (有摄像头)。情况三左右孩子至少有一个有摄像头 (State 1)孩子里有摄像头那当前节点就被孩子照亮了。当前节点安全了。当前节点状态设为2 (有覆盖)。特殊情况根节点遍历结束后如果根节点状态是 0无覆盖因为根节点没有父节点了没人能救它。必须给根节点补一个摄像头。算法流程 (JavaScript)定义结果变量res 0。定义递归函数traversal(node)终止条件如果node为空返回什么状态空节点不能是“无覆盖”否则叶子节点会为了救空节点而装摄像头浪费。空节点也不能是“有摄像头”。空节点应该视为“有覆盖” (2)。这样叶子节点看到空孩子是 2自己就会变成 0等着父节点来救符合贪心策略。递归left traversal(node.left)right traversal(node.right)逻辑判断if (left 0 || right 0) - 装摄像头res返回 1。if (left 1 || right 1) - 被覆盖返回 2。if (left 2 right 2) - 无覆盖返回 0。主函数调用traversal(root)。检查返回值如果 root 也是 0res。返回res。代码实现深度辨析为什么顺序不能乱在代码中判断顺序非常关键先判0 (无覆盖)救人要紧。只要有孩子没被覆盖必须装摄像头。再判1 (有摄像头)如果没人求救但有孩子有摄像头我就蹭个光。最后默认孩子都安全我就先“躺平”状态 0。如果你把判断顺序搞乱了比如先判断有没有被覆盖可能会导致在需要装摄像头的时候没装破坏了覆盖结构。总结贪心算法毕业典礼恭喜你坚持到了这里。 这道题融合了树的遍历、状态机、局部贪心是当之无愧的贪心压轴题。回顾我们的贪心之旅基础分发饼干排序匹配。序列摆动序列视觉上的峰谷。股票买卖股票 II收集每一滴利润。覆盖跳跃游戏 I II维护最大范围。维度分发糖果、重建队列拆分维度逐个击破。区间射气球、无重叠、合并区间Start排序 边界更新这是最重要的模板。数字单调递增数字借位思想。树形监控二叉树自底向上状态推导。掌握了这些你已经建立了一套完整的**“贪心直觉”。在未来的面试中当你面对一个“求最值”的问题如果 DP 太复杂不妨先问问自己“如果我只顾眼前能不能推导出全局最优”**