题目描述
思路解析动画文字版
记牢这套:把串当节点、两种操作当出边,BFS 逐个出队;每出队一个就更新最小答案,再把它的两个邻居里没访问过的入队,visited 判重。下面每一帧都在套它。
先看画面怎么摆。上面这排是当前要处理的串,这会儿是初始串 「74」。下标 0 是偶数位 7,累加操作永远不碰它;下标 1 是奇数位 4,累加会落在它头上。右边「已访问 visited」是判重集合,现在只装着起点 「74」。队列里也只有 「74」 一个,当前最优答案先记成 「74」。
从队头取出 「74」 来处理。先拿它和当前最优比一比,它就是最优本身,不更小,最优保持 「74」 不变。接着要对它做两种操作,生成两个邻居。
第一种操作:累加。只动奇数下标 1 上的数字,4 加 5 等于 9,没超过 9 不用绕回,偶数位 7 原样不动,得到 「79」。visited 里没有 「79」,是个新串,标成已访问并塞进队尾。
第二种操作:右移 1 位,把末尾 1 个字符 4 搬到最前面,「74」 变成 「47」。visited 里也没有 「47」,新串,标记已访问、入队。现在队列里排着 「79」 和 「47」。
出队下一个 「79」。和当前最优 「74」 比,「79」 大于 「74」,字典序更大,最优不更新,仍是 「74」。再对它做两种操作。
对 「79」 累加:奇数位 9 加 5 等于 14,超过 9 了,对 10 取余落回成 4,得到 「74」。可是 「74」 早就在 visited 里了,说明绕回了起点,跳过不再入队。这一步正是判重在拦环。
对 「79」 右移 1 位,末尾的 9 挪到最前,得到 「97」。visited 里没有 「97」,新串,入队。
出队 「47」。和当前最优 「74」 比,第一位 4 就小于 7,「47」 字典序更小,最优更新成 「47」。这是第一次刷新答案。
对 「47」 累加:奇数位 7 加 5 等于 12,取余落回 2,偶数位 4 不动,得到 「42」。新串,入队。
对 「47」 右移 1 位,末尾 7 搬到前面,变回 「74」。又是起点,visited 里有,跳过。
出队 「97」。和当前最优 「47」 比,第一位 9 大于 4,更大,最优不更新,仍是 「47」。
对 「97」 累加:奇数位 7 加 5 等于 12,取余成 2,得到 「92」。新串,入队。
对 「97」 右移 1 位,末尾 7 挪到前面,得到 「79」。visited 里已经有 「79」,跳过。
出队 「42」。和当前最优 「47」 比,前两位都比一比,第一位都是 4,第二位 2 小于 7,所以 「42」 更小,最优更新成 「42」。
对 「42」 累加:奇数位 2 加 5 等于 7,得到 「47」。「47」 之前访问过了,跳过。
对 「42」 右移 1 位,末尾 2 搬到最前,得到 「24」。这是个新串,入队。注意这个 「24」 正是最后的答案,但搜索还没结束,先继续走。
出队 「92」。和当前最优 「42」 比,第一位 9 大于 4,更大,最优不更新。
对 「92」 累加:奇数位 2 加 5 等于 7,得到 「97」。访问过了,跳过。
对 「92」 右移 1 位,末尾 2 挪到前,得到 「29」。新串,入队。到这儿可达串已经凑齐 8 个了。
出队 「24」。和当前最优 「42」 比,第一位 2 小于 4,「24」 更小,最优更新成 「24」。这就是最终答案了,不过队列还没空,得把流程走完才能确定。
对 「24」 做两种操作:累加得到 「29」,右移得到 「42」。这两个串 visited 里都有,全部跳过,不再产生新节点。visited 已经集满 8 个串,搜索快到头了。
出队最后一个 「29」。和当前最优 「24」 比,第一位 2 相同,第二位 9 大于 4,更大,最优不更新。
对 「29」 累加得到 「24」、右移得到 「92」,两个都在 visited 里,全跳过。没有新串入队,队列就此清空。
队列空了,8 个可达串全都处理完,visited 里 「74」「79」「47」「97」「42」「92」「24」「29」 一个不少。整个过程里最优答案从 「74」 一路被刷新到 「47」、「42」、最后停在 「24」。所以从 「74」 出发能得到的字典序最小串就是 「24」,和开头说的对上了。
边界:「0011」 怎么操作都变大,初始串就是最小;「10」 先右移成 「01」 再给奇数位加 9 取余得 「00」;「00」 一加就变大,本身已最小。
三个追问:可达串数有限(O(n) 量级)所以 BFS 必停;换成 DFS 加 visited 答案一样;也能枚举旋转与累加次数直接构造,但 BFS 最直观不易错。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def findLexSmallestString(self, s: str, a: int, b: int) -> str: q = deque([s]) vis = {s} ans = s while q: s = q.popleft() if ans > s: ans = s t1 = ''.join( [str((int(c) + a) % 10) if i & 1 else c for i, c in enumerate(s)] ) t2 = s[-b:] + s[:-b] for t in (t1, t2): if t not in vis: vis.add(t) q.append(t) return ans复杂度
- 时间：O(n²) 级，设串长 n。右移最多产生 n 种不同旋转;给奇数位反复累加 a,不同结果最多 10 种,若 b 为奇数旋转会把奇偶位错开、偶数位也可能被累加,再多至多 10 倍。所以可达串数是 O(n) 量级(常数最多 100)。每个串生成、比较字典序、丢进哈希集合各要 O(n);BFS 每个串扩展 2 个邻居。合起来大约 O(n²) 级(含这个常数 100)
- 空间：O(n²) 级，按峰值算。visited 与队列里最多同时存下全部可达串,可达串数是 O(n) 量级,每个串长 n,所以存它们要 O(n) 乘以 n,即 O(n²) 级。这就是整个过程占用的内存峰值
易错点
面试追问把动画讲成自己的话
追问操作能用任意多次, 为什么 BFS 还能在有限步内停下来?
追问用深度优先搜索行不行?
追问能不能不搜索, 直接构造最优解?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
生成平衡数组的方案数
LeetCode 1664 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题