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,high1): 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之间 # 从起点不断拼接下一位last1直到超过 high 停止 ans [] for x in range(1,10): star_number x next_number x1 # 易错点1先定义两个位数值所有都进入循环 while while star_number high and next_number 9: star_number star_number*10next_number if low star_number high: ans.append(star_number) # 易错点2:前一位已经通过更新变化了后一位也要变化1 next_number next_number1 # 易错点3:排序后输出 ans.sort() return ans不用遍历 low~high 每个数字判断数字范围大时低效直接按起点生成所有合法顺次数再筛选落在 [low,high] 的数起点只能是 1~9首位不能 0从起点不断拼接下一位last1直到超过 high 停止收集所有生成的顺次数过滤区间最后排序返回。生成逻辑num * 10 next_digitstart1next2110212next312103123优势生成量极少最多几十个数远小于遍历全部数字