难度: Hard
Submission
运行时间: 47 ms
内存: 16.1 MB
class Solution:
def confusingNumberIII(self, n: int) -> int:
ret = 0
for i in range(1, n + 1):
s = str(i)
if '2' in s:
continue
if '3' in s:
continue
if '4' in s:
continue
if '5' in s:
continue
if '7' in s:
continue
s = s.replace('6', 'z')
s = s.replace('9', '6')
s = s.replace('z', '9')
s = s[::-1]
if s != str(i):
ret += 1
return ret
def confusingNumberII(self, n: int) -> int:
invalid = 0
try:
for l in range(1, len(str(n)) + 1):
hl = (l + 1) // 2
for i in product('01689', repeat=hl):
if i[0] == '0':
continue
if i[-1] == '6' or i[-1] == '9':
if l % 2:
continue
i = ''.join(i)
if l % 2:
s = i + i[:-1][::-1].replace('6', 'a').replace('9', '6').replace('a', '9')
else:
s = i + i[::-1].replace('6', 'a').replace('9', '6').replace('a', '9')
if int(s) >n:
raise ValueError()
invalid += 1
except ValueError:
pass
x = []
flag = False
for c in str(n):
if flag:
x.append('9')
else:
if c in '01689':
x.append(c)
else:
x.append({'7':'6', '5':'1', '4':'1', '3':'1', '2':'1',}[c])
flag = True
x = ''.join(x)
x = x.replace('6', '2').replace('8', '3').replace('9', '4')
x = int(x, 5)
#print(x, invalid)
return x - invalid
Explain
这道题目要求找到不超过给定数字 n 的所有'易混淆数'的数量。'易混淆数'是指当一个数字旋转 180 度后，形成一个不同的有效数字。题解中定义了两个方法：confusingNumberIII 和 confusingNumberII。 confusingNumberIII 方法遍历从 1 到 n 的所有数字，首先将包含不可翻转的数字（2, 3, 4, 5, 7）的数字排除。然后，将剩余的数字进行转换：6 和 9 互换，最后将数字翻转。如果翻转后的数字与原数字不同，则是一个易混淆数。 confusingNumberII 方法使用了一种生成方法来直接构造可能的易混淆数，并且计算它们的数量。通过固定数字的一半长度，然后生成所有可能的组合，并将它们翻转拼接来形成完整的数字。然后根据生成的数字是否有效和是否大于 n 来决定是否停止。这种方法更有效地使用了数位的特性来直接计算易混淆数的数量。
时间复杂度: confusingNumberIII: O(n * k), confusingNumberII: O(5^L)
空间复杂度: confusingNumberIII: O(k), confusingNumberII: O(L)
class Solution:
def confusingNumberIII(self, n: int) -> int:
ret = 0
for i in range(1, n + 1):
s = str(i)
# 排除含有2,3,4,5,7的数字
if any(c in s for c in '23457'):
continue
# 6和9互换
s = s.replace('6', 'z').replace('9', '6').replace('z', '9')
# 反转字符串
s = s[::-1]
# 检查翻转后是否与原字符串不同
if s != str(i):
ret += 1
return ret
def confusingNumberII(self, n: int) -> int:
invalid = 0
try:
for l in range(1, len(str(n)) + 1):
hl = (l + 1) // 2
# 生成长度为 hl 的数字串
for i in product('01689', repeat=hl):
if i[0] == '0':
continue
if i[-1] == '6' or i[-1] == '9':
if l % 2:
continue
i = ''.join(i)
# 根据是否是中间数字调整生成策略
if l % 2:
s = i + i[:-1][::-1].replace('6', 'a').replace('9', '6').replace('a', '9')
else:
s = i + i[::-1].replace('6', 'a').replace('9', '6').replace('a', '9')
# 如果生成的数字超过 n，停止
if int(s) > n:
raise ValueError()
invalid += 1
except ValueError:
pass
x = []
flag = False
for c in str(n):
if flag:
x.append('9')
else:
if c in '01689':
x.append(c)
else:
x.append({'7':'6', '5':'1', '4':'1', '3':'1', '2':'1',}[c])
flag = True
x = ''.join(x)
# 使用不同的替换策略来减少无效数的影响
x = x.replace('6', '2').replace('8', '3').replace('9', '4')
x = int(x, 5)
#print(x, invalid)
return x - invalid
Explore
在`confusingNumberIII`方法中，选择通过字符串操作来检测数字是否为易混淆数主要是因为字符串操作在处理数字的各个位上的替换和反转时更直观和简单。数学运算处理这类问题需要额外的逻辑来分解数字并逐位进行替换，这不仅增加了实现的复杂性，还可能导致错误率增加。而字符串提供了内置的方法来直接进行字符替换和反转，使得代码更简洁、易于理解和维护。
在`confusingNumberII`方法中，通过使用递归或迭代的方式生成数字，并在生成过程中遵循特定的序列（如'01689'），从而避免重复。生成的数字是基于组合的方式构造，确保每种组合只被使用一次。处理大于n的情况是通过在生成数字后立即进行检查，如果生成的数字超过n，则使用`raise ValueError()`来中断所有进一步的数字生成，这样可以有效地停止不必要的计算和迭代。
在`confusingNumberII`方法中，异常处理（`raise ValueError()`）会在生成的数字超过给定的上限n时触发。这种异常用来立即中断当前的数字生成过程，避免进一步的无效计算。选择使用异常来控制流程是因为它提供了一种简洁有效的方式来从多层嵌套的循环中直接退出，特别是在深度递归或多层迭代的场景中，传统的控制结构如break或return可能不足以直接跳出所有层级。异常处理在这种情况下能够立刻响应错误情况，并将控制权返回到上层逻辑。
在`confusingNumberII`方法中，数字的最后一位使用6或9时需要特别处理奇数长度的数字串，是因为在生成对称数字时，中间的数字必须是能够自我翻转的（即0、1、8），这样翻转后的数字才是有效的。如果中间的数字是6或9，翻转后会变成另一个数字（9变6，6变9），这会导致整个数字不再对称。因此，在奇数长度的数字串中，最中间的位不能是6或9，以确保翻转后数字的有效性。