时间戳

首页 > 解决方案 > 查找具有给定长度的“运行”的十进制字符串的数量

python - 查找具有给定长度的“运行”的十进制字符串的数量

问题描述

我遇到了一个问题，我想找到长度为 n 的十进制字符串的数量（n 个数字中的每一个可以是 0,1，...9），它们至少具有length >= k. “运行”是连续递增/递减的数字序列，可以溢出/下溢 mod 10。例如，“345600”、“901285”、“098723”都有长度为 4 的运行，但“123890”只有两个长度运行3.

我的想法是遍历每个10^n可能的候选人。我知道对于每个候选人，您必须检查数字n-k+1的“块”k以查看它们是“递增”还是“递减”。

def checkinc(inputstring, straightlength):
    for startdigit in range(len(inputstring)-straightlength+1):
        for i in range(straightlength):
            if int(inputstring[startdigit+i]) != (int(inputstring[startdigit]) + i)%10:
                return False
    return True

我无法想出一个检查“递增 mod 10”的功能。目前，此函数返回 False 太容易了。也许我错过了一个我还没有学过的标准技巧，或者有一个简单的递归方法可以做到这一点？感谢您的任何指导。

这是我第一次在 StackOverflow 上提问。请让我知道将来如何更好地提出问题。

标签： python

解决方案

当 (a-b+10)%10 等于 1 时，数字 a、b 为递增序列，如果等于 9，则为递减序列。任何其他值表示它们不在序列中。

您可以创建一个字典对，以判断两个连续字符是递增（1）还是递减（9）运行的一部分。然后处理字符串中的每一对字符以将它们转换为运行指标。如果您找到长度为 N-1 的连续“1”或“9”指示符，那么您知道您至少有一个长度为 N 的游程：

def hasRun(string,count):
    match = {(str(n),str((n+d)%10)):str(d) for d in [1,9] for n in range(10) }
    runs  =  "".join( match.get(pair,".") for pair in zip(string,string[1:]) )
    return "1"*(count-1) in runs or "9"*(count-1) in runs

解决此问题的另一种方法是在字符串中搜索长度为 N 的 20 次可能的运行（10 次递增和 10 次反转）：

def hasRun(string,count):
    for i in range(10):
        run = "".join(str((d+i)%10) for d in range(count))
        if run in string or run[::-1] in string: return True
    return False

最后，如果您需要一种程序方法，您可以这样做：

def hasRun(string,count):
    runType  = 0
    runCount = 0
    match = {(str(n),str((n+d)%10)):d for d in [1,9] for n in range(10) }
    for a,b in zip(string,string[1:]):
        delta    = match.get((a,b),0)
        runCount = 2 if delta != runType else runCount + 1
        if delta != 0 and runCount == count:
            return True
        runType  = delta
    return False

注意：这种程序方法在 O(n) 时间内运行。当它在字符串的早期找到请求长度的运行时，它通常会比其他两个执行得更快。这是因为它立即停止迭代并且不处理字符串的其余部分。

推荐阅读