检查一个数是否可以由一个数及其倒数的总和组成
Check if a number can be formed by sum of a number and its reverse
我想检查给定的数字是否可以由另一个数字组成，比如 b 和 reverse(b)。例如 12 == 6+6、22 == 11 + 11 和 121 == 29+92。我想通的一件事是，如果数字是 11 的倍数或者是小于 20 的偶数，那么它就可以形成。我试图在下面实现这个：
num = 121
if num%11==0:
print('Yes')
else:
if num%2==0 and num<20:
print('Yes')
else:
for j in range(11,(int(num)//2)+1):
if j+int(str(j)[::-1])==num:
print('Yes')
break
但是，如果条件进入 for 循环，它会给出 TLE。可以再给个条件吗？
更新：如果反转后的数字有尾随零，则应将其删除，然后再添加。例如：101 == 100+1。我正在寻找我的代码的优化形式。或者我认为我缺少一些可能需要 O(1) 时间的条件，类似于条件 if num%11==0: print('Yes')
能否提供问题的约束条件？
您可以尝试以下方法：
i = 0
j = num
poss = 0
while(i<=j):
if(str(i)==str(j)[::-1]):
poss = 1
break
i+=1
j-=1
if(poss):
print("Yes")
else:
print("No")
你可以像这样暴力破解：
def reverse_digits(n):
return int(str(n)[::-1])
def sum_of_reversed_numbers(num):
for i in range(num + 1):
if i == reverse_digits(num - i):
return i, num - i
return None
print("Yes" if sum_of_reversed_numbers(num) else "No")
不用 str 切片也可以：
def reverse(n):
r = 0
while n != 0:
r = r*10 + int(n%10)
n = int(n/10)
return r
def f(n):
for i in range(n + 1):
if i + reverse(i) == n:
return True
return False
print('Yes' if f(101) else 'No')
#Yes
前面的答案都不是真正的检查。这更像是一种蛮力尝试和错误。
所以让我们做得更聪明一些。
我们从一个数字开始，例如246808642。我们可以将问题简化为数字末尾的外部2位值。让我们称这个值在前面为 A 和 B，在后面为 Y 和 Z。中间的其余部分是 Π。所以我们的数字现在看起来是 ABΠYZ，A = 2，B = 4，Π = 68086，Y = 4 和 Z = 2。（一对可能的数字求和是 123404321）。 A 是否等于 1，这仅适用于大于 10 的总和（一个假设，但我想它可行，一些证明会很好！）。
所以如果它是一个，我们知道倒数第二个数字比结转大一个。所以我们暂时忽略A，比较B和Z，因为它们应该是相同的，因为两者都是相同的两个数相加的结果。如果是这样，我们取剩余的部分 Π 并将 Y 减一（从外部加法结转），然后可以从该图表的顶部再次开始 Π(Y-1)。只有结转才能使 B 比 Z 大 1，如果是这样，我们可以将 B 替换为 1，并从顶部的 1Π(Y-1) 开始。 B-1!=Z 和 B!=Z，我们可以停下来，这对于一个数字的总和及其反转的数字来说是不可能的。
如果 A != 1，我们做的一切都与以前类似，但现在我们使用 A 而不是 B。（我在这里删掉这个。答案已经够长了。）
代码：
import time
def timing(f):
def wrap(*args, **kwargs):
time1 = time.time()
ret = f(*args, **kwargs)
time2 = time.time()
print('{:s} function took {:.3f} ms'.format(f.__name__, (time2-time1)*1000.0))
return ret
return wrap
@timing
def check(num):
num = str(num)
if (int(num) < 20 and int(num)%2 == 0) or (len(num) ==2 and int(num)%11 == 0):
return print('yes')
if len(num) <= 2 and int(num)%2 != 0:
return print('no')
# get the important place values of the number x
A = num[0]
B = num[1]
remaining = num[2:-2]
Y = num[-2]
Z = num[-1]
# check if A = 1
if A == '1':
# A = 1
# check if B == Z
if B == Z:
# so the outest addition matches perfectly and no carry over from inner place values is involved
# reduce the last digit about one and check again.
check(remaining + (str(int(Y)-1) if Y != '0' else '9'))
elif int(B)-1 == int(Z):
# so the outest addition matches needs a carry over from inner place values to match, so we add to
# to the remaining part of the number a leading one
# we modify the last digit of the remaining place values, because the outest had a carry over
check('1' + remaining + (str(int(Y)-1) if Y != '0' else '9'))
else:
print("Not able to formed by a sum of a number and its reversed.")
else:
# A != 1
# check if A == Z
if A == Z:
# so the outest addition matches perfectly and no carry over from inner place values is involved
check(B + remaining + Y)
elif int(A) - 1 == int(Z):
# so the outest addition matches needs a carry over from inner place values to match, so we add to
# to the remaining part of the number a leading one
# we modify the last digit of the remaining place values, because the outest had a carry over
check('1' + B + remaining + Y)
else:
print("Not able to formed by a sum of a number and its reversed.")
@timing
def loop_check(x):
for i in range(x + 1):
if i == int(str(x - i)[::-1]) and not str(x - i).endswith("0"):
print('yes, by brute force')
break
loop_check(246808642)
check(246808642)
结果：
yes, by brute force
loop_check function took 29209.069 ms
Yes
check function took 0.000 ms
还有一次我们看到了数学的力量。希望这对你有用！
我的解决方案的基本思想是首先生成数字到可以组成它们的数字的映射，因此 0 可以由 0+0 或 1+9、2+ 组成8 等（但在这种情况下，您必须在下一步中牢记进位 1）。然后您从最小的数字开始，并使用该代码检查形成第一个数字的每种可能方式（这为您提供了数字的第一个和最后一个数字的候选人，这些数字与其倒数相加以提供输入数字）。然后你继续第二个数字并尝试那些。通过同时检查最后一位和第一位数字可以大大改进此代码，但它因进位 1 而变得复杂。
import math
candidates = {}
for a in range(10):
for b in range(10):
# a, b, carry
candidates.setdefault((a + b) % 10, []).append((a, b, (a + b) // 10))
def sum_of_reversed_numbers(num):
# We reverse the digits because Arabic numerals come from Arabic, which is
# written right-to-left, whereas English text and arrays are written left-to-right
digits = [int(d) for d in str(num)[::-1]]
# result, carry, digit_index
test_cases = [([None] * len(digits), 0, 0)]
if len(digits) > 1 and str(num).startswith("1"):
test_cases.append(([None] * (len(digits) - 1), 0, 0))
results = []
while test_cases:
result, carry, digit_index = test_cases.pop(0)
if None in result:
# % 10 because if the current digit is a 0 but we have a carry from
# the previous digit, it means that the result and its reverse need
# to actually sum to 9 here so that the +1 carry turns it into a 0
cur_digit = (digits[digit_index] - carry) % 10
for a, b, new_carry in candidates[cur_digit]:
new_result = result[::]
new_result[digit_index] = a
new_result[-(digit_index + 1)] = b
test_cases.append((new_result, new_carry, digit_index + 1))
else:
if result[-1] == 0 and num != 0: # forbid 050 + 050 == 100
continue
i = "".join(str(x) for x in result)
i, j = int(i), int(i[::-1])
if i + j == num:
results.append((min(i, j), max(i, j)))
return results if results else None
我们可以通过预先计算从 0 到 10ⁿ 及其倒数的所有数字的总和并将它们存储在名为 correct 的列表字典中来检查上面的代码（列表是因为有很多方法可以形成相同的数字，例如 11+11 == 02 + 20)，这意味着我们有 10ⁿ⁻¹ 的正确答案，我们可以用它来检查上面的函数。顺便说一句，如果你经常用小数字做这件事，这种预计算方法会更快，但会占用内存。
如果此代码不打印任何内容，则表示它可以正常工作（或者您的终端已损坏 :)）
correct = {}
for num in range(1000000):
backwards = int(str(num)[::-1])
components = min(num, backwards), max(num, backwards)
summed = num + backwards
correct.setdefault(summed, []).append(components)
for i in range(100000):
try:
test = sum_of_reversed_numbers(i)
except Exception as e:
raise Exception(i) from e
if test is None:
if i in correct:
print(i, test, correct.get(i))
elif sorted(test) != sorted(correct[i]):
print(i, test, correct.get(i))
偷了@Doluk 的想法。我今天在测试中被问到这个问题。我当时解决不了。根据 Doluk 的想法并认真思考，下面是一种用于一级递归的决策树。我可能是错的，因为我没有 运行 这个算法。
设n为数字，我们要检查是否特殊
情况一：前导数不为1
情况 1a：内部加法没有结转
abcdefgh
hgfedcba
x x => (a+h) < 10
if both ends are same in n, strip both sides by one digit and recurse
情况 1b：从内部加法结转
1
abcdefgh
hgfedcba
(x+1)......(x) => (a+h+1) < 10
if left end is 1 greater than right end in n, strip both sides by one digit, add digit 1 on the left and recurse
情况2：前导数为1
情况 2a：内部加法没有结转
1 1
abcdefgh
hgfedcba
1x x => (a+h) >= 10
strip - if second and last digit are same, strip two digits from left and one from right, from the remaining number minus 1 and recurse.
情况 2b：从内部加法结转
案例 2bi: a+h = 9
11
abcdefgh
hgfedcba
10......9
strip - two from left and one from right and recurse.
案例 2bj：a+h >= 10
11 1
abcdefgh
hgfedcba
1(x+1)......x
strip - two from left and one from right and subtract 1 from number and recurse.
我想检查给定的数字是否可以由另一个数字组成，比如 b 和 reverse(b)。例如 12 == 6+6、22 == 11 + 11 和 121 == 29+92。我想通的一件事是，如果数字是 11 的倍数或者是小于 20 的偶数，那么它就可以形成。我试图在下面实现这个：
num = 121
if num%11==0:
print('Yes')
else:
if num%2==0 and num<20:
print('Yes')
else:
for j in range(11,(int(num)//2)+1):
if j+int(str(j)[::-1])==num:
print('Yes')
break
但是，如果条件进入 for 循环，它会给出 TLE。可以再给个条件吗？
更新：如果反转后的数字有尾随零，则应将其删除，然后再添加。例如：101 == 100+1。我正在寻找我的代码的优化形式。或者我认为我缺少一些可能需要 O(1) 时间的条件，类似于条件 if num%11==0: print('Yes')
能否提供问题的约束条件？
您可以尝试以下方法：
i = 0
j = num
poss = 0
while(i<=j):
if(str(i)==str(j)[::-1]):
poss = 1
break
i+=1
j-=1
if(poss):
print("Yes")
else:
print("No")
你可以像这样暴力破解：
def reverse_digits(n):
return int(str(n)[::-1])
def sum_of_reversed_numbers(num):
for i in range(num + 1):
if i == reverse_digits(num - i):
return i, num - i
return None
print("Yes" if sum_of_reversed_numbers(num) else "No")
不用 str 切片也可以：
def reverse(n):
r = 0
while n != 0:
r = r*10 + int(n%10)
n = int(n/10)
return r
def f(n):
for i in range(n + 1):
if i + reverse(i) == n:
return True
return False
print('Yes' if f(101) else 'No')
#Yes
前面的答案都不是真正的检查。这更像是一种蛮力尝试和错误。 所以让我们做得更聪明一些。
我们从一个数字开始，例如246808642。我们可以将问题简化为数字末尾的外部2位值。让我们称这个值在前面为 A 和 B，在后面为 Y 和 Z。中间的其余部分是 Π。所以我们的数字现在看起来是 ABΠYZ，A = 2，B = 4，Π = 68086，Y = 4 和 Z = 2。（一对可能的数字求和是 123404321）。 A 是否等于 1，这仅适用于大于 10 的总和（一个假设，但我想它可行，一些证明会很好！）。
所以如果它是一个，我们知道倒数第二个数字比结转大一个。所以我们暂时忽略A，比较B和Z，因为它们应该是相同的，因为两者都是相同的两个数相加的结果。如果是这样，我们取剩余的部分 Π 并将 Y 减一（从外部加法结转），然后可以从该图表的顶部再次开始 Π(Y-1)。只有结转才能使 B 比 Z 大 1，如果是这样，我们可以将 B 替换为 1，并从顶部的 1Π(Y-1) 开始。 B-1!=Z 和 B!=Z，我们可以停下来，这对于一个数字的总和及其反转的数字来说是不可能的。
如果 A != 1，我们做的一切都与以前类似，但现在我们使用 A 而不是 B。（我在这里删掉这个。答案已经够长了。）
代码：
import time
def timing(f):
def wrap(*args, **kwargs):
time1 = time.time()
ret = f(*args, **kwargs)
time2 = time.time()
print('{:s} function took {:.3f} ms'.format(f.__name__, (time2-time1)*1000.0))
return ret
return wrap
@timing
def check(num):
num = str(num)
if (int(num) < 20 and int(num)%2 == 0) or (len(num) ==2 and int(num)%11 == 0):
return print('yes')
if len(num) <= 2 and int(num)%2 != 0:
return print('no')
# get the important place values of the number x
A = num[0]
B = num[1]
remaining = num[2:-2]
Y = num[-2]
Z = num[-1]
# check if A = 1
if A == '1':
# A = 1
# check if B == Z
if B == Z:
# so the outest addition matches perfectly and no carry over from inner place values is involved
# reduce the last digit about one and check again.
check(remaining + (str(int(Y)-1) if Y != '0' else '9'))
elif int(B)-1 == int(Z):
# so the outest addition matches needs a carry over from inner place values to match, so we add to
# to the remaining part of the number a leading one
# we modify the last digit of the remaining place values, because the outest had a carry over
check('1' + remaining + (str(int(Y)-1) if Y != '0' else '9'))
else:
print("Not able to formed by a sum of a number and its reversed.")
else:
# A != 1
# check if A == Z
if A == Z:
# so the outest addition matches perfectly and no carry over from inner place values is involved
check(B + remaining + Y)
elif int(A) - 1 == int(Z):
# so the outest addition matches needs a carry over from inner place values to match, so we add to
# to the remaining part of the number a leading one
# we modify the last digit of the remaining place values, because the outest had a carry over
check('1' + B + remaining + Y)
else:
print("Not able to formed by a sum of a number and its reversed.")
@timing
def loop_check(x):
for i in range(x + 1):
if i == int(str(x - i)[::-1]) and not str(x - i).endswith("0"):
print('yes, by brute force')
break
loop_check(246808642)
check(246808642)
结果：
yes, by brute force
loop_check function took 29209.069 ms
Yes
check function took 0.000 ms
还有一次我们看到了数学的力量。希望这对你有用！
我的解决方案的基本思想是首先生成数字到可以组成它们的数字的映射，因此 0 可以由 0+0 或 1+9、2+ 组成8 等（但在这种情况下，您必须在下一步中牢记进位 1）。然后您从最小的数字开始，并使用该代码检查形成第一个数字的每种可能方式（这为您提供了数字的第一个和最后一个数字的候选人，这些数字与其倒数相加以提供输入数字）。然后你继续第二个数字并尝试那些。通过同时检查最后一位和第一位数字可以大大改进此代码，但它因进位 1 而变得复杂。
import math
candidates = {}
for a in range(10):
for b in range(10):
# a, b, carry
candidates.setdefault((a + b) % 10, []).append((a, b, (a + b) // 10))
def sum_of_reversed_numbers(num):
# We reverse the digits because Arabic numerals come from Arabic, which is
# written right-to-left, whereas English text and arrays are written left-to-right
digits = [int(d) for d in str(num)[::-1]]
# result, carry, digit_index
test_cases = [([None] * len(digits), 0, 0)]
if len(digits) > 1 and str(num).startswith("1"):
test_cases.append(([None] * (len(digits) - 1), 0, 0))
results = []
while test_cases:
result, carry, digit_index = test_cases.pop(0)
if None in result:
# % 10 because if the current digit is a 0 but we have a carry from
# the previous digit, it means that the result and its reverse need
# to actually sum to 9 here so that the +1 carry turns it into a 0
cur_digit = (digits[digit_index] - carry) % 10
for a, b, new_carry in candidates[cur_digit]:
new_result = result[::]
new_result[digit_index] = a
new_result[-(digit_index + 1)] = b
test_cases.append((new_result, new_carry, digit_index + 1))
else:
if result[-1] == 0 and num != 0: # forbid 050 + 050 == 100
continue
i = "".join(str(x) for x in result)
i, j = int(i), int(i[::-1])
if i + j == num:
results.append((min(i, j), max(i, j)))
return results if results else None
我们可以通过预先计算从 0 到 10ⁿ 及其倒数的所有数字的总和并将它们存储在名为 correct 的列表字典中来检查上面的代码（列表是因为有很多方法可以形成相同的数字，例如 11+11 == 02 + 20)，这意味着我们有 10ⁿ⁻¹ 的正确答案，我们可以用它来检查上面的函数。顺便说一句，如果你经常用小数字做这件事，这种预计算方法会更快，但会占用内存。
如果此代码不打印任何内容，则表示它可以正常工作（或者您的终端已损坏 :)）
correct = {}
for num in range(1000000):
backwards = int(str(num)[::-1])
components = min(num, backwards), max(num, backwards)
summed = num + backwards
correct.setdefault(summed, []).append(components)
for i in range(100000):
try:
test = sum_of_reversed_numbers(i)
except Exception as e:
raise Exception(i) from e
if test is None:
if i in correct:
print(i, test, correct.get(i))
elif sorted(test) != sorted(correct[i]):
print(i, test, correct.get(i))
偷了@Doluk 的想法。我今天在测试中被问到这个问题。我当时解决不了。根据 Doluk 的想法并认真思考，下面是一种用于一级递归的决策树。我可能是错的，因为我没有 运行 这个算法。
设n为数字，我们要检查是否特殊
情况一：前导数不为1
情况 1a：内部加法没有结转
abcdefgh
hgfedcba
x x => (a+h) < 10
if both ends are same in n, strip both sides by one digit and recurse
情况 1b：从内部加法结转
1
abcdefgh
hgfedcba
(x+1)......(x) => (a+h+1) < 10
if left end is 1 greater than right end in n, strip both sides by one digit, add digit 1 on the left and recurse
情况2：前导数为1
情况 2a：内部加法没有结转
1 1
abcdefgh
hgfedcba
1x x => (a+h) >= 10
strip - if second and last digit are same, strip two digits from left and one from right, from the remaining number minus 1 and recurse.
情况 2b：从内部加法结转
案例 2bi: a+h = 9
11
abcdefgh
hgfedcba
10......9
strip - two from left and one from right and recurse.
案例 2bj：a+h >= 10
11 1
abcdefgh
hgfedcba
1(x+1)......x
strip - two from left and one from right and subtract 1 from number and recurse.