枚举

长度为 n 的字符串，最多轮转 n 次。一个数位最多 10 个数字，所以奇数位最多累加 10 次。由于字符串长度 n 是偶数，若轮转单位 b 是偶数，偶数位只会在偶数位，所以无法执行累加；若轮转单位 b 为奇数，偶数位也可以变成奇数位，偶数位最多累加 10 次。

轮转次数 n ，奇数位累加次数 10，偶数位累加次数 10，每次操作改变所有数位共 n 位，四者是互斥关系，时间复杂度 O(n2×102)O(n ^ 2 \times 10^2)O(n2×102)

提示：本文算法是最暴力的枚举，这是由于字符串长度在 100 以内。还有很多性质可以分析，算法可以进一步优化。

class Solution {
public:string findLexSmallestString(string s, int a, int b) {// 最多轮转 n 次，每次轮转 b 位 // 奇数位最多累加 10 次，每次累加 a // 若 b 为偶数，偶数位无法执行累加；若 b 为奇数，偶数位最多累加 10 次， 每次累加 a。int n = s.size();string ans = s;int max_k = (b & 1) * 9 + 1;// 从不累加，到累加for (int i = 0; i < n; i ++) {for (int j = 0; j < 10; j ++) {for (int k = 0; k < max_k; k ++) {string t = s.substr((i * b) % n, n) + s.substr(0, (i * b) % n); // 轮转for (int p1 = 1; p1 < n; p1 += 2) {t[p1] = (t[p1] - '0' + j * a) % 10 + '0'; // 按位累加}for (int p2 = 0; p2 < n; p2 += 2) {t[p2] = (t[p2] - '0' + k * a) % 10 + '0';}ans = min(ans, t);}}}return ans;}
};

1. 时间复杂度 : O(n2×102)O(n ^ 2 \times 10^2)O(n2×102) ， nnn 是字符串的长度，轮转次数 n ，奇数位累加次数 10，偶数位累加次数 10，每次操作改变所有数位共 n 位，四者是互斥关系，时间复杂度 O(n2×102)O(n ^ 2 \times 10^2)O(n2×102)。
2. 空间复杂度 : O(n)O(n)O(n) ，临时字符串 ttt 的空间复杂度 O(n)O(n)O(n) 。

AC

致语

• 理解思路很重要
• 读者有问题请留言，清墨看到就会回复的。