如果一个整数在其十进制表示中至少有三个连续的升序数字，则它是一个特殊数字。
连续顺序中的三位数字必须大于零。
例如：123、45123、245789、123456789、12345为special号，012、1012、1245为not special号。
我必须计算在给定的S到E之间的范围内存在的特殊数字的数量。(1 <= S,E <= 10^18)
暴力方法可以迭代所有数字，并检查每个数字的数字。但我正在寻找一种跳过一些数字并且比暴力方法具有更好的时间复杂性的方法。
是否存在此类解决方案？
是否存在此类解决方案？
这样的解决方案当然存在，并且即使S和E比10**18大得多，也可以有效地计算S和E之间的特殊数字。例如，我们将在下面看到，正好有26854019828391474979539976989876500770006474049724特殊数字小于10**50，因此大约有四分之一的50位数字是特殊的。
我将概述解决方案的想法，然后用Python给出一些代码。
首先是简单的部分：对于任何非负整数n，能够计算range(n)中的特殊数就足够了。也就是说，我们只需要一个函数：
def count_special_below(n: int) -> int:
"""
Return count of special numbers m satisfying 0 <= m < n.
"""
# See below for implementation
给定count_special_below(我们稍后将对其进行适当定义)，我们可以通过以下函数轻松地找到任何给定范围内的特殊数字的计数：
def count_special_between(start: int, end: int) -> int:
"""
Return count of special numbers m satisfying start <= m <= end.
"""
return count_special_below(end + 1) - count_special_below(start)
这个想法
我们将把非负整数分成几个类。其中一个类别将是特殊号码；其余的将是各种形式的非特殊数字。除法是以这样一种方式进行的，即当我们添加给定的数字时，我们知道任何给定整数的类是如何变化的。
具体来说，我们定义了十六个互斥类，编号从0到15，如下所示：
- 类15包含所有特殊数字
- 类14包含所有以数字"78"结尾的非特殊数字
- 类13包含所有以数字"67"结尾的非特殊数字
- 类12包含所有以数字"56"结尾的非特殊数字
- 类11包含所有以数字"45"结尾的非特殊数字
- 类10包含所有以数字"34"结尾的非特殊数字
- 类9包含所有以数字"23"结尾的非特殊数字
- 类8包含所有以数字"12"结尾的非特殊数字
- 类7包含所有以"7"结尾但不以"67"结尾的非特殊数字
- 类6包含所有以"6"结尾但不以"56"结尾的非特殊数字
- 类5包含所有以"5"结尾但不以"45"结尾的非特殊数字
- 类4包含所有以"4"结尾但不以"34"结尾的非特殊数字
- 类3包含所有以"3"结尾但不以"23"结尾的非特殊数字
- 类2包含所有以"2"结尾但不以"12"结尾的非特殊数字
- 类1包含所有以"1"结尾的非特殊数字
- 类0包含所有以"8"、"9"或"0"结尾但不以"78"结尾的非特殊数字
这些类的意义在于，如果某些q和r的n = 10*q = r，那么我们可以只知道q的类和r的值来计算n的类：我们不需要知道q本身。
例如，如果q在类9和r = 4中，那么n = 10*q + r在类15中：这是特殊的。而如果q在9和r = 5类中，则n在5类中，并且如果q在9和r = 0类中，那么n在0类中。
我们可以遍历所有160个(类、数字)组合来计算转换，然后将这些转换记录在一个简单的列表中。
现在我们可以放大：再次假设n = 10*q + r，并且我们已经计算(例如递归地)了range(q)中属于16个类中每一个的整数的数量。然后，我们可以使用转移矩阵来计算range(n)中属于16个类中每一个类的整数的数量。
例如，如果n = 135457、q = 13545和r = 7，则range(q)中的类9的值的数目变为121。这些121值中的每一个都通过附加一个4来为range(135457)贡献恰好一个特殊数字。还有类别8的135值，它们同样各自贡献range(135457)中的一个特殊数字。通过添加贡献，并注意考虑范围range(135450, 135457)，我们得到了range(135457)中每个类的总数。
Python代码
这是迭代形式的代码。递归地表达它比迭代更自然，但对于非常大的起始值和结束值(例如有数千个数字)，我们会遇到Python的递归限制。
首先是转换矩阵：这是一个列表列表，行对应于十六个类，列对应于数字。如果q具有类别c，则10*q + r具有类别transitions[c][r]。
transitions = [
[0, 1, 2, 3, 4, 5, 6, 7, 0, 0],
[0, 1, 8, 3, 4, 5, 6, 7, 0, 0],
[0, 1, 2, 9, 4, 5, 6, 7, 0, 0],
[0, 1, 2, 3, 10, 5, 6, 7, 0, 0],
[0, 1, 2, 3, 4, 11, 6, 7, 0, 0],
[0, 1, 2, 3, 4, 5, 12, 7, 0, 0],
[0, 1, 2, 3, 4, 5, 6, 13, 0, 0],
[0, 1, 2, 3, 4, 5, 6, 7, 14, 0],
[0, 1, 2, 15, 4, 5, 6, 7, 0, 0],
[0, 1, 2, 3, 15, 5, 6, 7, 0, 0],
[0, 1, 2, 3, 4, 15, 6, 7, 0, 0],
[0, 1, 2, 3, 4, 5, 15, 7, 0, 0],
[0, 1, 2, 3, 4, 5, 6, 15, 0, 0],
[0, 1, 2, 3, 4, 5, 6, 7, 15, 0],
[0, 1, 2, 3, 4, 5, 6, 7, 0, 15],
[15, 15, 15, 15, 15, 15, 15, 15, 15, 15],
]
现在完整的count_special_below功能：
def count_special_below(n: int) -> int:
"""
Return count of special numbers m satisfying 0 <= m < n.
"""
n_counts, n_cls = [0] * 16, 0
for digit in map(int, str(n)):
m_counts = [0] * 16
for tc, count in zip(transitions, n_counts):
for tcs in tc:
m_counts[tcs] += count
for t in transitions[n_cls][:digit]:
m_counts[t] += 1
n_counts, n_cls = m_counts, transitions[n_cls][digit]
return n_counts[15]
测试解决方案
出于测试目的，我们还定义一个暴力版本：
def is_special(n: int) -> bool:
"""
Return True if n is special, else False.
"""
s = str(n)
return any(
substr in s
for substr in ["123", "234", "345", "456", "567", "678", "789"]
)
def count_special_between_brute(start: int, end: int) -> int:
"""
Return count of special numbers m satisfying start <= m <= end.
"""
return sum(is_special(n) for n in range(start, end + 1))
一些测试，数量较小：
>>> count_special_between(125, 289901)
7593
>>> count_special_between_brute(125, 289901)
7593
>>> count_special_between(0, 10**7)
324691
>>> count_special_between_brute(0, 10**7)
324691
但我们的新功能在更大的数字下也能很好地发挥作用：
>>> count_special_between(0, 10**50)
26854019828391474979539976989876500770006474049724
即使在我的机器上计算10**10000以下的特殊数字也只需要一两秒钟，但由于答案正好是10000数字(毫不奇怪，因为"大多数"大数字都是特殊的)，我不会在这里包括它。
与正则表达式的连接
众所周知，通过正则表达式(在严格的数学意义上)进行匹配可以通过确定性有限自动机(DFA)来实现。如果我们认为"特殊数"适用于数字字符串而不是整数，我们可以编写一个简单的正则表达式来匹配特殊数：
special = "[0-9]*(123|234|345|456|567|678|789)[0-9]*"
该正则表达式可以被编译为具有恰好16个状态的DFA，对应于上述的16个类。事实上，如果我们使用Python包greenery(我刚刚发现)，我们可以显式地看到编译。(我在下面的会话中编辑了空白，使其更可读，但在其他方面没有改变。)
>>> from greenery.lego import parse
>>> p = parse("[0-9]*(123|234|345|456|567|678|789)[0-9]*")
>>> p.to_fsm()
fsm(
alphabet = {'2', '1', '7', anything_else, '0', '4', '8', '3', '5', '6', '9'},
states = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15},
initial = 0,
finals = {15}, map = {
0: {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 0, '9': 0},
1: {'0': 0, '1': 1, '2': 8, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 0, '9': 0},
2: {'0': 0, '1': 1, '2': 2, '3': 9, '4': 4, '5': 5, '6': 6, '7': 7, '8': 0, '9': 0},
3: {'0': 0, '1': 1, '2': 2, '3': 3, '4': 10, '5': 5, '6': 6, '7': 7, '8': 0, '9': 0},
4: {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 11, '6': 6, '7': 7, '8': 0, '9': 0},
5: {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 12, '7': 7, '8': 0, '9': 0},
6: {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 13, '8': 0, '9': 0},
7: {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 14, '9': 0},
8: {'0': 0, '1': 1, '2': 2, '3': 15, '4': 4, '5': 5, '6': 6, '7': 7, '8': 0, '9': 0},
9: {'0': 0, '1': 1, '2': 2, '3': 3, '4': 15, '5': 5, '6': 6, '7': 7, '8': 0, '9': 0},
10: {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 15, '6': 6, '7': 7, '8': 0, '9': 0},
11: {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 15, '7': 7, '8': 0, '9': 0},
12: {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 15, '8': 0, '9': 0},
13: {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 15, '9': 0},
14: {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 0, '9': 15},
15: {'0': 15, '1': 15, '2': 15, '3': 15, '4': 15, '5': 15, '6': 15, '7': 15, '8': 15, '9': 15}})
检查将验证上面的map实际上与我们之前创建的转换表完全对应。