Easy

题目描述

给你一个由数字组成的字符串 s 和一个整数 k。

如果 s 的长度大于 k，则可以进行一轮操作。在一轮操作中，需要执行以下步骤：

  1. 将 s 分割成长度为 k 的连续组，使得前 k 个字符在第一组，接下来的 k 个字符在第二组，依此类推。注意，最后一组的长度可以小于 k。
  2. 用表示该组所有数字之和的字符串来替换 s 中的每个组。例如，“346” 被替换为 “13”，因为 3 + 4 + 6 = 13。
  3. 合并连续的组以形成新字符串。如果字符串的长度大于 k，则重复步骤 1。

返回完成所有轮操作后的 s。

示例 1：

输入：s = "11111222223", k = 3
输出："135"
解释：
- 第一轮，我们将 s 分成大小为 3 的组："111"、"112"、"222" 和 "23"。
  然后我们计算每个组的数字和：1 + 1 + 1 = 3，1 + 1 + 2 = 4，2 + 2 + 2 = 6，2 + 3 = 5。
  所以，第一轮后 s 变成 "3" + "4" + "6" + "5" = "3465"。
- 第二轮，我们将 s 分成 "346" 和 "5"。
  然后我们计算每个组的数字和：3 + 4 + 6 = 13，5 = 5。
  所以，第二轮后 s 变成 "13" + "5" = "135"。
现在，s.length <= k，所以我们返回 "135" 作为答案。

示例 2：

输入：s = "00000000", k = 3
输出："000"
解释：
我们将 s 分成 "000"、"000" 和 "00"。
然后我们计算每个组的数字和：0 + 0 + 0 = 0，0 + 0 + 0 = 0，0 + 0 = 0。
s 变成 "0" + "0" + "0" = "000"，其长度等于 k，所以我们返回 "000"。

约束条件：

  • 1 <= s.length <= 100
  • 2 <= k <= 100
  • s 仅由数字组成

解题思路

解题思路

这道题是一个典型的模拟题，我们需要按照题目描述的步骤逐步执行操作。

核心思路：

  1. 当字符串长度大于 k 时，持续进行操作轮次
  2. 每轮操作中，将字符串按长度 k 进行分组
  3. 计算每组数字的和，并转换为字符串
  4. 将所有组的结果拼接成新字符串
  5. 重复上述过程直到字符串长度不超过 k

算法步骤：

  1. 使用 while 循环，条件是字符串长度大于 k
  2. 在每次循环中：
    • 初始化新的结果字符串
    • 以步长 k 遍历原字符串，对每个长度为 k（或剩余长度）的子串计算数字和
    • 将数字和转换为字符串并拼接到结果中
  3. 更新原字符串为新结果
  4. 当字符串长度不超过 k 时返回结果

这个算法的时间复杂度主要取决于操作的轮数和每轮处理的字符数量。由于每轮操作都会显著减少字符串长度，所以整体效率较高。

代码实现

class Solution {
public:
    string digitSum(string s, int k) {
        while (s.length() > k) {
            string newS = "";
            for (int i = 0; i < s.length(); i += k) {
                int sum = 0;
                for (int j = i; j < min((int)s.length(), i + k); j++) {
                    sum += s[j] - '0';
                }
                newS += to_string(sum);
            }
            s = newS;
        }
        return s;
    }
};

class Solution:
    def digitSum(self, s: str, k: int) -> str:
        while len(s) > k:
            new_s = ""
            for i in range(0, len(s), k):
                group = s[i:i+k]
                digit_sum = sum(int(digit) for digit in group)
                new_s += str(digit_sum)
            s = new_s
        return s

public class Solution {
    public string DigitSum(string s, int k) {
        while (s.Length > k) {
            string newS = "";
            for (int i = 0; i < s.Length; i += k) {
                int sum = 0;
                for (int j = i; j < Math.Min(s.Length, i + k); j++) {
                    sum += s[j] - '0';
                }
                newS += sum.ToString();
            }
            s = newS;
        }
        return s;
    }
}

var digitSum = function(s, k) {
    while (s.length > k) {
        let newS = "";
        for (let i = 0; i < s.length; i += k) {
            let sum = 0;
            for (let j = i; j < Math.min(s.length, i + k); j++) {
                sum += parseInt(s[j]);
            }
            newS += sum.toString();
        }
        s = newS;
    }
    return s;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)其中 n 是字符串的初始长度。每轮操作处理所有字符一次，操作轮数较少
空间复杂度O(n)需要额外空间存储每轮操作的新字符串

相关题目