目录
- 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(List<List<Integer>>grid,inthealth){//宽度优先遍历intn=grid.size(),m=grid.get(0).size();int[][]dis=newint[n][m];for(int[]row:dis){Arrays.fill(row,Integer.MAX_VALUE);}//存放下标Deque<int[]>q=newArrayDeque<>();q.offerFirst(newint[]{0,0});dis[0][0]=grid.get(0).get(0);//当前格子已计算，计算新的格子while(!q.isEmpty()){int[]cur=q.pollFirst();intcx=cur[0],cy=cur[1];//只要到终点，肯定是最短距离//每次添加时都是将小的放前面，大的放后面，因此双端队列整体是升序的if(cx==n-1&&cy==m-1){returntrue;}for(int[]dir:DIRS){intx=cx+dir[0],y=cy+dir[1];if(x<0||x==n||y<0||y==m){continue;}intcost=dis[cx][cy]+grid.get(x).get(y);if(cost>=health){continue;}if(cost<dis[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]
思路
# 以n=2为例，假设已知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{publicList<Integer>grayCode(intn){List<Integer>ans=newArrayList<>(1<<n);ans.add(0);for(inti=1;i<=n;i++){intOr=1<<(i-1);intm=ans.size();for(intj=m-1;j>=0;j--){ans.add(ans.get(j)|Or);}}returnans;}}时间复杂度：O ( 2 n ) O(2^n)O(2n)
空间复杂度：O ( 1 ) O(1)O(1)最终答案所需空间不考虑
