k 镜像数字的和

难度: Hard

一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的正整数。

比方说，9 是一个 2 镜像数字。9 在十进制下为 9 ，二进制下为 1001 ，两者从前往后读和从后往前读都一样。
相反地，4 不是一个 2 镜像数字。4 在二进制下为 100 ，从前往后和从后往前读不相同。

给你进制 k 和一个数字 n ，请你返回 k 镜像数字中最小的 n 个数之和。

示例 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 。

示例 3：

输入：k = 7, n = 17
输出：20379000
解释：17 个最小的 7 镜像数字分别为：
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

提示：

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

Submission

运行时间: 740 ms

内存: 139.6 MB

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        """

        :param k:
        :param n:
        :return:
        """
        @cache
        def gen_ans(length):
            if length == 0:
                return ['']
            if length == 1:
                return [str(i) for i in range(k)]
            ret = []

            for i in range(k):
                base = str(i)
                for res in gen_ans(length-2):
                    ret.append(base + res + base)
            return ret

        collected = 0
        cnt = 0
        for i in range(1, 101):
            anslist = gen_ans(i)
            for j in anslist:
                if j[0] == '0':
                    continue
                xval = str(int(j, k))
                if xval != xval[::-1]:
                    continue
                collected += 1
                cnt += int(j, k)
                if collected >= n:
                    break
            if collected >= n:
                break
        return cnt

Explain

该题解的核心是生成并检验k镜像数字。首先，使用一个递归函数`gen_ans`生成长度为`i`的所有可能的k进制数，这些数的特点是从两边向中间对称。然后，逐个检验这些数是否也是十进制下的镜像数字。如果是，累加它们的十进制值，并计数。当找到足够的k镜像数字时，返回它们的和。

时间复杂度: O(k^i * d)，其中i是最大的数字长度，d是数字的位数

空间复杂度: O(k^i)，其中i是最大的数字长度

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        
        @cache
        def gen_ans(length):
            # 递归生成长度为length的所有对称的k进制数
            if length == 0:
                return ['']
            if length == 1:
                return [str(i) for i in range(k)]
            ret = []
            
            for i in range(k):
                base = str(i)
                for res in gen_ans(length-2):
                    ret.append(base + res + base)
            return ret
        
        collected = 0
        cnt = 0
        # 检查生成的数字是否满足条件，并累加
        for i in range(1, 101):
            anslist = gen_ans(i)
            for j in anslist:
                if j[0] == '0':
                    continue
                xval = str(int(j, k))
                # 检查十进制表示是否是镜像的
                if xval != xval[::-1]:
                    continue
                collected += 1
                cnt += int(j, k)
                if collected >= n:
                    break
            if collected >= n:
                break
        return cnt

Explore

在`gen_ans`递归函数中，确保生成的k进制数是对称的通过以下步骤：首先，如果请求生成长度为0的对称数，返回一个空字符串列表。如果长度为1，则返回所有单个数字的字符串，这些自然是对称的。对于更长的长度，函数首先遍历所有可能的数字作为起始和结束位（保证对称），然后递归地在这对数字之间插入长度为`length-2`的对称数。这样，每个生成的数都是通过在较短的对称数两侧添加相同数字构造的，从而确保整个数字的对称性。

在k进制数中，首位数字为'0'意味着该数实际上在数学意义上不是一个有效的数值（例如，'012'在十进制中应该表示为'12'）。这种情况在k进制表示中也同样适用，因为首位的'0'会使得数值的表示和实际值不符。在转换这种数到十进制时，会丢失前导零，导致可能的误解和数值错误。因此，检验时需要排除首位为'0'的k进制数，确保所有数在十进制和k进制中都是有效且准确的。

递归深度101在代码中并不是基于严格的数学证明，而是一个实际的设定范围，可能是为了确保足够的搜索深度来生成所需数量的镜像数字。这个值可能比实际需要的值大，确保覆盖足够的情况。实际上，更优的深度选择应该基于n的值（即所需的镜像数字的数量）和k的值。如果n较小或k较大，可能不需要如此深的递归。在实际应用中，可以根据具体问题需要调整递归深度，通过实验确定最佳值以优化性能。