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

Question

我遇到了一个问题，我想找出长度为n的十进制字符串的数目（n个数字中的每一个可以是0,1，…9），这些字符串至少有一个length >= k的“run”“运行”是连续递增/递减的数字序列，可以溢出/下溢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

我很难想出一个函数来检查'增加模10'。目前，这个函数很容易返回False。也许我错过了一个我还没有学会的标准技巧，或者有一个简单的递归方法来做到这一点？谢谢你的指导。你知道吗

这是我第一次问关于StackOverflow的问题。请告诉我以后怎样才能问得更好。你知道吗

Answer 1

当（a-b+10）%10等于1时，数字a、b按递增顺序排列；当（a-b+10）%10等于9时，数字a、b按递减顺序排列。任何其他值都表示它们不是按顺序排列的。你知道吗

您可以创建一个成对的字典来判断两个连续字符是递增（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）时间内运行。当它在字符串的早期找到一个请求长度的运行时，它通常会比其他两个运行的速度更快。这是因为它立即停止迭代，并且不处理字符串的其余部分。