Leetcode - 周赛422

目录

一，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 反复的，这里有两种解决办法：

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 % p
    static{
        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;
    }
}