Leetcode - 周赛445

一、3516. 找到最近的人

题目链接

纯模拟，代码如下：

class Solution {
    public int findClosest(int x, int y, int z) {
        int a = Math.abs(x-z);
        int b = Math.abs(y-z);
        return a == b ? 0 : a > b ? 2 : 1; 
    }
}

二、3517. 最小回文排列 I

题目链接

本题求字典序最小的回文字符串，由于回文串是对称的，所以只需要考虑前半段就行，统计所有字符的出现次数，将其全部除以2（如果它的模是奇数，说明它有一个需要放在中间位置，额外记录一下），然后依次遍历a->z，将字符填入到前半段回文串中就行。

代码如下：

class Solution {
    public String smallestPalindrome(String s) {
        int n = s.length();
        int[] cnt = new int[26];
        int idx = -1;// 记录奇数回文串中间的值
        for(char c : s.toCharArray()){
            cnt[c-'a']++;
        }
        for(int i = 0; i < 26; i++){
            if(cnt[i] % 2 == 1){
                idx = i;
            }
            cnt[i] /= 2;
        }
        char[] ans = new char[n];
        int j = 0;
        for(int i = 0; i < 26; i++){
            while(cnt[i]-- > 0){
                ans[j] = ans[n-1-j] = (char)(i + 'a');
                j++;
            }
        }
        if(idx != -1) ans[j] = (char)(idx + 'a');
        return new String(ans);
    }
}

三、3518. 最小回文排列 II

题目链接

与T2类似，只不过多了一个限制条件 k，可以使用试填法，枚举每一位可以选择的字符，计算如果当前选择字符 a，出现的所有排列 p，与 k 进行比较:

• p >= k，说明当前可以选择字符 a
• p < k，说明当前不能选择字符 a，继续枚举字符

本题的难点在于计算 $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$，不能先预处理 n! 再去计算，因为可能会出现越界，这里有两种做法：

• 根据选或不选，可以得到公式 $\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{m}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{m-1}\right)$，根据该公式去计算 $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$，由于是加法运算，不会溢出，如果 > k，可以直接返回 k.
• $\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\frac{n!}{m!(n-m)!}=\frac{n\ast (n-1)\ast ...\ast (n-m+1)}{1\ast 2\ast ...\ast m}$，可以分开计算 $n/1\ast (n-1)/2\ast (n-3)/3\ast ...$，这样也可以避免溢出。

代码如下：

class Solution {
    public String smallestPalindrome(String s, int k) {
        int[] cnt = new int[26];
        int n = s.length();
        for(int i = 0; i < n / 2; i++){
            cnt[s.charAt(i)-'a']++;
        }
        if(perm(n/2, k, cnt) < k) return "";
        char[] ans = new char[n];
        int size = n / 2;
        for(int i = 0; i < n / 2; i++){ // 枚举每一位
            for(int j = 0; j < 26; j++){ // 枚举选那个字符
                if(cnt[j] == 0) continue;
                cnt[j]--;
                long p = perm(size-1, k, cnt);
                if(p >= k){
                    ans[i] = ans[n-1-i] = (char)(j + 'a');
                    size--;
                    break;
                }
                k -= p;
                cnt[j]++;
            }
        }
        if(n % 2 == 1) ans[n/2] = s.charAt(n/2);
        return new String(ans);
    }
    // n!/(m!*(n-m)!)
    int comb(int n, int m, int k){
        m = Math.min(n-m, m);// 不能省略，因为有 k
        int res = 1;
        for(int i = 1; i <= m; i++){
            res = res * (n + 1 - i) / i;
            if(res >= k) return k;
        }
        return res;
    }
    // 计算当前有多少种排列组合
    long perm(int n, int k, int[] cnt){
        long res = 1;
        for(int m : cnt){
            if(m == 0) continue;
            res *= comb(n, m, k);
            if(res >= k) return res;
            n -= m;
        }
        return res;
    }
}

四、3519. 统计逐位非递减的整数

题目链接

本题就是数位DP，直接套用灵神模板，唯一的难点在于计算大数进制转换，在Java中可以使用BigInteger 类中自带的 toString(int radix) 方法，将十进制数转换成 radix 进制数。或者自己手写一个转换函数，代码如下：

//import java.math.BigInteger;
class Solution {
    public int countNumbers(String l, String r, int b) {
        //char[] low = new BigInteger(l).toString(b).toCharArray();
        //char[] high = new BigInteger(r).toString(b).toCharArray();
        char[] low = getRadix(l, b);
        char[] high = getRadix(r, b);
        memo = new int[high.length][b];
        for(int[] row : memo) Arrays.fill(row, -1);
        return dfs(0, 0, b-1, true, true, low, high);
    }
    int MOD = (int)1e9+7;
    int[][] memo;
    // 数位dp
    int dfs(int i, int j, int b, boolean isLow, boolean isHigh, char[] low, char[] high){
        if(i == high.length) return 1;
        if(!isLow && !isHigh && memo[i][j] != -1) return memo[i][j];
        int idx = high.length - low.length;
        int down = i >= idx && isLow ? low[i-idx] - '0' : 0;
        int up = isHigh ? high[i] - '0' : b;
        int res = 0;
        for(int d = Math.max(down, j); d <= up; d++){
            res = (res + dfs(i+1, d, b, isLow && d == down, isHigh && d == up, low, high)) % MOD;
        }
        if(!isLow && !isHigh) memo[i][j] = res;
        return res;
    }
    // 进制转换
    char[] getRadix(String s, int radix){
        StringBuilder res = new StringBuilder();
        while(s.length() > 0){
            StringBuilder tmp = new StringBuilder();
            int p = 0;
            for(char c : s.toCharArray()){
                int x = c - '0';
                int cur = 10 * p + x;
                int mul = cur / radix;
                if(mul > 0 || tmp.length() > 0){
                    tmp.append(mul);
                }
                p = cur % radix;
            }
            res.append(p);
            s = tmp.toString();
        }
        return res.reverse().toString().toCharArray();
    }
}