题目
给你一个字符串 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’ 之前。
示例 1：
讯享网输入：s = "5525", a = 9, b = 2 输出："2050" 解释：执行操作如下： 初态："5525" 轮转："2555" 累加："2454" 累加："2353" 轮转："5323" 累加："5222" 累加："5121" 轮转："2151" 累加："2050" 无法获得字典序小于 "2050" 的字符串。
示例 2：
输入：s = "74", a = 5, b = 1 输出："24" 解释：执行操作如下： 初态："74" 轮转："47" 累加："42" 轮转："24" 无法获得字典序小于 "24" 的字符串。 示例 3：
讯享网输入：s = "0011", a = 4, b = 2 输出："0011" 解释：无法获得字典序小于 "0011" 的字符串。
示例 4：
输入：s = "", a = 7, b = 3 输出："00" 提示：
讯享网2 <= s.length <= 100 s.length 是偶数 s 仅由数字 0 到 9 组成 1 <= a <= 9 1 <= b <= s.length - 1
解题思路
比赛的时候没做出来，赛后看了下题解，发现一把子暴力可以做。。。
其实对字符串的操作就2个，一个是调整奇数位的数字，另外一个是轮转。所以直接暴力搜索所有可能的结果，再输出字典序最小的即可。
代码
class Solution: def findLexSmallestString(self, s: str, a: int, b: int) -> str: def change(s: str) -> str: s = list(map(int, list(s))) s = [(s[index] + (a if index & 1 == 1 else 0)) % 10 for index in range(len(s))] return ''.join(map(str, s)) def loop(s: str, loop: int) -> str: return s[loop:] + s[:loop] all_set = set() stack = [s] while stack: new_s = stack.pop() if new_s in all_set: continue all_set.add(new_s) stack += [change(new_s), loop(new_s, b % len(new_s))] return min(all_set)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/128145.html