移除 9

Submission

运行时间: 32 ms

内存: 16.4 MB

class Solution:
    def newInteger(self, n: int) -> int:
        if n == 0:
            return 0
        return self.newInteger(n // 9) * 10 + n % 9

Explain

该题解使用递归的方法求解。基本思路是将数字 n 看作 9 进制数，然后将其转换为 9 进制数的十进制表示。在转换过程中，9 会被跳过，最终得到移除了 9 的新整数。递归函数每次处理 n 的一位数字，将其转换为新的整数。

时间复杂度: O(log n)

空间复杂度: O(log n)

class Solution:
    def newInteger(self, n: int) -> int:
        if n == 0:
            return 0
        # 递归处理 n // 9 的结果，将其乘以 10，再加上当前位数字 n % 9
        return self.newInteger(n // 9) * 10 + n % 9

Explore

将一个数字转换为9进制数意味着我们只使用0到8这9个数字。在这种转换中，每个9进制的位代表的是9的幂次（例如，最右边的位代表9^0，下一位代表9^1，依此类推）。当我们将一个十进制数转换为9进制时，本质上是将其表示为一个不包含数位9的数。这是因为在9进制中，任何数位都不会出现9（类似于十进制中不会出现数字10）。因此，通过将十进制数转换为9进制并使用其位数作为新的十进制数，我们自然地“跳过”了所有的9。

在递归函数中，将n除以9的目的是为了逐步减少n的大小，逐渐向基本情况靠近，即n为0的情况。n除以9的操作实际上是移除了n最低位的9进制表示。例如，如果n是十进制数，n除以9后得到的商是去掉最低位的9进制数，余数则是当前的最低位（0到8之间）。递归处理商，然后将其结果用于构建没有9的新整数。

在递归过程中，将结果乘以10再加上n%9是为了构建新的整数，其中n%9是当前9进制位的值，乘以10是因为我们正在构建一个十进制数。具体来说，每递归一次，我们处理一个9进制位，将其转换为十进制并放在结果的最右边。乘以10的操作是为了为下一个9进制位腾出位置。这种操作确保了每次递归调用处理的9进制位正确地放置在十进制结果中的相应位置。

递归结束的条件是n为0，这是一个安全的边界条件，因为它确保了所有的数字都被正确处理。当n为0时，意味着没有更多的数字可以转换（即n已经完全转换为9进制表示），因此返回0是合理的。这种设计不会导致处理极小或特定数字时的边界问题。实际上，这样的设计确保了从最小的整数（0）到任何较大的数都可以被正确处理。