leetcode 1625. 执行操作后字典序最小的字符串-爱代码爱编程
【LetMeFly】1625.执行操作后字典序最小的字符串
力扣题目链接: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:
输入: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 = "43987654", a = 7, b = 3 输出:"00553311"
提示:
2 <= s.length <= 100
s.length
是偶数s
仅由数字0
到9
组成1 <= a <= 9
1 <= b <= s.length - 1
方法一:模拟
我们只需要明白:
- 因为轮转不可能产生无限多种字符串,所以轮转所产生的字符串是在不断循环地
- 因为我们只能同时改变偶数位置的字符,所以对于一个轮转后的字符串,我们要让下标为1的字符尽可能地小
- 因为字符串长度为偶数,所以如果轮转距离b是奇数,则奇数位置的字符下标也有机会到达偶数;反之奇数下标永远只能处于奇数的位置。
这样,我们就能开开心心地模拟了。
首先模拟所有的“轮转结果”(最多有len(s)种)
对于每种轮转结果,我们让其下标1处的字符加上数个a后尽可能地小,然后让所有奇数下标的字符加上相同数量的a。如果b为奇数,则再让下标0处的字符加上数个a后尽可能小,并将所有偶数下标的字符加上相同数量的a。
对于每种轮转结果,得到加最优a后的字符串后,在所有字符串中最小的一个即为答案。
- 时间复杂度 O ( l e n ( s ) 2 × C ) O(len(s)^2\times C) O(len(s)2×C),其中 C = 10 C=10 C=10。最多需要 l e n ( s ) len(s) len(s)次轮转,对于每次轮转需要 l e n ( s ) × C len(s)\times C len(s)×C的复杂度完成“加a”、比较等操作。最多加上10次a即可找到最优的加a次数。
- 空间复杂度 O ( l e n ( s ) ) O(len(s)) O(len(s))
AC代码
C++
class Solution {
private:
int add2minStep(char original, int a) { // 将original加数次a,使得original尽可能小,需要加几次
int ans = 0;
int step = 0;
int m = original - '0';
int n = original - '0';
do {
n = (n + a) % 10;
step++;
if (n < m) {
m = n;
ans = step;
}
} while (a * step % 10);
return ans;
}
string change2loc2min(string& s, int a, int b, int l) { // 将s的l、l + 1两个位置变得尽可能小并移动到最前
string ans = s.substr(l, s.size() - l) + s.substr(0, l);
if (b % 2) {
int m1 = add2minStep(ans[0], a);
for (int i = 0; i < s.size(); i += 2) {
ans[i] = (char)((ans[i] - '0' + a * m1) % 10 + '0');
}
}
int m2 = add2minStep(ans[1], a);
for (int i = 1; i < s.size(); i += 2) {
ans[i] = (char)((ans[i] - '0' + a * m2) % 10 + '0');
}
return ans;
}
public:
string findLexSmallestString(string& s, int a, int b) {
string ans = s;
int totalRotate = b;
do {
// string thisStr = change2loc2min(s, a, b, s.size() - totalRotate); cout << thisStr << endl; //**********
ans = min(ans, change2loc2min(s, a, b, s.size() - totalRotate));
totalRotate = (totalRotate + b) % s.size();
} while (totalRotate != b);
return ans;
}
};
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/129651164