执行操作后字典序最小的字符串 图解题解

这道题到底在问什么

输入

s = "5525", a = 9, b = 2

输出

"2050"

输入

s = "74", a = 5, b = 1

输出

"24"

输入

s = "0011", a = 4, b = 2

输出

"0011" (已经最小, 操作后都不会更小)

最优解：一步一步想明白

1. 3记牢这套:把串当节点、两种操作当出边,BFS 逐个出队;每出队一个就更新最小答案,再把它的两个邻居里没访问过的入队,visited 判重。下面每一帧都在套它。
2. 4先看画面怎么摆。上面这排是当前要处理的串,这会儿是初始串 「74」。下标 0 是偶数位 7,累加操作永远不碰它;下标 1 是奇数位 4,累加会落在它头上。右边「已访问 visited」是判重集合,现在只装着起点 「74」。队列里也只有 「74」 一个,当前最优答案先记成 「74」。
3. 5从队头取出 「74」 来处理。先拿它和当前最优比一比,它就是最优本身,不更小,最优保持 「74」 不变。接着要对它做两种操作,生成两个邻居。
4. 6第一种操作:累加。只动奇数下标 1 上的数字,4 加 5 等于 9,没超过 9 不用绕回,偶数位 7 原样不动,得到 「79」。visited 里没有 「79」,是个新串,标成已访问并塞进队尾。
5. 7第二种操作:右移 1 位,把末尾 1 个字符 4 搬到最前面,「74」 变成 「47」。visited 里也没有 「47」,新串,标记已访问、入队。现在队列里排着 「79」 和 「47」。
6. 8出队下一个 「79」。和当前最优 「74」 比,「79」 大于 「74」,字典序更大,最优不更新,仍是 「74」。再对它做两种操作。
7. 9对 「79」 累加:奇数位 9 加 5 等于 14,超过 9 了,对 10 取余落回成 4,得到 「74」。可是 「74」 早就在 visited 里了,说明绕回了起点,跳过不再入队。这一步正是判重在拦环。
8. 10对 「79」 右移 1 位,末尾的 9 挪到最前,得到 「97」。visited 里没有 「97」,新串,入队。
9. 11出队 「47」。和当前最优 「74」 比,第一位 4 就小于 7,「47」 字典序更小,最优更新成 「47」。这是第一次刷新答案。
10. 12对 「47」 累加:奇数位 7 加 5 等于 12,取余落回 2,偶数位 4 不动,得到 「42」。新串,入队。
11. 13对 「47」 右移 1 位,末尾 7 搬到前面,变回 「74」。又是起点,visited 里有,跳过。
12. 14出队 「97」。和当前最优 「47」 比,第一位 9 大于 4,更大,最优不更新,仍是 「47」。
13. 15对 「97」 累加:奇数位 7 加 5 等于 12,取余成 2,得到 「92」。新串,入队。
14. 16对 「97」 右移 1 位,末尾 7 挪到前面,得到 「79」。visited 里已经有 「79」,跳过。
15. 17出队 「42」。和当前最优 「47」 比,前两位都比一比,第一位都是 4,第二位 2 小于 7,所以 「42」 更小,最优更新成 「42」。
16. 18对 「42」 累加:奇数位 2 加 5 等于 7,得到 「47」。「47」 之前访问过了,跳过。
17. 19对 「42」 右移 1 位,末尾 2 搬到最前,得到 「24」。这是个新串,入队。注意这个 「24」 正是最后的答案,但搜索还没结束,先继续走。
18. 20出队 「92」。和当前最优 「42」 比,第一位 9 大于 4,更大,最优不更新。
19. 21对 「92」 累加:奇数位 2 加 5 等于 7,得到 「97」。访问过了,跳过。
20. 22对 「92」 右移 1 位,末尾 2 挪到前,得到 「29」。新串,入队。到这儿可达串已经凑齐 8 个了。
21. 23出队 「24」。和当前最优 「42」 比,第一位 2 小于 4,「24」 更小,最优更新成 「24」。这就是最终答案了,不过队列还没空,得把流程走完才能确定。
22. 24对 「24」 做两种操作:累加得到 「29」,右移得到 「42」。这两个串 visited 里都有,全部跳过,不再产生新节点。visited 已经集满 8 个串,搜索快到头了。
23. 25出队最后一个 「29」。和当前最优 「24」 比,第一位 2 相同,第二位 9 大于 4,更大,最优不更新。
24. 26对 「29」 累加得到 「24」、右移得到 「92」,两个都在 visited 里,全跳过。没有新串入队,队列就此清空。
25. 27队列空了,8 个可达串全都处理完,visited 里 「74」「79」「47」「97」「42」「92」「24」「29」 一个不少。整个过程里最优答案从 「74」 一路被刷新到 「47」、「42」、最后停在 「24」。所以从 「74」 出发能得到的字典序最小串就是 「24」,和开头说的对上了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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 = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class 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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    string findLexSmallestString(string s, int a, int b) {
        queue<string> q{{s}};
        unordered_set<string> vis{{s}};
        string ans = s;
        int n = s.size();
        while (!q.empty()) {
            s = q.front();
            q.pop();
            ans = min(ans, s);
            string t1 = s;
            for (int i = 1; i < n; i += 2) {
                t1[i] = (t1[i] - '0' + a) % 10 + '0';
            }
            string t2 = s.substr(n - b) + s.substr(0, n - b);
            for (auto& t : {t1, t2}) {
                if (!vis.count(t)) {
                    vis.insert(t);
                    q.emplace(t);
                }
            }
        }
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public String findLexSmallestString(String s, int a, int b) {
        Deque<String> q = new ArrayDeque<>();
        q.offer(s);
        Set<String> vis = new HashSet<>();
        vis.add(s);
        String ans = s;
        int n = s.length();
        while (!q.isEmpty()) {
            s = q.poll();
            if (ans.compareTo(s) > 0) {
                ans = s;
            }
            char[] cs = s.toCharArray();
            for (int i = 1; i < n; i += 2) {
                cs[i] = (char) (((cs[i] - '0' + a) % 10) + '0');
            }
            String t1 = String.valueOf(cs);
            String t2 = s.substring(n - b) + s.substring(0, n - b);
            for (String t : Arrays.asList(t1, t2)) {
                if (vis.add(t)) {
                    q.offer(t);
                }
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问