2243.计算字符串的数字和:模拟

【LetMeFly】2243.计算字符串的数字和:模拟

力扣题目链接:https://leetcode.cn/problems/calculate-digit-sum-of-a-string/

给你一个由若干数字(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)组成。

解题方法:模拟

当字符串s长度大于k时,进行如下操作:

创建一个临时空字符串,遍历字符串s,累加当前字符对应数字。每遍历k个字符就将数字和转为字符串并拼接到临时字符串中,同时将累加和清零。

遍历结束后,赋值s为临时字符串。

时空复杂度

  • 时间复杂度$O(len(s))$
  • 空间复杂度$O(len(s))$

关于时间复杂度:

假如$k$很大,则几乎不用操作就会结束。

假如$k$很小(最小为$2$),每次操作字符串长度大约缩短为原来的$\frac12$,$n+\frac{n}2+\frac{n}4+\dots\approx2n$。

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
* @LastEditTime: 2026-11-16 21:57:46
*/
class Solution {
public:
string digitSum(string s, int k) {
while (s.size() > k) {
string tmp;
int cnt = 0;
for (int i = 0, n = s.size(); i < n; i++) {
if (i && i % k == 0) {
tmp += to_string(cnt);
cnt = 0;
}
cnt += s[i] - '0';
}
tmp += to_string(cnt);
swap(s, tmp);
}
return s;
}
};

End

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源


2243.计算字符串的数字和:模拟
https://blog.letmefly.xyz/2026/11/16/LeetCode 2243.计算字符串的数字和/
作者
发布于
2026年11月16日
许可协议