1625. Lexicographically Smallest String After Applying Operations
题目简介
吐槽一下：这一题能成为 medium 单纯就是暴力模拟的计算量不大，如果要简化这题的话个人认为是一道 hard……
/**
* @param {string} s
* @param {number} a
* @param {number} b
* @return {string}
*/
本题给了我们一个原始字符串 s（其中每个字符都是 0～9 的数字字符，并且 s 的长度是偶数）以及一个整数 a 与整数 b
要求我们经过无限次的操作之后，求出语义最小的字符串 s
操作有两种：
- 旋转（将字符串往右旋转 b 个字符）：假设
s=0123, b = 2，旋转后得到s=2301 - 求和（将当前字符串奇数下标加 a 后对 10 取余）：假设
s=0123, a = 9，结果为s=0022
解题思路——模拟
这题最简单的思路就是把所有可能的字符串都找出来，然后比较一下将语义最小的字符串返回
具体来说，我们可以用一个 set 来记录我们处理过的字符串；一个 queue 来将所有新字符串入栈；一个变量 res 来记录当前语义最小的字符串
每次循环我们从 queue 中取出字符串，更新 res 变量，然后将其旋转与求和的新字符串入栈，直到 queue 栈为空
Javascript
/**
* @param {string} s
* @param {number} a
* @param {number} b
* @return {string}
*/
var findLexSmallestString = function (s, a, b) {
let res = s
const set = new Set()
const queue = [s]
while (queue.length > 0) {
const str = queue.shift()
if (str < res) {
res = str
}
const rotatedStr = rotate(str, b)
if (!set.has(rotatedStr)) {
set.add(rotatedStr)
queue.push(rotatedStr)
}
const addedStr = add(str, a)
if (!set.has(addedStr)) {
set.add(addedStr)
queue.push(addedStr)
}
}
return res
};
const rotate = (str, b) => {
return str.slice(b, str.length) + str.slice(0, b)
}
const add = (str, a) => {
let newStr = ''
for (let i = 0; i < str.length; i++) {
if (i % 2 === 0) {
newStr += str[i]
} else {
newStr += String((Number(str[i]) + a) % 10)
}
}
return newStr
}
解题思路——数学简化
上面的方法虽然能过，但是构造所有字符串无疑是有点麻烦了，我们接下来研究一下要如何简化
首先我们明确一下目标，要让语义最小，我们的首要目标就是让最高位的数字最小
题目提供了两种调整最高位数字的方法，所以我们可以将目标拆解为两个：
- 通过求和把所有的数字调整到最小
- 通过旋转把最小的数字调整到最前面
求和
根据题目要求，我们每次求和都只能将所有位于当前奇数下标的数字全部求和
所以，在只讨论求和的情况下，我们的目标就是，把最高位的奇数下标的数字调整到最小，也就是将 s[1] 的数字调整到最小
那么我们如何将 s[1] 调整到最小呢？有两种方式：
- 循环对 s[1] 求和，直到得出最小的数字为止，然后对余下的奇数下标数字操作相同次数的求和（最差的情况会多 10 次计算）
- 用我们伟大的数学直接计算出需要加多少～（在所有情况都只需要一次计算）
第一个方式的实现非常简单，但是缺点是会提升复杂度（但是这一题暴力都能解所以肯定是可以通过的）
我们接下来重点看一下第二个方式的推导：
根据题目求和的要求，我们可以得出如下公式
$ r = (s[1] + ak) \mod 10$
其中 k 代表我们进行了 k 次的操作，r 代表 s[1] 经过 k 次操作之后的结果
我们的目标就是得出 ak 是多少可以让 r 最小
我们再进一步可以将 mod 10 操作看成减去多次的 10，我们假设 q 为需要减去 10 的次数，于是公式变成了
$ r = s[1] + ak - 10q$
由于我们的目标是得出 s[1] 要如何操作才能变成 r，所以我们调换一下公式
$ak - 10q = r - s[1]$
其中 ak - 10q 就是我们需要对 s[1] 进行的操作，所以我们接下来的目标就是看看如何使得 ak - 10q 有解
万幸的是～我们有 裴蜀定理：
裴蜀定理假设有 a，b 两个不全为 0 的整数，必定存在两个整数 x 与 y 使得 ax+by= gcd(a, b) 成立
Gcd 表示最大公因数
我们把其中的 x 替换成 k、y 替换成 q、a 还是 a、b 替换成 10，可以得到：
$ak - 10q = gcd(a, 10) = r - s[1]$
于是我们得到结论一：r - s[1] 是 gcd(a, 10) 的倍数
根据同余的定义，我们可以根据结论一推导出～
如果整数 (a) 和 (b) 的差 ((a-b)) 能被 (m) 整除，即 (m|(a-b))，则称 (a) 和 (b) 对模 (m) 同余
结论二： r 与 s[1] 对gcd(a, 10) 同余
由于我们要让 r 最小，所以我们可以推导出～
结论三：r = s[1] mod gcd(a, 10)
我们把结论三套回一开始的公式：
$s[1]\ mod\ gcd(a, 10) = s[1] + ak - 10q$
调整一下，计算 ak 的公式就有了：
$ak = s[1]\ mod\ gcd(a, 10) - s[1] + 10q$
由于我们最后会对 10 取余，所以我们只需要让 q = 1 就可以防止 s[1] mod gcd(a, 10) - s[1] 是负的了
旋转
接下来我们来看看旋转要如何简化
首先明确一点，我们旋转的目的是为了让最高位的数字最小，换言之就是 s[0] 最小
那么我们接下来就来分析一下，有哪些数字有机会成为 s[0]（或者换一个思路，s[0] 通过旋转能出现在哪些位置）
假设字符串 s 长度是 len，每次能旋转 b 位，我们不难得出以下公式
$0 + bk\ mod\ len$
其中 k 代表旋转的次数，这个公式代表 s[0] 通过 k 次旋转后会出现的位置，我们整理一下公式
$bk - len*q$
其中 mod len 可以看成减去了 q 次的 len
根据我们的老熟人 裴蜀定理 得知：如果该公式有解，这些解必须是 gcd(b, len)
也就是说，只有位置在 gcd(b, len) 的倍数的字符有机会旋转到 s[0]
旋转+求和
接下来我们来讨论一下两个操作一起来的情况
具体而言，我们要来讨论一下我们是否能通过旋转将下标为奇数的字符旋转为下标为偶数的字符
我们已经知道字符串长度必为偶数，那么只有两种情况：
- b 为奇数：旋转一次会让奇偶下标的字符位置互换
- b 为偶数：奇偶下标字符不会互换
所以我们得到结论：只有当 b 为奇数的时候，我们才需要对偶数下标的数字求和
Javascript
/**
* @param {string} s
* @param {number} a
* @param {number} b
* @return {string}
*/
var findLexSmallestString = function (s, a, b) {
const arr = s.split('').map(c => Number(c))
const len = arr.length
const rotateStep = gcd(b, len)
const addGcd = gcd(a, 10)
let res = arr
for (let i = 0; i < len; i += rotateStep) {
const rotatedArr = arr.slice(i).concat(arr.slice(0, i))
if (b % 2 === 1) {
add(rotatedArr, addGcd, 0)
}
add(rotatedArr, addGcd, 1)
if (compare(rotatedArr, res) < 0) {
res = rotatedArr
}
}
return res.join('')
};
const gcd = (a, b) => {
while (a) {
[a, b] = [b % a, a]
}
return b
}
const add = (arr, addGcd, start) => {
const c = arr[start]
const inc = c % addGcd - c + 10
for (let i = start; i < arr.length; i += 2) {
arr[i] = (arr[i] + inc) % 10
}
}
const compare = (arr1, arr2) => {
for (let i = 0; i < arr1.length; i++) {
if (arr1[i] !== arr2[i]) {
return arr1[i] - arr2[i]
}
}
return 0
}