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....

hexo资料 hexo文档 https://hexo.io/zh-cn/docs/ hexo常用主题 hexo next主题 https://theme-next.iissnan.com/getting-started.html hexo常用命令 npm install hexo -g //安装 npm update hexo -g //升级 hexo version //查看hexo的版本 hexo init nodejs-hexo //创建nodejs-hexo 名字的本地文件 hexo init nodejs-hexo //创建博客 hexo init blog //初始化，生成文件夹为blog cd blog //进入blog文件夹 npm install //安装依赖库 hexo generate //生成一套静态网页 hexo server //运行测试,浏览器打开地址，http://localhost:4000/ hexo deploy //进行部署 hexo new "new article" //新建文章‘new article’ hexo new page "about" //新建页面 ‘about’ hexo n "我的博客"` == `hexo new` "我的博客" //新建文章 hexo g == hexo generate //生成` hexo s == hexo server //启动服务预览 hexo d == hexo deploy //部署

题目 现在你总共有 n 门课需要选，记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1] 给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？ 示例 1: 输入: 2, [[1,0]] 输出: true 解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。 示例 2: 输入: 2, [[1,0],[0,1]] 输出: false 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。 说明: 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。 你可以假定输入的先决条件中没有重复的边。 提示: 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。 拓扑排序也可以通过 BFS 完成。 代码 方法1：广度优先遍历 我们使用一个队列来进行广度优先搜索。初始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。 在广度优先搜索的每一步中，我们取出队首的节点 u： 我们将 u 放入答案中； 我们移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 11。如果某个相邻节点 v 的入度变为 0，那么我们就将 v 放入队列中。...

题目 一些恶魔抓住了公主（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....

题目 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。 思路 思路 状态定义： 设dp[i][j]为走到当前位置的最小路径和 递推公式： 只能向下或向右走，意味着当前格子只能由上边或者左边走过来 dp[i][j] = Min(dp[i-1][j],dp[i][j-1]) + grid[i][j] 初始化 第一行第n列和第一列第n行为均原数组值 边界条件 格子有边界，因此当i==0 或j==0时，i-1和j-1会越界 i = 0，j != 0时,dp[i][j] = dp[i][j-1]+grid[i][j] i !=0，j == 0时,dp[i][j] = dp[i-1][j]+grid[i][j] i !=0 && j != 0时,dp[i][j] = Min(dp[i-1][j],dp[i][j-1])+grid[i][j] i == 0 && j == 0时,dp[i][j]=grid[i][j] 返回值 dp最后一个元素值 代码 cpp代码 #include <stdio.h> #include <vector> class Solution { public: int minPathSum(std::vector<std::vector<int> >& grid) { if (grid....