1625.执行操作后字典序最小的字符串

发表于 分类于 阅读次数：

前言

题目来自LeetCode：https://leetcode.cn/problems/lexicographically-smallest-string-after-applying-operations/

题目（难度：中等）

给你一个字符串 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：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：s = "5525", a = 9, b = 2
输出："2050"
解释：执行操作如下：
初态："5525"
轮转："2555"
累加："2454"
累加："2353"
轮转："5323"
累加："5222"
累加："5121"
轮转："2151"
累加："2050"​​​​​​​​​​​​
无法获得字典序小于 "2050" 的字符串。

提示：

  • 2 <= s.length <= 100
  • s.length 是偶数
  • s 仅由数字 0 到 9 组成
  • 1 <= a <= 9
  • 1 <= b <= s.length - 1

题解

因为字符串s的长度是偶数，如果轮转数b是偶数，那么起始位置的字符奇偶性是不变的，也就是说怎样轮转，起始偶数下标的数一定不会加上a。轮转的话，在n次之后是一定会轮转回原串s。那么我们就可以枚举轮转的情况，直到轮转回s结束。
那么加上一个数多少次一轮回呢？
假设要被加数为x，加数为a，那么加了k次之后就是x + ka，因为超过9要变为0，那么加了k次之后就是(x + ka) % 10,根据取余的定理，(x + ka) % 10 -> x % 10 + ka % 10，因为x小于10，最终加了k次后变成x + ka % 10，而且a <= 9,那么要变回x的最小k就是10，也就是说x加上10次a一定会变回x。
那么每次轮转的情况下枚举9次加a的情况，找到最小的字典序即可（当然，当b为奇数的时候，偶数下标也是可以加a的，所以枚举要加上偶数下标的）。

代码 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public String findLexSmallestString(String s, int a, int b) {
        int n = s.length();
        //标记开始下标，如果访问到枚举过的下标，证明轮转的原来的字符串
        boolean[] vis = new boolean[n];
        String res = s;
        //延长一倍的s，容易截取轮转后的新字符串
        s = s + s;
        //枚举轮转
        for (int i = 0; !vis[i]; i = (i + b) % n) {
            vis[i] = true;
            //枚举奇数下标加a
            for (int j = 0; j < 10; j++) {
                //如果b不是偶数则需要枚举偶数下标的数加a
                int kLimit = b % 2 == 0 ? 0 : 9;
                //k = 0,相当于只在枚举奇数下标，k = 9相当于偶数下标也枚举
                for (int k = 0; k <= kLimit; k++) {
                    char[] t = s.substring(i, i + n).toCharArray();
                    for (int p = 1; p < n; p += 2) {
                        t[p] = (char) ('0' + (t[p] - '0' + j * a) % 10);
                    }
                    for (int p = 0; p < n; p += 2) {
                        t[p] = (char) ('0' + (t[p] - '0' + k * a) % 10);
                    }
                    String tStr = new String(t);
                    if (tStr.compareTo(res) < 0) {
                        res = tStr;
                    }
                }
            }
        }
        return res;
    }
}