LeetCode 1215. [Python] Stepping Numbers
原题链接
中等
作者:
徐辰潇
,
2021-01-18 09:18:02
,
所有人可见
,
阅读 291
class Solution:
def countSteppingNumbers(self, low: int, high: int) -> List[int]:
#can be considered as a BFS
#TC: O(magic number)
#SC: O(magic number)
seg = [0,1,2,3,4,5,6,7,8,9]
res = []
mod = 10
for ele in seg:
if low <= ele <= high:
res.append(ele)
while(max(seg) < high):
seg_new = []
for ele in seg:
if ele == 0:
continue
remain = ele % mod
add = remain + 1
minus = remain - 1
if minus >= 0:
ele_new = ele*10 + minus
seg_new.append(ele_new)
if low <= ele_new <= high:
res.append(ele_new)
elif ele_new > high:
break
if add < 10:
ele_new = ele*10 + add
seg_new.append(ele_new)
if low <= ele_new <= high:
res.append(ele_new)
elif ele_new > high:
break
seg = seg_new.copy()
return res