Easy

题目描述

给你一个由小写英文字母组成的字符串 s，以及一个整数 k。

首先，用字母在字母表中的位置替换该字母，将 s 转化 为一个整数（也就是，'a' 用 1 替换，'b' 用 2 替换，… 'z' 用 26 替换）。接着，将整数 转换 为其各位数字之和。共重复 转换 操作 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 由小写英文字母组成

解题思路

这题的解题思路可以分为两个阶段：

第一阶段：字母转换为数字串 将字符串中每个字母替换为其在字母表中的位置（a=1, b=2, …, z=26）。这里有个优化点：我们不需要真正构造一个巨大的数字串，而是直接计算所有数字的数位之和。对于字母 c，其对应数字为 c - 'a' + 1，我们直接累加这个数字的各位数字之和即可。

第二阶段：重复数位求和 对得到的数字重复进行数位求和操作，总共执行 k 次。每次求和就是将数字的每一位相加得到新的数字。

关键优化：

  • 第一次转换时直接计算数位和，避免构造超大整数
  • 后续的 k-1 次转换直接对整数进行数位求和
  • 由于字符串长度最大100，第一次转换后的结果最大为 100×26 的数位和，约等于 100×(2+6)=800，之后的数字会快速缩小

推荐解法： 直接计算数位和，避免字符串操作，时间和空间效率都最优。

代码实现

class Solution {
public:
    int getLucky(string s, int k) {
        // 第一步：将字符串转换为数字并计算数位和
        int sum = 0;
        for (char c : s) {
            int num = c - 'a' + 1;
            // 直接计算数位和
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
        }
        
        // 执行剩余的 k-1 次转换
        for (int i = 1; i < k; i++) {
            int newSum = 0;
            while (sum > 0) {
                newSum += sum % 10;
                sum /= 10;
            }
            sum = newSum;
        }
        
        return sum;
    }
};

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        # 第一步：将字符串转换为数字并计算数位和
        total = 0
        for c in s:
            num = ord(c) - ord('a') + 1
            # 直接计算数位和
            while num > 0:
                total += num % 10
                num //= 10
        
        # 执行剩余的 k-1 次转换
        for _ in range(k - 1):
            new_total = 0
            while total > 0:
                new_total += total % 10
                total //= 10
            total = new_total
        
        return total

public class Solution {
    public int GetLucky(string s, int k) {
        // 第一步：将字符串转换为数字并计算数位和
        int sum = 0;
        foreach (char c in s) {
            int num = c - 'a' + 1;
            // 直接计算数位和
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
        }
        
        // 执行剩余的 k-1 次转换
        for (int i = 1; i < k; i++) {
            int newSum = 0;
            while (sum > 0) {
                newSum += sum % 10;
                sum /= 10;
            }
            sum = newSum;
        }
        
        return sum;
    }
}

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var getLucky = function(s, k) {
    // 第一步：将字符串转换为数字并计算数位和
    let sum = 0;
    for (let c of s) {
        let num = c.charCodeAt(0) - 'a'.charCodeAt(0) + 1;
        // 直接计算数位和
        while (num > 0) {
            sum += num % 10;
            num = Math.floor(num / 10);
        }
    }
    
    // 执行剩余的 k-1 次转换
    for (let i = 1; i < k; i++) {
        let newSum = 0;
        while (sum > 0) {
            newSum += sum % 10;
            sum = Math.floor(sum / 10);
        }
        sum = newSum;
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + k × log(max_sum))，其中 n 是字符串长度，k 是转换次数，max_sum 是可能的最大数字值
空间复杂度O(1)，只使用常数额外空间

相关题目