1945. 字符串转化后的各位数字之和
1945. 字符串转化后的各位数字之和
题目
You are given a string s
consisting of lowercase English letters, and an integer k
. Your task is to convert the string into an integer by a special process, and then transform it by summing its digits repeatedly k
times. More specifically, perform the following steps:
- Convert
s
into an integer by replacing each letter with its position in the alphabet (i.e. replace'a'
with1
,'b'
with2
, ...,'z'
with26
). - Transform the integer by replacing it with the sum of its digits.
- Repeat the transform operation (step 2)
k
times in total.
For example, if s = "zbax"
and k = 2
, then the resulting integer would be 8
by the following operations:
- Convert :
"zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
- Transform #1 :
262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
- Transform #2 :
17 ➝ 1 + 7 ➝ 8
Return the resulting integer after performing the operations described above.
Example 1:
Input: s = "iiii", k = 1
Output: 36
Explanation:
The operations are as follows:
- Convert: "iiii" ➝ "(9)(9)(9)(9)" ➝ "9999" ➝ 9999
- Transform #1: 9999 ➝ 9 + 9 + 9 + 9 ➝ 36
Thus the resulting integer is 36.
Example 2:
Input: s = "leetcode", k = 2
Output: 6
Explanation:
The operations are as follows:
- Convert: "leetcode" ➝ "(12)(5)(5)(20)(3)(15)(4)(5)" ➝ "12552031545" ➝ 12552031545
- Transform #1: 12552031545 ➝ 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 ➝ 33
- Transform #2: 33 ➝ 3 + 3 ➝ 6
Thus the resulting integer is 6.
Example 3:
Input: s = "zbax", k = 2
Output: 8
Constraints:
1 <= s.length <= 100
1 <= k <= 10
s
consists of lowercase English letters.
题目大意
给你一个由小写字母组成的字符串 s
,以及一个整数 k
。你的任务是通过一种特殊处理将字符串转为整数,然后通过重复对它的数位求和 k
次来进行转换。更具体地说,执行以下步骤:
- 用字母在字母表中的位置 替换 该字母,将
s
转化 为一个整数(也就是,'a'
用1
替换,'b'
用2
替换,...'z'
用26
替换)。 - 接着,将整数 转换 为其 各位数字之和 。
- 共重复 转换 操作(第 2 步)
k
次 。
例如,如果 s = "zbax"
且 k = 2
,那么执行下述步骤后得到的结果是整数 8
:
- 转化:
"zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
- 转换 #1 :
262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
- 转换 #2 :
17 ➝ 1 + 7 ➝ 8
返回执行上述 操作 后得到的 结果整数 。
示例 1:
输入: s = "iiii", k = 1
输出: 36
解释:
操作如下:
- 转化:"iiii" ➝ "(9)(9)(9)(9)" ➝ "9999" ➝ 9999
- 转换 #1:9999 ➝ 9 + 9 + 9 + 9 ➝ 36
因此,结果整数为 36 。
示例 2:
输入: s = "leetcode", k = 2
输出: 6
解释:
操作如下:
- 转化:"leetcode" ➝ "(12)(5)(5)(20)(3)(15)(4)(5)" ➝ "12552031545" ➝ 12552031545
- 转换 #1:12552031545 ➝ 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 ➝ 33
- 转换 #2:33 ➝ 3 + 3 ➝ 6
因此,结果整数为 6 。
示例 3:
输入: s = "zbax", k = 2
输出: 8
提示:
1 <= s.length <= 100
1 <= k <= 10
s
由小写英文字母组成
解题思路
定义
transform
函数transform
函数用来将一个整数的所有数位相加并返回累加和。- 使用循环逐位提取数位(利用取余和整除操作)并累加。
- 例如:输入
123
时,输出1 + 2 + 3 = 6
。
字符转换为数值并求和
- 每个字符从
'a'
到'z'
对应数值1
到26
。 - 通过
char.charCodeAt() - 96
计算字母的数值。 - 如果字母数值超过
9
,通过transform
函数进一步拆解并求和,将其转化为数位之和。
- 每个字符从
重复数位求和
k
次- 初次求和得到的结果存储在变量
sum
中。 - 每次调用
transform
函数对当前的数值进行数位求和,并更新sum
。 - 如果在循环中某一次结果已经小于 10,则提前终止,避免无意义的重复计算。
- 初次求和得到的结果存储在变量
返回结果
- 在
k
次迭代结束后,sum
中存储的即为最终结果。
- 在
复杂度分析
时间复杂度:
O(n + k * log_10(m))
- 初次字符映射:
O(n)
,其中n
是字符串s
的长度。 - 每次数位求和:近似
O(log_10(m))
,其中m
是当前数值的大小。 - 总体复杂度为
O(n + k * log_10(m))
。
- 初次字符映射:
空间复杂度:
O(1)
,仅使用常数空间,无需额外数组存储。
代码
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var getLucky = function (s, k) {
// 数位求和函数
const transform = (n) => {
if (n < 10) return n;
let res = 0;
while (n > 0) {
res += n % 10; // 累加当前数位
n = Math.floor(n / 10); // 去掉最低位
}
return res;
};
// 初始化,将字符映射为字母顺序值并求和
let sum = 0;
for (let char of s) {
sum += transform(char.charCodeAt() - 96);
}
// 执行数位求和 k - 1 次,因为在上面已经执行过一次了
while (k-- > 1) {
sum = transform(sum);
if (sum < 10) break; // 如果数值稳定为个位数,提前结束
}
return sum;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
202 | 快乐数 | [✓] | 哈希表 数学 双指针 | 🟢 | 🀄️ 🔗 |
258 | 各位相加 | [✓] | 数学 数论 模拟 | 🟢 | 🀄️ 🔗 |
2180 | 统计各位数字之和为偶数的整数个数 | [✓] | 数学 模拟 | 🟢 | 🀄️ 🔗 |
3300 | 替换为数位和以后的最小元素 | 数组 数学 | 🟢 | 🀄️ 🔗 |