目录
一，3340. 检查平衡字符串
二，3341. 到达最后一个房间的最少时间 I
三，3342. 到达最后一个房间的最少时间 II
四，3343. 统计平衡排列的数目
一，3340. 检查平衡字符串
本题直接暴力，定义一个变量 s，如果是偶数下标就 + ，反之则 - 。最后判断 s == 0。
代码如下：
class Solution {public boolean isBalanced(String num) {char[] ch = num.toCharArray();int s = 0;for(int i=0; i<ch.length; i++){if(i%2==0){s += ch[i]-'0';}else{s -= ch[i]-'0';}}return s == 0;}
}二，3341. 到达最后一个房间的最少时间 I
本题直接使用dijkstra算法（不知道原理的可以看这篇博客Leetcode - 128双周赛），唯一需要注意的点是如何计算它到一个地点所需要的时间，题目要求如果要从（i，j）移动到（x，y），那么移动前即在（i，j）时的时间一定要大于等于 moveTime[x][y]
代码如下：
class Solution {int[][] dirct = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};public int minTimeToReach(int[][] move) {PriorityQueue<int[]> que = new PriorityQueue<>((x, y)->x[2]-y[2]);que.offer(new int[]{0, 0, 0});int n = move.length, m = move[0].length;int[][] vis = new int[n][m];for(int i=0; i<n; i++) Arrays.fill(vis[i], Integer.MAX_VALUE);vis[0][0] = 0;while(!que.isEmpty()){int[] t = que.poll();if(t[2] > vis[t[0]][t[1]]) continue;for(int[] d : dirct){int x = t[0] + d[0], y = t[1] + d[1];int time = t[2];if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]>Math.max(time, move[x][y])+1){vis[x][y] = Math.max(time, move[x][y])+1;que.offer(new int[]{x, y, vis[x][y]});}}}return vis[n-1][m-1];}}三，3342. 到达最后一个房间的最少时间 II
本题和T2一样，不过多了一个条件，每次移动花费的时间是1，2，1，2 反复的，这里有两种解决办法：
- 可以直接在存储数据时添加一个变量，专门用来记录移动到当前位置所需的移动时间
- 其实可以使用坐标来解决，从（x，y）到它相邻的房间，要么 x +1/-1，要么 y+1/-1，也就是说不管怎么移动，它的坐标 x+y 的奇偶性一定会发生变化，我们可以利用这点来计算移动时间
代码如下：
class Solution {int[][] dirct = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};public int minTimeToReach(int[][] move) {PriorityQueue<int[]> que = new PriorityQueue<>((x, y)->x[2]-y[2]);que.add(new int[]{0, 0, 0});int n = move.length, m = move[0].length;int[][] vis = new int[n][m];for(int i=0; i<n; i++) Arrays.fill(vis[i], Integer.MAX_VALUE);vis[0][0] = 0;while(!que.isEmpty()){int[] t = que.poll();if(t[2] > vis[t[0]][t[1]]) continue;for(int[] d : dirct){int x = t[0] + d[0], y = t[1] + d[1];int add = (t[0] + t[1]) % 2 + 1;if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]>Math.max(t[2], move[x][y])+add){vis[x][y] = Math.max(t[2], move[x][y])+add;que.add(new int[]{x, y, vis[x][y]});}}}return vis[n-1][m-1];}
}四，3343. 统计平衡排列的数目
本题是一道排列组合题，可以先将其进行分组，然后再排列，假设num的长度为n，题目要求奇偶位置的数字之和相等，也就是说可以通过该条件得到两个集合A，B，对于A集合它会有 m! 种排列（可能会有重复的），如果一个数字出现 k 次，需要将 m! / k!，本题只会出现0~9，所以会有 m! / k0!...k9!；同理，B集合会有 (n - m)! / k0!...k9! 种排列，它们一共会有 m! * (n-m)! / k0!...k9! (cnt[0]-k0)!...(cnt[9]-k9)! 种排列。
但是这只是其中一种分组，我们还需要计算一共能分成几种A，B集合，这里有点类似于两数之和，需要计算构成长度为 n / 2，总和为 total / 2 的集合有多少种可能，这里可以使用 dfs 计算，dfs(x，i，j)：数字范围在[0，x]时，构成长度为 i，总和为 j 的集合的所有可能组合。
代码如下：
class Solution {private static final int MOD = 1_000_000_007;private static final int MX = 41;private static final long[] f = new long[MX];private static final long[] inv_f = new long[MX];// (a/b)%MOD = a * b ^ (MOD-2) % MOD // 费马小定理！// 1 / b % MOD = b ^ (MOD-2) % MOD 注：MOD必须为质数// 1 / (a*b*c) % p = pow(a*b*c, p - 2) % p// 1 / (a*b) % p = pow(a*b, p-2) % p// 1 / (a*b) % p = 1 / (a*b*c) * c % p// 得到：inv_f[i-1] = inv_f[i] * i % pstatic{f[0] = 1;for(int i=1; i<MX; i++){f[i] = f[i-1] * i % MOD;}inv_f[MX-1] = pow(f[MX-1], MOD-2);for(int i=MX-1; i>0; i--){inv_f[i-1] = inv_f[i] * i % MOD;}}public int countBalancedPermutations(String num) {int n = num.length();int[] cnt = new int[10];int tar = 0;for(char c : num.toCharArray()){cnt[c-'0']++;tar += (int)(c-'0');}if(tar%2 == 1) return 0;for(int i=1; i<10; i++){cnt[i] += cnt[i-1];}int n1 = n / 2;memo = new int[10][n1 + 1][tar / 2 + 1];for (int[][] mat : memo) {for (int[] row : mat) {Arrays.fill(row, -1);}}return (int) (f[n1] * f[n - n1] % MOD * dfs(9, n1, tar / 2, cnt) % MOD);}int[][][] memo;int dfs(int x, int i, int j, int[] cnt){if(x < 0) return j==0?1:0;if(memo[x][i][j] != -1) return memo[x][i][j];long res = 0;int c = cnt[x] - (x > 0 ? cnt[x-1] : 0);int l = cnt[x] - i;for(int y=Math.max(c-l, 0); y<=Math.min(c, i) && y*x <= j; y++){int r = dfs(x-1, i-y, j-y*x, cnt);res = (res + r * inv_f[y] % MOD * inv_f[c-y])%MOD;}return memo[x][i][j] = (int)res;}private static long pow(long x, int n) {long res = 1;for (; n > 0; n /= 2) {if (n % 2 > 0) {res = res * x % MOD;}x = x * x % MOD;}return res;}
}