Leetcode

968. 监控二叉树 给定一个二叉树，我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。 示例 1： 输入：[0,0,null,0,0] 输出：1 解释：如图所示，一台摄像头足以监控所有节点。 示例 2： 输入：[0,0,null,0,null,0,null,null,0] 输出：2 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。 提示： 给定树的节点数的范围是 [1, 1000]。 每个节点的值都是 0。 java代码 这是一道hard难度的题目。我们要从底向上进行推导，因为尽量让叶子节点的父节点安装摄像头，这样摄像头的数量才是最少的。 如何从低向上推导呢？ 采用后序遍历也就是左右中的顺序，这样就可以从下到上进行推导了。 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { //NO_CAMERA表示的是子节点没有相机，当前节点也没放相机 private final int NO_CAMERA = 0; //HAS_CAMERA表示当前节点有一个相机 private final int HAS_CAMERA = 1; //NO_NEEDED表示当前节点没有相机，但他的子节点有一个相机，把它给 //覆盖了，所以它不需要了。或者他是一个空的节点也是不需要相机的 private final int NO_NEEDED = 2; //全局的，统计有多少相机 int res = 0; public int minCameraCover(TreeNode root) { //边界条件判断 if (root == null) return 0; //如果最后返回的是NO_CAMERA，表示root节点的子节点也没有相机， //所以root节点要添加一个相机 if (dfs(root) == NO_CAMERA) res++; //返回结果 return res; } public int dfs(TreeNode root) { //如果是空的，就不需要相机了 if (root == null) return NO_NEEDED; int left = dfs(root....

题目 一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。 为了尽快到达公主，骑士决定每次只向右或向下移动一步。 编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。 例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。 -2 (K) -3 3 -5 -10 1 10 30 -5 (P) 说明: 骑士的健康点数没有上限。 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。 思路 参考了评论中的答案，使用动态规划 核心思路是：每次只能往右边或者下面走，那么如果你知道了往右边走需要的最小生命代价和往下面需要的最小生命代价，那么你就知道了当前需要的最小代价 使用二维数组来保存最小生命代价，life[i][j]表示从i，j开始走到右下角的最小生命代价 从右下开始往上动态规划，初始话最小代价是1，如果当前不需要额外的生命代价的话，那么当前的最小生命代价就是1，如果需要额外的代价的话，那么最小生命代价就是额外需要的代价。 说的比较绕口，代码应该比较好理解，总的思路就是，如果后面不需要额外生命，那么你只需要保证能走到当前就可以了，如果后面需要额外代价，那么你需要保证能走到当前并且+后面的额外生命代价 java代码 class Solution { // 求骑士走到右下角的最低生命值 // 只能右或者下 // DP public int calculateMinimumHP(int[][] dungeon) { int row = dungeon.length; int col = dungeon[0].length; int[][] life = new int[row][col]; // life[i][j] 表示i,j的时候需要的最小生命值，肯定不能小于1 // 初始化 if(dungeon[row - 1][col - 1] < 0){ life[row - 1][col - 1] = -dungeon[row - 1][col - 1] + 1; }else { life[row - 1][col - 1] = 1; } // 初始化最后一列 for(int i = row - 2; i >= 0; i--){ if(life[i+1][col-1] == 1){ // 表示后面的可以自己满足 life[i][col-1] = Math....