问题描述
我正在尝试制定一种算法，可以确定给定数字范围内的最大公共前缀。 我有一种适用于最简单情况的算法。 但我对此不满意，在更困难的情况下，它分崩离析。
这个想法是对于给定的数字范围，打印出将匹配给定长度的所有数字的前缀。 例如，如果我们有1个长度为3的数字，它将匹配100-199之间的所有数字。
长度根本没有在代码中处理或寻址，只是前缀。
下面的示例代码。 第三种情况根本不起作用。 尽管目前尚无明确检查，但开始位置始终应小于结束位置。
#!/usr/bin/env python3
def calc_sig_num(start, end):
print("Start {} End {}".format(start, end))
while start[-1] == "0" and end[-1] == "9":
start = start[:-1]
end = end[:-1]
start = int(start)
end = int(end)
diff = end - start
ones_removed = 0
keep = True
while True:
if keep:
print(start + diff)
if diff == 0:
break
elif (start + diff) % 10 == 0:
if ones_removed:
keep = False
ones_removed = 0
else:
start //= 10
diff //= 10
else:
diff -= 1
ones_removed += 1
keep = True
print()
if __name__ == '__main__':
calc_sig_num("4929310000", "4929319999")
calc_sig_num("4929312000", "4929312511")
calc_sig_num("8666361784", "8666362423")
"""
expected ouput
Start 4929310000 End 4929319999
492931
Start 4929312000 End 4929312511
4929312511
4929312510
492931250
49293124
49293123
49293122
49293121
49293120
Start 8666361784 End 8666362423
8666362423
8666362422
8666362421
8666362420
866636241
866636240
86663623
86663622
86663621
86663620
86663619
86663618
866636179
8666361789
8666361788
8666361787
8666361786
8666361785
8666361784
"""
1楼
递归是您的朋友：
import os
def calc_sig_num(a, b):
lcp = os.path.commonprefix([a,b])
a, b = a[len(lcp):], b[len(lcp):] # we now have a[0] < b[0]
if a == "0"*len(a) and b == "9"*len(b): # base case, range is X00.. - X99..
yield lcp
return
da, db = int(a[0]), int(b[0])
size = len(a) - 1
for d in range(da, db + 1): # we iterate over 1 digit prefix extensions
suffixes = calc_sig_num(a[1:] if d == da else "0"*size,
b[1:] if d == db else "9"*size)
for suffix in suffixes:
yield lcp + str(d) + suffix
这是一个快速而肮脏的实现，请耐心等待。 我想虽然它具有一定的优雅；）它肯定可以说明这个概念。