LeetCode刷题 day28

目录1.穿越网格图的安全路径2. 格雷编码1.穿越网格图的安全路径给你一个 m x n 的二进制矩形 grid 和一个整数 health 表示你的健康值。你开始于矩形的左上角 (0, 0) 你的目标是矩形的右下角 (m - 1, n - 1) 。你可以在矩形中往上下左右相邻格子移动但前提是你的健康值始终是 正数 。对于格子 (i, j) 如果 grid[i][j] 1 那么这个格子视为 不安全 的会使你的健康值减少 1 。如果你可以到达最终的格子请你返回 true 否则返回 false 。注意 当你在最终格子的时候你的健康值也必须为正数。示例 1输入grid [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health 1输出true解释沿着下图中灰色格子走可以安全到达最终的格子。示例 2输入grid [[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health 3输出false解释健康值最少为 4 才能安全到达最后的格子。示例 3输入grid [[1,1,1],[1,0,1],[1,1,1]], health 5输出true解释沿着下图中灰色格子走可以安全到达最终的格子。任何不经过格子 (1, 1) 的路径都是不安全的因为你的健康值到达最终格子时都会小于等于 0 。思路广度优先搜索在搜索时遇到单元格为0的格子放入队首遇单元格为1的格子放队尾。并且在放入队列之前先判断若到当前格子路径的消费已经超过health则剪枝不放入队列中否则若到当前格子的消费小于目前的消费则更新格子的路径消费并放入队列classSolution{privatestaticint[][]DIRS{{0,1},{0,-1},{1,0},{-1,0}};publicbooleanfindSafeWalk(ListListIntegergrid,inthealth){//宽度优先遍历intngrid.size(),mgrid.get(0).size();int[][]disnewint[n][m];for(int[]row:dis){Arrays.fill(row,Integer.MAX_VALUE);}//存放下标Dequeint[]qnewArrayDeque();q.offerFirst(newint[]{0,0});dis[0][0]grid.get(0).get(0);//当前格子已计算计算新的格子while(!q.isEmpty()){int[]curq.pollFirst();intcxcur[0],cycur[1];//只要到终点肯定是最短距离//每次添加时都是将小的放前面大的放后面因此双端队列整体是升序的if(cxn-1cym-1){returntrue;}for(int[]dir:DIRS){intxcxdir[0],ycydir[1];if(x0||xn||y0||ym){continue;}intcostdis[cx][cy]grid.get(x).get(y);if(costhealth){continue;}if(costdis[x][y]){dis[x][y]cost;if(grid.get(x).get(y)0){q.offerFirst(newint[]{x,y});}else{q.offerLast(newint[]{x,y});}}}}returnfalse;}}时间复杂度O ( m ∗ n ) O(m*n)O(m∗n)m,n分别是grid的行和列空间复杂度O ( m ∗ n ) O(m*n)O(m∗n)2. 格雷编码n 位格雷码序列 是一个由 2n 个整数组成的序列其中每个整数都在范围 [0, 2n - 1] 内含 0 和 2n - 1第一个整数是 0一个整数在序列中出现 不超过一次每对 相邻 整数的二进制表示 恰好一位不同 且第一个 和 最后一个 整数的二进制表示 恰好一位不同给你一个整数 n 返回任一有效的 n 位格雷码序列 。示例 1输入n 2输出[0,1,3,2]解释[0,1,3,2] 的二进制表示是 [00,01,11,10] 。00 和 01 有一位不同01 和 11 有一位不同11 和 10 有一位不同10 和 00 有一位不同[0,2,3,1] 也是一个有效的格雷码序列其二进制表示是 [00,10,11,01] 。00 和 10 有一位不同10 和 11 有一位不同11 和 01 有一位不同01 和 00 有一位不同示例 2输入n 1输出[0,1]思路# 以n2为例假设已知2位格雷码序列求3位格雷码序列 #00-01-11-10# 先首尾补零序列仍不变 #000-001-011-010# 然后在首位补1#100-101-111-110# 这两个子序列的1的个数关系如下 #000-001-011-010#^|#|V#100-101-111-110# 因此只需保持n-1位格雷码序列不变将原序列首位补1并翻转即可得到n位格雷码序列classSolution{publicListIntegergrayCode(intn){ListIntegeransnewArrayList(1n);ans.add(0);for(inti1;in;i){intOr1(i-1);intmans.size();for(intjm-1;j0;j--){ans.add(ans.get(j)|Or);}}returnans;}}时间复杂度O ( 2 n ) O(2^n)O(2n)空间复杂度O ( 1 ) O(1)O(1)最终答案所需空间不考虑