20250810周赛记录
LeetCode 20250810周赛记录
Section titled “LeetCode 20250810周赛记录”题目给出两个数组 value 和 limit，需要按照特定规则激活元素以获得最大总和。
激活规则：
- 激活元素i的条件：当前活跃元素数量 < limit[i]
- 激活后果：活跃元素数量+1，同时所有满足 limit[j] ≤ 当前活跃数量 的元素j变为非活跃
- 目标：最大化所有激活过的元素的value之和
关键观察1： 一个元素一旦被激活，就会永久贡献其value值到总和中，无论它后来是否变为非活跃状态。
关键观察2： 激活顺序至关重要。如果先激活limit较大的元素，可能导致活跃数量增长过快，使得limit较小的元素永远无法被激活。
排序规则：
- 按照limit从小到大排序
- 对于相同limit的元素，按照value从大到小排序
为什么这样排序？
- limit小的元素在后期很难被激活（因为活跃数量会越来越大），所以要趁早激活
- 相同limit时，优先选择价值更高的元素
- 将所有元素按(limit, -value)排序
- 维护当前活跃元素数量，按排序后的顺序尝试激活：
- 如果当前活跃数量 < limit[i]，则激活元素i
- 将value[i]加入总和
- 活跃数量+1
- 移除所有limit ≤ 当前活跃数量的元素，更新活跃数量
class Solution { public long maxTotal(int[] value, int[] limit) { int n = value.length; Pair[] pairs = new Pair[n];
// 构建(value, limit)对 for(int i = 0; i < n; i++){ pairs[i] = new Pair(value[i], limit[i]); }
// 按limit升序，相同limit按value降序排序 Arrays.sort(pairs, new Comparator<Pair>(){ public int compare(Pair o1, Pair o2){ return o1.limit == o2.limit ? o2.value - o1.value : o1.limit - o2.limit; } });
long res = 0; int activeCount = 0;
// 使用优先队列维护已激活的元素 PriorityQueue<Pair> activePQ = new PriorityQueue<Pair>(new Comparator<Pair>(){ public int compare(Pair o1, Pair o2){ return o1.limit - o2.limit; } });
for(int i = 0; i < n; i++){ Pair current = pairs[i];
if(current.limit > activeCount){ // 可以激活当前元素 res += current.value; activePQ.add(current); activeCount++;
// 移除所有limit <= activeCount的已激活元素 while(!activePQ.isEmpty() && activePQ.peek().limit <= activeCount){ activePQ.poll(); activeCount--; }
// 跳过所有limit <= activeCount的未激活元素 while((i+1) < n && pairs[i+1].limit <= activeCount){ i++; } } } return res; }
class Pair{ int value; int limit; public Pair(int value, int limit){ this.value = value; this.limit = limit; } }}特殊回文数必须满足：
- 是回文数
- 数字k恰好出现k次（例如数字3恰好出现3次）
关键观察：
- 每个特殊回文数最多包含一个奇数数字作为中间数字
- 可能的数字组合有限：从{1,2,3,4,5,6,7,8,9}中选择，最多96种组合
- 可以预处理所有可能的特殊回文数，然后二分查找
为什么暴力枚举可行：时间复杂度详细分析
Section titled “为什么暴力枚举可行：时间复杂度详细分析”这道题的关键在于理解为什么暴力枚举是可行的。让我们详细分析时间复杂度：
1. 数字组合的数量限制
Section titled “1. 数字组合的数量限制”可选数字集合： {1, 2, 3, 4, 5, 6, 7, 8, 9}
组合限制：
- 最多选择一个奇数数字：{1, 3, 5, 7, 9} 中最多选1个，共6种选择（包括不选）
- 偶数数字可以任意组合：{2, 4, 6, 8} 共4个，每个可选可不选，共2^4 = 16种选择
- 总组合数：6 × 16 = 96种
2. 排列生成的复杂度
Section titled “2. 排列生成的复杂度”对于每种数字组合，需要生成左半部分的所有排列：
最坏情况分析：
- 选择所有偶数{2,4,6,8}和一个奇数（如9）
- 左半部分包含：1个2，2个4，3个6，4个8，4个9 = 总共14个数字
- 但由于回文数长度限制≤16，实际很少达到这种情况
实际情况：
- 大部分组合的左半部分长度在3-8之间
- 平均排列数最差为8! < 10^6 （1 2 4 8 一定可以生成16以内任何的数字）
3. 具体时间复杂度计算
Section titled “3. 具体时间复杂度计算”预处理阶段：
- 数字组合枚举：O(2^9) = 512次循环
- 有效组合（满足奇数限制）：约96个
- 每个组合的排列生成：平均O(k!)，其中k最差位8
- 总预处理时间：96 × 8! ≈ 4 × 10^6
4. 长度限制的作用
Section titled “4. 长度限制的作用”if (size > 16) continue;这个限制非常重要：
- 防止溢出：long类型最大约19位，16位提供安全边界
- 减少组合：排除了很多高复杂度的组合
- 实际意义：n ≤ 10^15，最多15位，16位的回文数已经足够覆盖
5. 查询阶段复杂度
Section titled “5. 查询阶段复杂度”- 排序：O(m log m)，其中m是生成的回文数个数（约几千）
- 二分查找：O(log m)，每次查询
总结： 预处理：O(7 × 10^4) ≈ 常数时间 查询：O(log m) ≈ O(log 10^3) ≈ O(10)
因此暴力枚举完全可行，且效率很高。
1. 位掩码表示数字选择
Section titled “1. 位掩码表示数字选择”使用9位二进制数表示选择哪些数字：
mask = 101001001表示选择数字1,4,7,9
2. 奇数数字限制
Section titled “2. 奇数数字限制”使用 o = 0x155 = 101010101 标记奇数位置：
t = o & mask得到选中的奇数(t & (t-1)) == 0确保最多选择一个奇数（判断t是不是2次幂）
3. 回文数构造
Section titled “3. 回文数构造”对于选中的数字组合：
- 偶数数字k：左半部分放k/2个，右半部分对称
- 奇数数字k：左半部分放k/2个，中间放1个，右半部分对称
import java.util.*;
/** * 特殊回文数生成器和查找器 * * 算法原理： * 1. 生成所有可能的"特殊回文数" * 2. 特殊回文数的定义：由数字1-9组成，每个数字最多出现该数字本身次数 * 例如：数字3最多出现3次，数字7最多出现7次 * 3. 回文数结构：左半部分 + 可选中间数字 + 右半部分（左半部分的反转） */public class Solution { // 存储所有生成的特殊回文数，按升序排列 private static List<Long> palindromes = new ArrayList<>();
// 静态初始化块：类加载时就生成所有特殊回文数 static { generateAllPalindromes(); }
/** * 生成所有特殊回文数的主函数 */ private static void generateAllPalindromes() { // o = 0x155 = 341 = 101010101 (二进制) // 这个数字的二进制表示了哪些数字(1,3,5,7,9)是奇数 // 用于后续判断哪些数字可以作为回文数的中间数字 int oddMask = 0x155;
// 遍历所有可能的数字组合（用位掩码表示） // mask的每一位表示是否包含对应的数字 for (int mask = 1; mask < (1 << 9); mask++) { // selectedOdds = oddMask & mask：检查当前组合中哪些奇数数字被选中 int selectedOdds = oddMask & mask;
// (selectedOdds & (selectedOdds - 1)) != 0 检查selectedOdds是否不是2的幂或0 // 这确保最多只有一个奇数数字被选中（作为中间数字） if ((selectedOdds & (selectedOdds - 1)) != 0) continue;
// leftHalf存储构成回文数左半部分的数字 List<Integer> leftHalf = new ArrayList<>(); int totalLength = 0; // 记录回文数的总长度 int middleDigit = 0; // 记录中间的奇数数字（如果有的话）
// 检查mask中的每个数字位置 for (int digit = 1; digit <= 9; digit++) { // 如果第digit个数字被选中 if (((mask >> (digit - 1)) & 1) == 1) { totalLength += digit; // 总长度增加digit（因为数字digit出现digit次）
// 将digit/2个数字digit添加到左半部分 // 例如：如果数字4被选中，则在左半部分添加2个4 for (int j = 0; j < digit / 2; j++) { leftHalf.add(digit); }
// 如果digit是奇数，则有一个数字作为中间数字 if (digit % 2 == 1) { middleDigit = digit; } } }
// 如果回文数长度超过16，跳过（避免数字过大） if (totalLength > 16) continue;
// 生成左半部分所有可能的排列，构造回文数 generatePermutations(leftHalf, 0, middleDigit); }
// 将所有生成的回文数排序 Collections.sort(palindromes); }
/** * 递归生成排列并构造回文数 * @param leftHalf 左半部分的数字列表 * @param start 当前排列的起始位置 * @param middle 中间的奇数数字（0表示没有） */ private static void generatePermutations(List<Integer> leftHalf, int start, int middle) { // 递归终止条件：已经排列完所有数字 if (start == leftHalf.size()) { long palindrome = buildPalindrome(leftHalf, middle); palindromes.add(palindrome); return; }
// 使用HashSet避免生成重复的排列 // 例如：[2,2,3]的排列中，两个2的位置交换结果是相同的 Set<Integer> used = new HashSet<>();
// 尝试将每个未使用的数字放到当前位置 for (int i = start; i < leftHalf.size(); i++) { // 如果这个数字在当前层已经使用过，跳过 if (used.contains(leftHalf.get(i))) continue; used.add(leftHalf.get(i));
// 交换当前位置和第i个位置的数字 Collections.swap(leftHalf, start, i);
// 递归处理下一个位置 generatePermutations(leftHalf, start + 1, middle);
// 回溯：恢复原来的顺序 Collections.swap(leftHalf, start, i); } }
/** * 根据左半部分和中间数字构造回文数 * @param leftHalf 左半部分数字列表 * @param middle 中间数字 * @return 构造的回文数 */ private static long buildPalindrome(List<Integer> leftHalf, int middle) { long result = 0;
// 构建回文数的左半部分 for (int digit : leftHalf) { result = result * 10 + digit; }
// 保存左半部分，用于后续构建右半部分 long leftValue = result;
// 如果有奇数数字，添加到中间 if (middle != 0) { result = result * 10 + middle; }
// 构建右半部分（左半部分的反转） while (leftValue > 0) { long lastDigit = leftValue % 10; // 获取最后一位数字 leftValue /= 10; // 去掉最后一位 result = result * 10 + lastDigit; // 添加到回文数末尾 }
return result; }
/** * 查找大于n的最小特殊回文数 * @param n 给定的数字 * @return 大于n的最小特殊回文数，如果不存在则返回-1 */ public long specialPalindrome(long n) { // 使用二分查找找到第一个大于n的元素 // 这等价于Python中的bisect_right(arr, n) int left = 0, right = palindromes.size() - 1; long result = -1;
while (left <= right) { int mid = left + (right - left) / 2;
if (palindromes.get(mid) > n) { result = palindromes.get(mid); // 记录当前找到的回文数 right = mid - 1; // 继续在左半部分寻找更小的满足条件的位置 } else { left = mid + 1; // 在右半部分寻找 } }
return result; }}假设选择数字2和5（mask = 18 = 010010）：
- 数字分析：
- 数字2：偶数，出现2次，左半部分放1个2
- 数字5：奇数，出现5次，左半部分放2个5，中间放1个5
- 排列生成：
- 左半部分：[2,5,5] → 生成排列 255, 525, 552
- 回文数构造：
- 255 + 5 + 552 = 2555552
- 525 + 5 + 525 = 5255255
- 552 + 5 + 255 = 5525255
时间复杂度总结
Section titled “时间复杂度总结”预处理阶段：
- 数字组合枚举：O(2^9) = 512，其中有效组合约96个
- 每个组合的排列生成：平均O(6!) ≈ 720
- 总预处理：O(96 × 720) ≈ O(7 × 10^4) ≈ 常数时间
查询阶段：
- 排序：O(m log m)，m为生成的回文数个数（约几千）
- 二分查找：O(log m) ≈ O(10)
空间复杂度： O(m)，存储所有特殊回文数
由于预处理只执行一次且复杂度较低，暴力枚举完全可行且高效。