计算字符串的数字和

标签: 字符串 模拟

难度: Easy

给你一个由若干数字（0 - 9）组成的字符串 s ，和一个整数。

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

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

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

示例 1：

输入：s = "11111222223", k = 3
输出："135"
解释：
- 第一轮，将 s 分成："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"
解释：
将 "000", "000", and "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 仅由数字（0 - 9）组成。

Submission

运行时间: 23 ms

内存: 16.1 MB

class Solution:
    def digitSum(self, s: str, k: int) -> str:
        while len(s) > k:
            groups = [s[i:i+k] for i in range(0, len(s), k)]  # Split s into groups of length k
            sums = [str(sum(int(digit) for digit in group)) for group in groups]  # Calculate sum of digits in each group
            s = ''.join(sums)  # Merge the sums into a new string
        return s

Explain

该题解采用了模拟的方法来解决问题。首先检查字符串s的长度是否大于k，如果是，则进行拆分、计算和合并的操作。具体步骤如下：1. 将字符串s按照长度k拆分成多个子字符串组；2. 对每个子字符串组，计算其所有字符代表的数字的总和；3. 将计算得到的每个和转换为字符串，并将这些字符串重新连接起来形成新的字符串s。这个过程重复进行，直到s的长度不大于k为止，然后返回s作为结果。

时间复杂度: O(n log_k(n))

空间复杂度: O(n)

class Solution:
    def digitSum(self, s: str, k: int) -> str:
        # 循环直到字符串s的长度不大于k
        while len(s) > k:
            # 将s分割成每组长度为k的子字符串
            groups = [s[i:i+k] for i in range(0, len(s), k)]
            # 计算每个分组的数字总和，并转换为字符串
            sums = [str(sum(int(digit) for digit in group)) for group in groups]
            # 将所有组的和连接起来形成新的字符串s
            s = ''.join(sums)
        # 返回处理后的字符串s
        return s

Explore

是的，该算法已经考虑了包含前导零的情况。在计算每个子字符串组的数字总和时，首先将每个字符转换为整数再进行求和。例如，子组'007'中的字符会首先被转换为整数0, 0, 7，然后求和得到7。因此，不论子字符串的前导零的数量如何，计算得到的和都是正确的。

理论上，最新生成的字符串长度有可能再次增加超过k，在某些情况下可能导致多轮重复，但不会导致无限循环。每次拆分和合并操作后，字符串s的长度将受到其组内数字总和的位数的影响。由于每次操作都会将多个数字的和转换为一到几个字符，所以总体上字符串长度会趋于减小或稳定在某个长度，直到不再大于k。因此，该算法最终会停止循环。

列表推导方法虽然简洁易读，但在处理非常大的字符串时可能不够高效，因为它需要多次遍历字符串并创建中间列表。对于大数据量的优化，可以考虑使用生成器表达式来减少内存使用，或者直接在一个循环中计算和并构建新的字符串，避免多次创建和销毁中间数据结构，从而提高效率。

在实际情况下，输入k为0或负数都不符合题目的预期使用场景，因为k表示的是子字符串的长度，必须是正整数。在实现算法时，应当首先检查k的值，如果k小于等于0，则抛出异常或返回错误信息，告知用户输入不符合要求。这样可以避免运行时错误并提醒用户提供合法的输入。