跳至主要內容

1945. 字符串转化后的各位数字之和


1945. 字符串转化后的各位数字之和

🟢   🔖  字符串 模拟  🔗 力扣open in new window LeetCodeopen in new window

题目

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:

  1. Convert s into an integer by replacing each letter with its position in the alphabet (i.e. replace 'a' with 1, 'b' with 2, ..., 'z' with 26).
  2. Transform the integer by replacing it with the sum of its digits.
  3. 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:

  1. Convert : "zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
  2. Transform #1 : 262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
  3. 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 次来进行转换。更具体地说,执行以下步骤:

  1. 用字母在字母表中的位置 替换 该字母,将 s 转化 为一个整数(也就是,'a'1 替换,'b'2 替换,... 'z'26 替换)。
  2. 接着,将整数 转换 为其 各位数字之和
  3. 共重复 转换 操作(第 2 步) k

例如,如果 s = "zbax"k = 2 ,那么执行下述步骤后得到的结果是整数 8

  • 转化:"zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
  • 转换 #1262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
  • 转换 #217 ➝ 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 由小写英文字母组成

解题思路

  1. 定义 transform 函数

    • transform 函数用来将一个整数的所有数位相加并返回累加和。
    • 使用循环逐位提取数位(利用取余和整除操作)并累加。
    • 例如:输入 123 时,输出 1 + 2 + 3 = 6
  2. 字符转换为数值并求和

    • 每个字符从 'a''z' 对应数值 126
    • 通过 char.charCodeAt() - 96 计算字母的数值。
    • 如果字母数值超过 9,通过 transform 函数进一步拆解并求和,将其转化为数位之和。
  3. 重复数位求和 k

    • 初次求和得到的结果存储在变量 sum 中。
    • 每次调用 transform 函数对当前的数值进行数位求和,并更新 sum
    • 如果在循环中某一次结果已经小于 10,则提前终止,避免无意义的重复计算。
  4. 返回结果

    • 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快乐数[✓]哈希表 数学 双指针🟢🀄️open in new window 🔗open in new window
258各位相加[✓]数学 数论 模拟🟢🀄️open in new window 🔗open in new window
2180统计各位数字之和为偶数的整数个数[✓]数学 模拟🟢🀄️open in new window 🔗open in new window
3300替换为数位和以后的最小元素数组 数学🟢🀄️open in new window 🔗open in new window