文章/答案/技术大牛

发布

社区首页 >问答首页 >计算显着数(或最大公共前缀)

问计算显着数(或最大公共前缀)
EN

Stack Overflow用户

提问于 2014-03-09 22:03:28

回答 1查看 151关注 0票数 1

我试图找出一个算法，可以确定一个给定的数字范围的最大公共前缀。我有一个算法，适用于最简单的情况。但我对此并不满意，在更困难的情况下，它就分崩离析了。

其思想是，对于给定的数字范围，打印前缀，将匹配所有的数字，与给定的长度。例如，如果我们有长度为3的1，它将匹配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
"""

python-3.x

python

algorithm

回答 1

Stack Overflow用户

回答已采纳

发布于 2014-03-10 04:10:29

递归是你的朋友：

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

这是一个快速而肮脏的实现，所以请原谅我。不过，我认为它具有一定的优雅性;)而且它肯定会说明这一概念。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/22288773

复制

相似问题

问计算显着数(或最大公共前缀)
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算显着数(或最大公共前缀)EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算显着数(或最大公共前缀)
EN