leetcode每日一题（20241207)(20241204补)

leetcode每日一题（20241206）和补一下（20241204）的这天的

（20241204): 2056. 棋盘上有效移动组合的数目:题目描述：

有一个 8 x 8 的棋盘，它包含 n 个棋子（棋子包括车，后和象三种）。给你一个长度为 n 的字符串数组 pieces ，其中 pieces[i] 表示第 i 个棋子的类型（车，后或象）。除此以外，还给你一个长度为 n 的二维整数数组 positions ，其中 positions[i] = [ri, ci] 表示第 i 个棋子现在在棋盘上的位置为 (ri, ci) ，棋盘下标从 1 开始。
每个棋子的移动中，首先选择移动的 方向 ，然后选择 移动的步数 ，同时你要确保移动过程中棋子不能移到棋盘以外的地方。棋子需按照以下规则移动：
车可以 水平或者竖直 从 (r, c) 沿着方向 (r+1, c)，(r-1, c)，(r, c+1) 或者 (r, c-1) 移动。
后可以 水平竖直或者斜对角 从 (r, c) 沿着方向 (r+1, c)，(r-1, c)，(r, c+1)，(r, c-1)，(r+1, c+1)，(r+1, c-1)，(r-1, c+1)，(r-1, c-1) 移动。
象可以 斜对角 从 (r, c) 沿着方向 (r+1, c+1)，(r+1, c-1)，(r-1, c+1)，(r-1, c-1) 移动。
你必须同时 移动 棋盘上的每一个棋子。移动组合 包含所有棋子的 移动 。每一秒，每个棋子都沿着它们选择的方向往前移动 一步 ，直到它们到达目标位置。所有棋子从时刻 0 开始移动。如果在某个时刻，两个或者更多棋子占据了同一个格子，那么这个移动组合 不有效 。
请你返回 有效 移动组合的数目。
注意：
初始时，不会有两个棋子 在 同一个位置 。
有可能在一个移动组合中，有棋子不移动。
如果两个棋子 直接相邻 且两个棋子下一秒要互相占据对方的位置，可以将它们在同一秒内 交换位置 。

这题逻辑就是先找出所有可能然后再深度遍历找出所有的符合条件的组合（比较难和麻烦要好好看代码我是看视频讲解和解析才弄出来了）

class Solution {int[][] rookDir={{1,0},{-1,0},{0,1},{0,-1}};int[][] bishopDir={{1,1},{1,-1},{-1,1},{-1,-1}};int[][] queenDir={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};List<int[]> path=new ArrayList<>(); //存储的一个组合里面前面合规的选择int len; //代表的是一共有几个人List<List<int[]>> list;public int countCombinations(String[] pieces, int[][] positions) {//找出他们所有能到达的点len=pieces.length;list=new ArrayList<>(len);for(int i=0;i<len;i++){list.add(genPoints(positions[i],pieces[i]));}return dfs(0);}public boolean isValid(int[] move1,int[] move2){int x1=move1[0];int y1=move1[1];int x2=move2[0];int y2=move2[1];for(int i=0;i<Math.max(move1[4],move2[4]);i++){if(i<move1[4]){x1+=move1[2];y1+=move1[3];}if(i<move2[4]){x2+=move2[2];y2+=move2[3];}if(x1==x2&&y1==y2){return false;}}return true;}public int dfs(int i){if(i==len){return 1;}int count=0;//先去看这次新加的和之前的有没有冲突for(int[] move:list.get(i)){boolean flag=true;for(int[] preMove:path){if(!isValid(move,preMove)){flag=false;break;}}if(flag){path.add(move);count+=dfs(i+1);path.remove(path.size()-1);}}return count;}public List<int[]> genPoints(int[] pos,String piece){int[][] dirAll;if(piece.equals("queen")){dirAll=queenDir;}else if(piece.equals("rook")){dirAll=rookDir;}else{dirAll=bishopDir;}int x=pos[0];int y=pos[1];List<int[]> list=new ArrayList<>();list.add(new int[]{x,y,0,0,0}); //代表不动的情况for(int[] dir:dirAll){int tempX=x+dir[0];int tempY=y+dir[1];int step=1;while(tempX>=1&&tempX<=8&&tempY>=1&&tempY<=8){list.add(new int[]{x,y,dir[0],dir[1],step});tempX+=dir[0];tempY+=dir[1];step++;}}return list;}
}

（20241207): 688. 骑士在棋盘上的概率:题目描述：

在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。
象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

在这里插入图片描述
这题还算简单，只不过会超时，加缓存那个想到了但是不知道该咋加：看第一版我的超时的版本：

class Solution {int[][] dir={{-2,1},{-1,2},{1,2},{2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};int step;int n;long count=0L;public double knightProbability(int n, int k, int row, int column) {step=k;this.n=n;dfs(row,column,0);return count/Math.pow(8,k);}public void dfs(int x,int y,int i){if(x<0||x>=n||y<0||y>=n){return ;}if(i==step){count++;return;}for(int[] move:dir){dfs(x+move[0],y+move[1],i+1);}}
}

看了解析加了缓存版本：

class Solution {int[][] dir={{-2,1},{-1,2},{1,2},{2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};int step;int n;double[][][] cache;public double knightProbability(int n, int k, int row, int column) {step=k;this.n=n;cache=new double[k+1][n][n];return dfs(row,column,0);}public double dfs(int x,int y,int i){if(x<0||x>=n||y<0||y>=n){return 0;}if(i==step){return 1;}if(cache[i][x][y]!=0){return cache[i][x][y];}double res=0;for(int[] move:dir){res+=dfs(x+move[0],y+move[1],i+1);}return cache[i][x][y]=res/8;}
}