class Solution {
public:
string findLexSmallestString(string s, int a, int b) {
}
};
1625. 执行操作后字典序最小的字符串
给你一个字符串 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 <= 100s.length 是偶数s 仅由数字 0 到 9 组成1 <= a <= 91 <= b <= s.length - 1原站题解
python3 解法, 执行用时: 988 ms, 内存消耗: 33.3 MB, 提交时间: 2022-12-09 12:01:24
class Solution:
def findLexSmallestString(self, s: str, a: int, b: int) -> str:
n = len(s)
b %= n
ss = set()
res = "1" + '0' * 101 # 最多是1e100
def backtrace(ts):
nonlocal res, ss
if int(res) > int(ts):
res = ts
if ts in ss: # 如果一个情况之前遇到过，说明可以终结循环了 暂时没想到减枝的方法
return
ss.add(ts)
backtrace(ts[b:]+ts[:b]) # 1.先搜索旋转的情况
ts = list(ts)
for i in range(1, n, 2): # 为所有奇位加上a
ts[i] = str((int(ts[i]) + a) % 10)
ts = ''.join(ts)
backtrace(ts) # 2.然后遍历奇位加上a的情况
backtrace(s)
return res
python3 解法, 执行用时: 1044 ms, 内存消耗: 32.2 MB, 提交时间: 2022-12-09 12:00:35
'''
模拟两个操作为子函数，暴力所有操作的结果，这里使用set存放，最后返回最小值即可，算法复杂度较高，好理解能ac
'''
class Solution:
def findLexSmallestString(self, s: str, a: int, b: int) -> str:
b = b%len(s)
def addOpt(s):
ans = [c for c in s]
for i in range(1,len(s),2):
ans[i]=str((int(s[i])+a))[-1]
return ''.join(ans)
def lunOpt(s):
return s[-b:]+s[:-b]
alls = {s}
def dfs(s):
alls.add(s)
s1 = addOpt(s)
s2 = lunOpt(s)
if s1 not in alls:
dfs(s1)
if s2 not in alls:
dfs(s2)
dfs(s)
return min(alls)
cpp 解法, 执行用时: 32 ms, 内存消耗: 6.9 MB, 提交时间: 2022-12-09 11:59:39
class Solution {
public:
string findLexSmallestString(string s, int a, int b) {
string anw = s;
for(int i = 0; i <= s.size(); i++) {
// 轮转
s = s.substr(b, s.size()) + s.substr(0, b);
// 修改奇数位置
for(int j = 0; j < 10; j++) {
for(int k = 1; k < s.size(); k += 2) {
s[k] += a;
if(s[k] > '9') {
s[k] = '0' + (s[k]-'9'-1);
}
}
if(b%2) {
// b为奇数，此时通过轮转，也能修改偶数位置
for(int m = 0; m < 10; m++) {
for(int k = 0; k < s.size(); k += 2) {
s[k] += a;
if(s[k] > '9') {
s[k] = '0' + (s[k]-'9'-1);
}
}
anw = min(anw, s);
}
} else {
anw = min(anw, s);
}
}
}
return anw;
}
};
cpp 解法, 执行用时: 160 ms, 内存消耗: 74.2 MB, 提交时间: 2022-12-09 11:58:30
class Solution {
public:
string findLexSmallestString(string s, int a, int b) {
unordered_set<string> vis;//记录已经出现的状态
string cur, nt, minstr = s;
int i, n = s.size(), bit;
vis.insert(s);
queue<string> q;
q.push(s);
while(!q.empty())
{
cur = q.front();
q.pop();
if(cur < minstr)
minstr = cur;
nt = cur;
for(i = 1; i < n; i+=2)
{ //奇数位加 a
bit = (cur[i]-'0'+a)%10;
nt[i] = bit+'0';
}
if(!vis.count(nt))
{
vis.insert(nt);
q.push(nt);
}
// 向右轮转
nt = cur.substr(n-b)+cur.substr(0,n-b);
if(!vis.count(nt))
{
vis.insert(nt);
q.push(nt);
}
}
return minstr;
}
};
cpp 解法, 执行用时: 4 ms, 内存消耗: 6.3 MB, 提交时间: 2022-12-09 11:57:50
/**
* 暴力枚举优化
* 事实上，对于每一个轮转，我们只需要让其第一个奇数位，也即p[1]达到最小；
* 当然，如果可以对偶数位进行操作，则需要再考虑让p[0]达到最小。
* 这样，对奇偶的讨论就变成了并联而非串联的关系。
* 在确定了奇数位（和偶数位）的操作次数后，对于每一轮转，我们只会生成一个唯一的新字符串。
**/
class Solution {
int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
public:
string findLexSmallestString(string s, int a, int b) {
int n = s.size();
string ans = s;
string t = s + s;
int ga = gcd(10, a), gb = gcd(n, b);
// 奇偶通用的add操作
auto add = [&](string &p, int pos) {
int lo = p[pos] - '0', added = 0;
for (int i = ga; i < 10; i += ga) {
int c = (p[pos] - '0' + i) % 10;
if (c < lo) {
lo = c;
added = i;
}
}
if (added)
for (int i = pos; i < n; i += 2)
p[i] = '0' + (p[i] - '0' + added) % 10;
};
// rotate操作
for (int i = 0; i < n; i += gb) {
string p = t.substr(i, n);
add(p, 1);
if (gb % 2)
add(p, 0);
ans = min(ans, p);
}
return ans;
}
};
cpp 解法, 执行用时: 68 ms, 内存消耗: 22.8 MB, 提交时间: 2022-12-09 11:56:20
/**
* 暴力枚举
* 首先考虑轮转操作。对于一个长度为N的字符串，每次轮转b个位置，等价于轮转g=GCD(N,b)个位置。
* 所以，我们只需要以g为步长进行轮转的枚举即可。
* 接下来考虑增加操作。如果g是偶数，那么不管怎么轮转，我们只能对下标为奇数的位置进行增加操作；
* 否则，我们也可以对下标为偶数的位置进行增加操作。根据这两种情况，枚举奇数和偶数位置的增加操作的次数即可。
* 因为每一位是[0,9]之间的数，而1≤a≤9，所以我们只需要枚举操作[0,9]次的情形。
**/
class Solution {
int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
public:
string findLexSmallestString(string s, int a, int b) {
int n = s.size();
string ans = s;
string t = s + s;
int g = gcd(n, b);
for (int i = 0; i < n; i += g) {
string p = t.substr(i, n);
for (int j = 0; j <= 9; ++j) {
int th = g % 2 == 0 ? 0 : 9;
for (int k = 0; k <= th; ++k) {
string q(p);
for (int t = 1; t < n; t += 2)
q[t] = '0' + (q[t] - '0' + a * j) % 10;
for (int t = 0; t < n; t += 2)
q[t] = '0' + (q[t] - '0' + a * k) % 10;
ans = min(ans, q);
}
}
}
return ans;
}
};