Leetcode - 周赛445

一、3516. 找到最近的人

题目链接

纯模拟，代码如下：

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

复制代码

二、3517. 最小回文排列 I

题目链接

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

1. class Solution {
2.     public String smallestPalindrome(String s) {
3.         int n = s.length();
4.         int[] cnt = new int[26];
5.         int idx = -1;// 记录奇数回文串中间的值
6.         for(char c : s.toCharArray()){
7.             cnt[c-'a']++;
8.         }
9.         for(int i = 0; i < 26; i++){
10.             if(cnt[i] % 2 == 1){
11.                 idx = i;
12.             }
13.             cnt[i] /= 2;
14.         }
15.         char[] ans = new char[n];
16.         int j = 0;
17.         for(int i = 0; i < 26; i++){
18.             while(cnt[i]-- > 0){
19.                 ans[j] = ans[n-1-j] = (char)(i + 'a');
20.                 j++;
21.             }
22.         }
23.         if(idx != -1) ans[j] = (char)(idx + 'a');
24.         return new String(ans);
25.     }
26. }

复制代码

三、3518. 最小回文排列 II

题目链接

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

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

本题的难点在于盘算                                    (                                   n                            m                                  )                              \binom{n}{m}                  (mn​)，不能先预处理 n! 再去盘算，因为可能会出现越界，这里有两种做法：

• 根据选或不选，可以得到公式                                                    (                                           n                                  m                                          )                                      =                                       (                                                        n                                     −                                     1                                              m                                          )                                      +                                       (                                                        n                                     −                                     1                                                           m                                     −                                     1                                                      )                                            \binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}                     (mn​)=(mn−1​)+(m−1n−1​)，根据该公式去盘算                                         (                                       n                               m                                      )                                  \binom{n}{m}                     (mn​)，由于是加法运算，不会溢出，如果 > k，可以直接返回 k.
  
•                                                    (                                           n                                  m                                          )                                      =                                                   n                                  !                                                      m                                  !                                  (                                  n                                  −                                  m                                  )                                  !                                                 =                                                   n                                  ∗                                  (                                  n                                  −                                  1                                  )                                  ∗                                  .                                  .                                  .                                  ∗                                  (                                  n                                  −                                  m                                  +                                  1                                  )                                                      1                                  ∗                                  2                                  ∗                                  .                                  .                                  .                                  ∗                                  m                                                       \binom{n}{m} = \frac{n!}{m!(n-m)!}= \frac{n*(n-1)*...*(n-m+1)}{1*2*...*m}                     (mn​)=m!(n−m)!n!​=1∗2∗...∗mn∗(n−1)∗...∗(n−m+1)​，可以分开盘算                                         n                            /                            1                            ∗                            (                            n                            −                            1                            )                            /                            2                            ∗                            (                            n                            −                            3                            )                            /                            3                            ∗                            .                            .                            .                                  n/1*(n-1)/2*(n-3)/3*...                     n/1∗(n−1)/2∗(n−3)/3∗...，如许也可以避免溢出。
  

代码如下：

1. class Solution {
2.     public String smallestPalindrome(String s, int k) {
3.         int[] cnt = new int[26];
4.         int n = s.length();
5.         for(int i = 0; i < n / 2; i++){
6.             cnt[s.charAt(i)-'a']++;
7.         }
8.         if(perm(n/2, k, cnt) < k) return "";
9.         char[] ans = new char[n];
10.         int size = n / 2;
11.         for(int i = 0; i < n / 2; i++){ // 枚举每一位
12.             for(int j = 0; j < 26; j++){ // 枚举选那个字符
13.                 if(cnt[j] == 0) continue;
14.                 cnt[j]--;
15.                 long p = perm(size-1, k, cnt);
16.                 if(p >= k){
17.                     ans[i] = ans[n-1-i] = (char)(j + 'a');
18.                     size--;
19.                     break;
20.                 }
21.                 k -= p;
22.                 cnt[j]++;
23.             }
24.         }
25.         if(n % 2 == 1) ans[n/2] = s.charAt(n/2);
26.         return new String(ans);
27.     }
28.     // n!/(m!*(n-m)!)
29.     int comb(int n, int m, int k){
30.         m = Math.min(n-m, m);// 不能省略，因为有 k
31.         int res = 1;
32.         for(int i = 1; i <= m; i++){
33.             res = res * (n + 1 - i) / i;
34.             if(res >= k) return k;
35.         }
36.         return res;
37.     }
38.     // 计算当前有多少种排列组合
39.     long perm(int n, int k, int[] cnt){
40.         long res = 1;
41.         for(int m : cnt){
42.             if(m == 0) continue;
43.             res *= comb(n, m, k);
44.             if(res >= k) return res;
45.             n -= m;
46.         }
47.         return res;
48.     }
49. }

复制代码

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

题目链接

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

1. //import java.math.BigInteger;
2. class Solution {
3.     public int countNumbers(String l, String r, int b) {
4.         //char[] low = new BigInteger(l).toString(b).toCharArray();
5.         //char[] high = new BigInteger(r).toString(b).toCharArray();
6.         char[] low = getRadix(l, b);
7.         char[] high = getRadix(r, b);
8.         memo = new int[high.length][b];
9.         for(int[] row : memo) Arrays.fill(row, -1);
10.         return dfs(0, 0, b-1, true, true, low, high);
11.     }
12.     int MOD = (int)1e9+7;
13.     int[][] memo;
14.     // 数位dp
15.     int dfs(int i, int j, int b, boolean isLow, boolean isHigh, char[] low, char[] high){
16.         if(i == high.length) return 1;
17.         if(!isLow && !isHigh && memo[i][j] != -1) return memo[i][j];
18.         int idx = high.length - low.length;
19.         int down = i >= idx && isLow ? low[i-idx] - '0' : 0;
20.         int up = isHigh ? high[i] - '0' : b;
21.         int res = 0;
22.         for(int d = Math.max(down, j); d <= up; d++){
23.             res = (res + dfs(i+1, d, b, isLow && d == down, isHigh && d == up, low, high)) % MOD;
24.         }
25.         if(!isLow && !isHigh) memo[i][j] = res;
26.         return res;
27.     }
28.     // 进制转换
29.     char[] getRadix(String s, int radix){
30.         StringBuilder res = new StringBuilder();
31.         while(s.length() > 0){
32.             StringBuilder tmp = new StringBuilder();
33.             int p = 0;
34.             for(char c : s.toCharArray()){
35.                 int x = c - '0';
36.                 int cur = 10 * p + x;
37.                 int mul = cur / radix;
38.                 if(mul > 0 || tmp.length() > 0){
39.                     tmp.append(mul);
40.                 }
41.                 p = cur % radix;
42.             }
43.             res.append(p);
44.             s = tmp.toString();
45.         }
46.         return res.reverse().toString().toCharArray();
47.     }
48. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。