执行操作后字典序最小的字符串【LC1625】
给你一个字符串
s以及两个整数a和b。其中，字符串s的长度为偶数，且仅由数字0到9组成。你可以在
s上按任意顺序多次执行下面两个操作之一：
- 累加：将
a加到s中所有下标为奇数的元素上（下标从 0 开始）。数字一旦超过9就会变成0，如此循环往复。例如，s = "3456"且a = 5，则执行此操作后s变成"3951"。- 轮转：将
s向右轮转b位。例如，s = "3456"且b = 1，则执行此操作后s变成"6345"。请你返回在
s上执行上述操作任意次后可以得到的 字典序最小 的字符串。如果两个字符串长度相同，那么字符串
a字典序比字符串b小可以这样定义：在a和b出现不同的第一个位置上，字符串a中的字符出现在字母表中的时间早于b中的对应字符。例如，"0158”字典序比"0190"小，因为不同的第一个位置是在第三个字符，显然'5'出现在'9'之前。
做着做着忘记累加奇数位偶数位的次数分别相同了，然后就WA了
感觉最近的中等题都很难呀
- 思路
- 首先，如果b为偶数，那么我们只能对奇数位做累加操作；如果b为奇数，那么我们能对所有数字进行累加操作【轮转后奇偶性相反】
那么我们可以使用BFS暴力搜索所有可能的状态，然后取字典序最小的状态即可
- 从队列中取出字符串，将其与答案进行比较，如果当前字符串字典序更小，那么更新答案
- 然后对该字符串进行累加和轮转操作，直至得到新的字符串
- 如果新的字符串没有出现过，那么将其入队，并更新哈希表
- 重复以上操作，直至队列为空
- 实现
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(b) + s.substring(0, b); for (String t : List.of(t1, t2)) { if (vis.add(t)) { q.offer(t); } } } return ans; } } 作者：ylb 链接：https://leetcode.cn/problems/lexicographically-smallest-string-after-applying-operations/solutions/2177449/python3javacgo-yi-ti-shuang-jie-bfs-bao-xl8n2/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
