易混淆数

Submission

运行时间: 20 ms

内存: 16.7 MB

class Solution:
    def confusingNumber(self, n: int) -> bool:
        dict = {'0':'0','1':'1','6':'9','8':'8','9':'6'}
        numstr = str(n)
        newnum = []
        for digit in numstr:
            newdigit = dict.get(digit,-1)
            if newdigit == -1:
                return False
            newnum = [newdigit] + newnum
        return int(''.join(newnum)) != n

Explain

该题解的核心思路是检查一个数字翻转180度后是否仍然保持不变。首先，我们使用一个字典来定义哪些数字可以翻转，并且翻转后的结果是什么（例如，'6'变成'9'，'9'变成'6'）。对于输入的数字n，我们首先将其转换为字符串，然后遍历每一个字符，使用字典查找翻转后的字符。如果某个字符在字典中没有对应的翻转结果，则直接返回False，表示这不是一个易混淆数。如果所有字符都能找到对应的翻转结果，我们将这些结果组成新的数字字符串，并判断翻转后的数字是否与原始数字不同。如果不同，则返回True；如果相同，则返回False。

时间复杂度: O(d)

空间复杂度: O(d)

class Solution:
    def confusingNumber(self, n: int) -> bool:
        # 定义翻转字典
        dict = {'0':'0','1':'1','6':'9','8':'8','9':'6'}
        # 将数字转为字符串
        numstr = str(n)
        # 初始化新数字列表
        newnum = []
        # 遍历每个数字
        for digit in numstr:
            # 从字典获取翻转后的数字
            newdigit = dict.get(digit,-1)
            # 如果数字不能翻转，返回False
            if newdigit == -1:
                return False
            # 将翻转后的数字加到列表前部
            newnum = [newdigit] + newnum
        # 比较原数字和翻转后的数字是否不同
        return int(''.join(newnum)) != n

Explore

易混淆数的定义是一个数字在翻转180度后，产生的数字与原数字不同且仍然有效。这意味着，如果翻转后的数字与原数字相同，则它不符合易混淆数的条件。因此，检查翻转后的数字是否与原数字不同是确认其为易混淆数的关键步骤。

在180度翻转的情况中，只有'0', '1', '6', '8', '9'这几个数字翻转后可以形成有效的数字（其中'6'和'9'互为翻转）。其他数字如'2', '3', '4', '5', '7'翻转后无法形成有效的数字，因此不包括在翻转字典中。例如，'2'翻转后的形状不对应任何有效的数字字符。

将翻转后的数字加到列表前部是为了实现数字的反向组合，即从最后一个字符到第一个字符的顺序，这模拟了数字的翻转过程。使用列表而不是直接构造字符串是因为列表在这种操作中修改更加灵活和高效（如插入操作）。最终可以通过将列表转换为字符串来获取最终翻转后的数字。

在数学中和大多数编程场景里，数字通常不会记录前导零。例如，数字'010'通常会被处理为'10'。当进行翻转操作时，只会考虑有效的数字部分，因此'010'翻转后会首先被视为'10'，然后翻转得到'01'，即最终处理结果为'1'。这表明前导零在翻转过程中会被忽略。