欢迎大家加QQ群：623375442。感觉自己水平下降严重啊。这周不是挺难的，AK的人也好多啊
100633. Find Closest Person
给你三个整数 x、y 和 z，表示数轴上三个人的位置：
- x 是第 1 个人的位置。
- y 是第 2 个人的位置。
- z 是第 3 个人的位置，第 3 个人 不会移动 。
第 1 个人和第 2 个人以 相同 的速度向第 3 个人移动。
判断谁会 先 到达第 3 个人的位置：
- 如果第 1 个人先到达，返回 1 。
- 如果第 2 个人先到达，返回 2 。
- 如果两个人同时到达，返回 0 。
根据上述规则返回结果。
测试样例：
输入：x = 2, y = 7, z = 4
输出：1
解释：
- 第 1 个人在位置 2，到达第 3 个人（位置 4）需要 2 步。
- 第 2 个人在位置 7，到达第 3 个人需要 3 步。
解答：使用 Math.abs 计算第 1 个人和第 2 个人与第 3 个人之间的距离。
根据两者的距离进行比较：
- 若第 1 个人的距离更小，则返回 1；
- 若第 2 个人的距离更小，则返回 2；
- 若两者距离相等，则返回 0。
class Solution {
public int findClosest(int x, int y, int z) {
// 计算第1个人到第3个人的距离
int d1 = Math.abs(x - z);
// 计算第2个人到第3个人的距离
int d2 = Math.abs(y - z);
// 如果第1个人的距离更小，返回1
if (d1 < d2) {
return 1;
// 如果第2个人的距离更小，返回2
} else if (d1 > d2) {
return 2;
// 如果两者的距离相等，返回0
else {
return 0;
}
}
}
100618. Smallest Palindromic Rearrangement I
给你一个 回文 字符串 s。
返回 s 的按字典序排列的 最小 回文排列。
如果一个字符串从前往后和从后往前读都相同，那么这个字符串是一个 回文 字符串。
排列 是字符串中所有字符的重排。
如果字符串 a 按字典序小于字符串 b，则表示在第一个不同的位置，a 中的字符比 b 中的对应字符在字母表中更靠前。如果在前 min(a.length, b.length) 个字符中没有区别，则较短的字符串按字典序更小。
测试样例：
输入：s = "babab"
输出："abbba"
解释: 通过重排 "babab" → "abbba"，可以得到按字典序最小的回文。
解答：
- 字符统计：统计字符串中每个字符出现的次数。
- 确定中间字符：遍历字母表，对于出现次数为奇数的字符，则该字符将作为回文的中间字符（如果有多个出现奇数的字符，后面覆盖赋值，但因为输入一定能构成回文所以只有一个中间字符）。
- 构建半字符串：将每个字符出现次数的一半按照字典序依次加入到半字符串中。
- 生成完整回文：将构建的半字符串、（若存在）中间字符、以及半字符串的逆序拼接在一起即构成回文字符串，并且为字典序最小。
class Solution {
public String smallestPalindrome(String s) {
// 统计每个字符出现的次数
int[] count = new int[26];
for (int i = 0; i < s.length(); ++i) {
count[s.charAt(i) - 'a'] += 1;
}
int[] halfFreq = new int[26];
char mid = 0;
// 对于每个字符，如果它的出现次数是奇数，记录它作为中间字符
for (int i = 0; i < 26; i++) {
if (count[i] % 2 != 0) {
mid = (char) (i + 'a');
}
halfFreq[i] = count[i] / 2;
}
// 构建字典序最小的半回文字符串
StringBuilder permutation = new StringBuilder();
for (int i = 0; i < 26; ++i) {
char c = (char)(i + 'a');
for (int j = 0; j < halfFreq[i]; ++j) {
permutation.append(c);
}
}
// 构造完整回文：半回文 + 中间字符（如果有） + 半回文的逆序
String halfStr = permutation.toString();
StringBuilder res = new StringBuilder();
res.append(halfStr);
if (mid != 0) res.append(mid);
res.append(new StringBuilder(halfStr).reverse());
return res.toString();
}
}100619. Smallest Palindromic Rearrangement II
给你一个 回文 字符串 s 和一个整数 k。
返回 s 的按字典序排列的 第 k 小 回文排列。如果不存在 k 个不同的回文排列，则返回空字符串。
注意： 产生相同回文字符串的不同重排视为相同，仅计为一次。
如果一个字符串从前往后和从后往前读都相同，那么这个字符串是一个 回文 字符串。
排列 是字符串中所有字符的重排。
如果字符串 a 按字典序小于字符串 b，则表示在第一个不同的位置，a 中的字符比 b 中的对应字符在字母表中更靠前。如果在前 min(a.length, b.length) 个字符中没有区别，则较短的字符串按字典序更小。
测试样例：
输入：s = "abba", k = 2
输出："baab"
解释: "abba" 的两个不同的回文排列是 "abba" 和 "baab"。按字典序，"abba" 位于 "baab" 之前。由于 k = 2，输出为 "baab"。
解答：
- 字符统计和准备：统计字符串中每个字符出现的次数，确定半边回文中每个字符的数量以及中间字符（若存在）。
- 组合数预处理：利用静态代码块预先构造组合数（类似 Pascal 三角形）来帮助后续计算排列的总数。
- 计算回文排列总数：使用组合数方法计算当前半边字符构成的排列数。
- 利用 DFS 进行构造：
- 从字典序最小的字符开始遍历。
- 对于每个可能选择，计算选定该字符后剩余的排列方式数。
- 如果剩余排列数大于或等于 k，则确认选择该字符；否则从 k 中扣除该部分排列数，继续尝试下一个字符。
- 拼接完整回文：构造半边字符串后，同样构造完整回文：半边字符串 + 中间字符（如果有）+ 半边字符串的逆序。
class Solution {
private static List<List<Integer>> combine = new ArrayList<>();
static {
combine.add(Arrays.asList(0));
for (int i = 1; i <= 5000; ++i) {
List<Integer> cur = new ArrayList<>(), last = combine.get(combine.size() - 1);
for (int j = 0; j <= i; ++j) {
if (j == 0 || j == i) {
cur.add(1);
} else if (j >= last.size()) {
break;
} else {
int add = last.get(j - 1) + last.get(j);
if (add > 1_000_000) {
break;
}
cur.add(add);
}
}
combine.add(cur);
}
}
public String smallestPalindrome(String s, int k) {
// 统计每个字符出现的次数
int[] count = new int[26];
for (int i = 0; i < s.length(); ++i) {
count[s.charAt(i) - 'a'] += 1;
}
int[] halfFreq = new int[26];
char mid = 0;
int totalHalf = 0;
for (int i = 0; i < 26; i++) {
if (count[i] % 2 != 0) {
mid = (char) (i + 'a');
}
halfFreq[i] = count[i] / 2;
totalHalf += halfFreq[i];
}
// 计算所有可能的回文排列数量
long totalWays = countPermutation(halfFreq, totalHalf, k);
if (totalWays < k) {
return "";
}
// 构建第k小回文排列
StringBuilder permutation = new StringBuilder();
for (int pos = 0; pos < totalHalf; pos++) {
for (int i = 0; i < 26; i++) {
if (halfFreq[i] > 0) {
halfFreq[i]--;
long ways = countPermutation(halfFreq, totalHalf - pos - 1, k);
if (ways >= k) {
permutation.append((char) ('a' + i));
break;
} else {
k -= (int) ways;
halfFreq[i]++;
}
}
}
}
// 构造回文：半回文 + 中间字符（如果有） + 半回文的逆序
String halfStr = permutation.toString();
StringBuilder res = new StringBuilder();
res.append(halfStr);
if (mid != 0) res.append(mid);
res.append(new StringBuilder(halfStr).reverse());
return res.toString();
}
private long countPermutation(int[] freq, int total, int k) {
long ways = 1;
int remaining = total;
for (int f : freq) {
if (f > 0) {
long comb = combineCount(remaining, f, k);
if (comb > k || ways * comb > k) {
ways = k + 1;
} else {
ways = ways * comb;
}
remaining -= f;
}
}
return ways;
}
private int combineCount(int n, int r, int k) {
if (r > n) return 0;
int min = Math.min(r, n - r);
if (min >= combine.get(n).size()) {
return k + 1;
} else {
return combine.get(n).get(min);
}
}
}100616. Count Numbers with Non-Decreasing Digits
给你两个以字符串形式表示的整数 l 和 r，以及一个整数 b。返回在区间 [l, r] （闭区间）内，以 b 进制表示时，其每一位数字为 非递减 顺序的整数个数。
整数逐位 非递减 需要满足：当按从左到右（从最高有效位到最低有效位）读取时，每一位数字都大于或等于前一位数字。
由于答案可能非常大，请返回对 10^9 + 7 取余 后的结果。
测试样例：
输入：l = "23", r = "28", b = 8
输出：3
解释: 从 23 到 28 的数字在 8 进制下为：27、30、31、32、33 和 34。其中，27、33 和 34 的数字是非递减的。因此，输出为 3。
解答：
- 数字转换：将大整数转换为指定进制下的数字数组。
- 数字动态规划（Digit DP）：
- 使用 DFS 模板，对每一个位置进行递归决策。
- 状态包含当前位 pos、是否受到上界限制 isBound、是否已经开始构造数字 isStart，以及上一位选的数字 last（用于保证后续位不小于前一位）。
- 当达到末尾时返回 1，表示构造了一个有效数字。
- 使用记忆化数组 mem 缓存中间状态以降低复杂度。
- 范围计数：分别计算 [0, r] 与 [0, l-1] 的结果，相减得到 [l, r] 的计数，注意取模运算。
import java.math.BigInteger;
class Solution {
private static final int mod = 1_000_000_007; // 定义模数
// 主函数：计算 [l, r] 范围内非递减数字个数（以 b 进制表示）
public int countNumbers(String l, String r, int b) {
// 将字符串 l 转换为大整数后减 1，方便计算区间差
BigInteger lb = new BigInteger(l).subtract(BigInteger.ONE);
BigInteger rb = new BigInteger(r);
// count(rb, b) 表示 [0, r] 中满足条件的数字个数
return (count(rb, b) - count(lb, b) + mod) % mod;
}
// 利用 DFS + 记忆化搜索计算 [0, num] 内符合条件的数字个数
private int count(BigInteger num, int b) {
// 将数字转换为 b 进制下的各位数组
int[] digits = convertToBase(num, b);
int len = digits.length;
// 四维缓存：位置、是否受限、是否开始、上一位数字（最后数字）
Integer[][][][] mem = new Integer[len + 1][2][2][b + 1];
// 开始递归搜索，从第 0 位开始，初始状态为受限且未开始构造数字，上一位设为 0
return dfs(0, 1, 0, 0, digits, b, mem);
}
/**
* DFS递归函数：
* @param pos 当前处理的位置
* @param isBound 当前位是否受到上界限制（1 表示受限）
* @param isStart 是否已经开始构造数字（1 表示已经开始放数字）
* @param last 当前已经构造的数字中最后一位的值，用于保证非递减
* @param digits 数字对应的 b 进制数组
* @param base 当前进制
* @param mem 记忆化缓存
* @return 当前状态下合法数字的个数
*/
private int dfs(int pos, int isBound, int isStart, int last, int[] digits, int base, Integer[][][][] mem) {
if (pos == digits.length) {
// 到达末尾，则找到一种符合条件的数字构造方式
return 1;
} else if (mem[pos][isBound][isStart][last] == null) {
long res = 0;
// 当前位的上界值：若受到限制则为 digits[pos]，否则可取到最大值 base-1
int ed = isBound == 1 ? digits[pos] : (base - 1);
if (isStart == 0) {
// 未开始数字，允许前导 0（不开始构造数字）
res = (res + dfs(pos + 1, (isBound == 1 && 0 == ed) ? 1 : 0, 0, 0, digits, base, mem)) % mod;
// 或者从当前位开始选择从 1 到 ed 的数字
for (int d = 1; d <= ed; d++) {
res = (res + dfs(pos + 1, (isBound == 1 && d == ed) ? 1 : 0, 1, d, digits, base, mem)) % mod;
}
} else {
// 已经开始构造数字，此时选择的数字必须不小于 last 保证非递减
for (int d = last; d <= ed; d++) {
res = (res + dfs(pos + 1, (isBound == 1 && d == ed) ? 1 : 0, 1, d, digits, base, mem)) % mod;
}
}
mem[pos][isBound][isStart][last] = (int) res;
}
return mem[pos][isBound][isStart][last];
}
// 将大整数转换为 b 进制下各位的数组表示
private int[] convertToBase(BigInteger num, int b) {
List<Integer> res = new ArrayList<>();
if (num.equals(BigInteger.ZERO)) {
res.add(0);
} else {
BigInteger base = BigInteger.valueOf(b);
// 依次求余得到各位数字
while (num.compareTo(BigInteger.ZERO) > 0) {
BigInteger[] divRem = num.divideAndRemainder(base);
res.add(divRem[1].intValue());
num = divRem[0];
}
}
// 反转顺序得到从最高位到最低位的数组
int[] digits = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
digits[i] = res.get(res.size() - i - 1);
}
return digits;
}
}