千问 LeetCode 2081.K 镜像数字的和 TypeScript实现

这是一道结合了回文数构造和进制转换的题目。

🧠 核心思路

1. 题目目标：
   找到最小的 n 个正整数，使得它们在十进制下是回文数，且在 k 进制下也是回文数。最后返回这些数的和。

2. 解题策略：

   • 暴力枚举不可行：如果从 1 开始逐个判断，效率太低，因为回文数很稀疏。
   • 构造回文数：我们应该直接生成十进制下的回文数，从小到大。
   • 生成方法：
     • 通过枚举回文数的左半部分来生成完整的回文数。
     • 例如：左半部分是 12，可以生成奇数长度回文 121（中间加一位）或偶数长度回文 1221（直接拼接反转）。
   • 验证：对生成的每个十进制回文数，将其转换为 k 进制，检查是否也是回文。

3. 算法流程：

   1. 从长度为 1 的数字开始（1-9），生成长度为 len 的所有回文数。
   2. 对于每个生成的回文数，检查其 k 进制形式是否为回文。
   3. 如果是，累加到结果中，计数器加一。
   4. 当找到 n 个满足条件的数时，返回总和。

💻 TypeScript 代码实现

function kMirror(k: number, n: number): number {
let sum = 0;
let count = 0;

// 从长度为 1 的回文数开始，逐步增加长度 for (let len = 1; count 0) { kBaseStr += (n % k).toString(); n = Math.floor(n / k); } // 检查是否是回文 return kBaseStr === kBaseStr.split('').reverse().join('');

}

⚡ 优化版本（更高效的回文生成）

function kMirror(k: number, n: number): number {
let sum = 0;
let count = 0;

// 从长度为1的回文数开始 for (let len = 1; count 0) { kBaseStr += (n % k).toString(); n = Math.floor(n / k); } return kBaseStr === kBaseStr.split('').reverse().join('');

}

📝 复杂度分析

1. 时间复杂度：

   • 主要取决于需要检查多少个十进制回文数才能找到 n 个 k 进制回文数。
   • 生成回文数的效率远高于暴力遍历。

2. 空间复杂度：O(log N)，用于存储进制转换的字符串。

💡 关键点

1. 主动生成回文数：比暴力遍历高效得多。
2. 双重回文检查：先检查十进制回文，再检查 k 进制回文。
3. 提前终止：找到 n 个就立即返回。