leetcode刷题笔记（中等）1291顺次数

一、问题描述

二、我的超时思路（暴力）

class Solution: def sequentialDigits(self, low: int, high: int) -> List[int]: # 暴力字符超时（暴力数字也超时） # 思路及关注点： # 1.进入循环取当前值长度。 # 2.做位数计算时for循环从1开始。 # 3.位数相减！=1时跳出，但位数转int类型。 # 4.将符合的字符串存入，最后统一返回。 # 5.针对个人：True False break ans = [] for num in range(low,high+1): s = str(num) flag = True for i in range(1,len(s)): if int(s[i])-int(s[i-1]) != 1: flag = False break if flag == True: ans.append(num) return ans

三、可通过代码

class Solution: def sequentialDigits(self, low: int, high: int) -> List[int]: # 思路： # 1.首位可能性：1-9 # 2.依次递增，判断是否在low和hight之间 # 从起点不断拼接下一位（last+1），直到超过 high 停止 ans = [] for x in range(1,10): star_number = x next_number = x+1 # 易错点1：先定义两个位数值，所有都进入循环 while while star_number <high and next_number <=9: star_number =star_number*10+next_number if low <= star_number <= high: ans.append(star_number) # 易错点2:前一位已经通过更新变化了，后一位也要变化+1 next_number = next_number+1 # 易错点3:排序后输出 ans.sort() return ans

不用遍历 low~high 每个数字判断（数字范围大时低效），直接按起点生成所有合法顺次数，再筛选落在 [low,high] 的数：

1. 起点只能是 1~9（首位不能 0）；
2. 从起点不断拼接下一位（last+1），直到超过 high 停止；
3. 收集所有生成的顺次数，过滤区间，最后排序返回。

• 生成逻辑num * 10 + next_digitstart=1，next=2：110+2=12；next=3：1210+3=123；
• 优势：生成量极少，最多几十个数，远小于遍历全部数字；