难度: Medium
Submission
运行时间: 66 ms
内存: 16.5 MB
class Solution:
def countSteppingNumbers(self, low: int, high: int) -> List[int]:
def gen():
curDigit = 1
base = 10
byStarts = [[i] for i in range(10)]
for i in range(10):
yield i
byStarts1 = [[] for i in range(10)]
for curDigit in count(2):
for digit in range(10):
digitBase = digit*base
byStarts1[digit].clear()
lst = []
if digit > 0:
lst.append(byStarts[digit-1])
if digit < 9:
lst.append(byStarts[digit+1])
for v in chain.from_iterable(lst):
v += digitBase
byStarts1[digit].append(v)
if digit:
yield v
base*=10
byStarts, byStarts1 = byStarts1, byStarts
res = []
for v in gen():
if v >high: break
if v >= low:
res.append(v)
return res
Explain
这个题解使用了生成器方法来产生步进数。步进数是那些相邻数字位只差1的数。首先，它初始化一个由单个数字构成的步进数列表，并逐步构建更长的步进数。方法是对每个数字位，考虑它的前一个和后一个数字，通过连接操作形成新的步进数，并检查这些生成的数字是否位于给定的范围[low, high]内。
时间复杂度: O(D * 10^D)，其中D是high的位数
空间复杂度: O(10^D)，其中D是high的位数
class Solution:
def countSteppingNumbers(self, low: int, high: int) -> List[int]:
def gen():
# 初始设置，每个数字自身是一个步进数
curDigit = 1
base = 10
byStarts = [[i] for i in range(10)]
for i in range(10):
yield i # 生成0-9的所有单个数字
byStarts1 = [[] for i in range(10)]
for curDigit in count(2):
for digit in range(10):
digitBase = digit*base
byStarts1[digit].clear()
lst = []
if digit > 0: # 检查下一个数字是否符合步进数要求
lst.append(byStarts[digit-1])
if digit < 9: # 检查上一个数字是否符合步进数要求
lst.append(byStarts[digit+1])
for v in chain.from_iterable(lst):
v += digitBase # 生成新的步进数
byStarts1[digit].append(v)
if digit:
yield v # 生成并返回符合条件的步进数
base*=10
byStarts, byStarts1 = byStarts1, byStarts # 更新列表以便下一轮使用
res = []
for v in gen():
if v >high: break # 超出范围则停止
if v >= low:
res.append(v) # 收集结果范围内的步进数
return res
Explore
生成器通过构建过程确保每个生成的数字都是步进数。它从已知的步进数（最初是单个数字0-9）开始，然后每一步生成新的步进数，确保新的数的每一位与前一位的数字只差1。这是通过检查当前数字位的前一个和后一个数字（如果存在）并将它们附加到已知的步进数上来实现的。因此，每次扩展都严格遵循步进数的定义，从而确保生成的数字不是随机的，而是符合步进数的要求。
在生成步进数时，一旦生成的数超过了给定的上限high，生成过程就会立即停止。这是通过在生成器中设置一个检查点实现的，一旦生成的步进数超过high，就会中断循环，从而停止生成更多的数字。这种方法有效地减少了不必要的计算和资源消耗，因为一旦超出范围，后续生成的更大的数字也不会符合条件。
在算法中，`byStarts` 和 `byStarts1` 列表用于存储当前和下一轮的步进数。每完成一轮步进数的生成后，这两个列表会交换角色：当前轮的结果列表（`byStarts`）成为下一轮的起始列表（`byStarts1`变为`byStarts`），而原始的起始列表则被清空并准备用于存放下一轮的结果。这种交替使用策略避免了每次生成新步进数时都需要创建新的列表的开销，从而提高了算法的空间效率和执行速度。
在算法中，`base` 用于帮助生成下一位数字的步进数。每当算法过渡到新的数位长度时，`base` 就会乘以10。这样做是为了在生成新的步进数时能够将前一步的数字扩展到正确的数位。例如，从数字9扩展到数字90或91，`base` 的值从1变为10，然后是100等等。这保证了每次附加的数字都放在正确的数位上，从而成功生成更长的步进数。