Hard

题目描述

k 镜像数字是一个正整数（无前导零），在十进制和 k 进制下从前往后读和从后往前读都相同。

例如，9 是一个 2 镜像数字。9 在十进制和二进制下的表示分别是 9 和 1001，从前往后读和从后往前读都相同。

相反，4 不是一个 2 镜像数字。4 在二进制下的表示是 100，从前往后读和从后往前读不相同。

给定进制 k 和数字 n，返回前 n 个最小的 k 镜像数字的和。

示例 1：

输入：k = 2, n = 5
输出：25
解释：
前 5 个最小的 2 镜像数字及其在二进制下的表示如下：
  十进制    二进制
    1          1
    3          11
    5          101
    7          111
    9          1001
它们的和 = 1 + 3 + 5 + 7 + 9 = 25

示例 2：

输入：k = 3, n = 7
输出：499
解释：
前 7 个最小的 3 镜像数字及其在三进制下的表示如下：
  十进制    三进制
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
它们的和 = 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499

提示：

  • 2 <= k <= 9
  • 1 <= n <= 30

解题思路

解题思路

这道题要找前 n 个最小的 k 镜像数字，即在十进制和 k 进制下都是回文数的数字。

核心思路：

  1. 生成十进制回文数：按长度递增生成所有十进制回文数，而不是逐个检查每个数字
  2. 检查 k 进制回文性：对于每个十进制回文数，转换为 k 进制并检查是否也是回文
  3. 优化搜索空间：通过生成回文数而非暴力枚举大大减少搜索空间

生成回文数的方法：

  • 对于长度为 d 的数字，可以通过取前 ⌈d/2⌉ 位作为"种子"
  • 奇数长度回文：将种子的前 d/2 位反向拼接到种子后面
  • 偶数长度回文：将种子的前 d/2 位反向拼接，不包括中间位

算法流程：

  1. 从长度 1 开始，逐个长度生成所有可能的十进制回文数
  2. 对每个回文数，转换为 k 进制字符串并检查是否回文
  3. 如果是 k 镜像数，加入结果并累加和
  4. 当找到 n 个数字时返回总和

这种方法比暴力枚举效率高很多，因为回文数的密度相对较低，直接生成可以避免大量无用检查。

代码实现

class Solution {
public:
    long long kMirror(int k, int n) {
        long long sum = 0;
        int count = 0;
        int len = 1;
        
        while (count < n) {
            // Generate palindromes of length len
            long long start = (len == 1) ? 1 : pow(10, (len - 1) / 2);
            long long end = pow(10, (len + 1) / 2);
            
            for (long long i = start; i < end && count < n; i++) {
                long long palindrome = generatePalindrome(i, len);
                if (isPalindromeInBaseK(palindrome, k)) {
                    sum += palindrome;
                    count++;
                }
            }
            len++;
        }
        
        return sum;
    }
    
private:
    long long generatePalindrome(long long seed, int len) {
        string s = to_string(seed);
        string palindrome = s;
        
        if (len % 2 == 0) {
            // Even length: reverse entire seed
            reverse(s.begin(), s.end());
            palindrome += s;
        } else {
            // Odd length: reverse seed without middle digit
            reverse(s.begin(), s.end() - 1);
            palindrome += s;
        }
        
        return stoll(palindrome);
    }
    
    bool isPalindromeInBaseK(long long num, int k) {
        string baseK = "";
        long long temp = num;
        
        while (temp > 0) {
            baseK = to_string(temp % k) + baseK;
            temp /= k;
        }
        
        string reversed = baseK;
        reverse(reversed.begin(), reversed.end());
        
        return baseK == reversed;
    }
};

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        def generate_palindrome(seed, length):
            s = str(seed)
            if length % 2 == 0:
                # Even length
                return int(s + s[::-1])
            else:
                # Odd length
                return int(s + s[-2::-1])
        
        def is_palindrome_in_base_k(num, k):
            base_k = ""
            while num > 0:
                base_k = str(num % k) + base_k
                num //= k
            return base_k == base_k[::-1]
        
        total_sum = 0
        count = 0
        length = 1
        
        while count < n:
            # Generate palindromes of current length
            start = 1 if length == 1 else 10 ** ((length - 1) // 2)
            end = 10 ** ((length + 1) // 2)
            
            for seed in range(start, end):
                if count >= n:
                    break
                    
                palindrome = generate_palindrome(seed, length)
                if is_palindrome_in_base_k(palindrome, k):
                    total_sum += palindrome
                    count += 1
            
            length += 1
        
        return total_sum

public class Solution {
    public long KMirror(int k, int n) {
        long sum = 0;
        int count = 0;
        int len = 1;
        
        while (count < n) {
            // Generate palindromes of length len
            long start = (len == 1) ? 1 : (long)Math.Pow(10, (len - 1) / 2);
            long end = (long)Math.Pow(10, (len + 1) / 2);
            
            for (long i = start; i < end && count < n; i++) {
                long palindrome = GeneratePalindrome(i, len);
                if (IsPalindromeInBaseK(palindrome, k)) {
                    sum += palindrome;
                    count++;
                }
            }
            len++;
        }
        
        return sum;
    }
    
    private long GeneratePalindrome(long seed, int len) {
        string s = seed.ToString();
        string palindrome = s;
        
        if (len % 2 == 0) {
            // Even length: reverse entire seed
            char[] arr = s.ToCharArray();
            Array.Reverse(arr);
            palindrome += new string(arr);
        } else {
            // Odd length: reverse seed without middle digit
            char[] arr = s.ToCharArray();
            Array.Reverse(arr, 0, arr.Length - 1);
            palindrome += new string(arr);
        }
        
        return long.Parse(palindrome);
    }
    
    private bool IsPalindromeInBaseK(long num, int k) {
        string baseK = "";
        long temp = num;
        
        while (temp > 0) {
            baseK = (temp % k).ToString() + baseK;
            temp /= k;
        }
        
        char[] reversed = baseK.ToCharArray();
        Array.Reverse(reversed);
        
        return baseK == new string(reversed);
    }
}

var kMirror = function(k, n) {
    function isPalindrome(str) {
        return str === str.split('').reverse().join('');
    }
    
    function toBaseK(num, base) {
        if (num === 0) return '0';
        let result = '';
        while (num > 0) {
            result = (num % base) + result;
            num = Math.floor(num / base);
        }
        return result;
    }
    
    function generatePalindromes() {
        const palindromes = [];
        
        // Single digit palindromes
        for (let i = 1; i <= 9; i++) {
            palindromes.push(i);
        }
        
        // Multi-digit palindromes
        for (let len = 2; len <= 10; len++) {
            const isOdd = len % 2 === 1;
            const halfLen = Math.floor(len / 2);
            const start = Math.pow(10, halfLen - 1);
            const end = Math.pow(10, halfLen);
            
            for (let i = start; i < end; i++) {
                const leftHalf = i.toString();
                let rightHalf = leftHalf.split('').reverse().join('');
                
                if (isOdd) {
                    for (let mid = 0; mid <= 9; mid++) {
                        const palindrome = parseInt(leftHalf + mid + rightHalf);
                        palindromes.push(palindrome);
                    }
                } else {
                    const palindrome = parseInt(leftHalf + rightHalf);
                    palindromes.push(palindrome);
                }
            }
        }
        
        return palindromes.sort((a, b) => a - b);
    }
    
    const palindromes = generatePalindromes();
    const kMirrors = [];
    
    for (const num of palindromes) {
        if (kMirrors.length >= n) break;
        
        const baseKRep = toBaseK(num, k);
        if (isPalindrome(baseKRep)) {
            kMirrors.push(num);
        }
    }
    
    return kMirrors.reduce((sum, num) => sum + num, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m × log_k(P))
空间复杂度O(log_k(P))

其中 m 是生成的回文数数量，P 是第 n 个 k 镜像数的值。时间复杂度主要由生成回文数和检查 k 进制回文性决定。空间复杂度主要用于存储 k 进制字符串。

相关题目