You are given a string s
consisting of digits and an integer k
.
A round can be completed if the length of s
is greater than k
. In one round, do the following:
- Divide
s
into consecutive groups of sizek
such that the firstk
characters are in the first group, the nextk
characters are in the second group, and so on. Note that the size of the last group can be smaller thank
. - Replace each group of
s
with a string representing the sum of all its digits. For example,"346"
is replaced with"13"
because3 + 4 + 6 = 13
. - Merge consecutive groups together to form a new string. If the length of the string is greater than
k
, repeat from step1
.
Return s
after all rounds have been completed.
Example 1:
Input: s = "11111222223", k = 3 Output: "135" Explanation: - For the first round, we divide s into groups of size 3: "111", "112", "222", and "23". Then we calculate the digit sum of each group: 1 + 1 + 1 = 3, 1 + 1 + 2 = 4, 2 + 2 + 2 = 6, and 2 + 3 = 5. So, s becomes "3" + "4" + "6" + "5" = "3465" after the first round. - For the second round, we divide s into "346" and "5". Then we calculate the digit sum of each group: 3 + 4 + 6 = 13, 5 = 5. So, s becomes "13" + "5" = "135" after second round. Now, s.length <= k, so we return "135" as the answer.
Example 2:
Input: s = "00000000", k = 3 Output: "000" Explanation: We divide s into "000", "000", and "00". Then we calculate the digit sum of each group: 0 + 0 + 0 = 0, 0 + 0 + 0 = 0, and 0 + 0 = 0. s becomes "0" + "0" + "0" = "000", whose length is equal to k, so we return "000".
Constraints:
1 <= s.length <= 100
2 <= k <= 100
s
consists of digits only.
Solution:
Time complexity: O(n*n/k?)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: string digitSum(string s, int k) { while (s.length() > k) { string ss; for (int j = 0; j < s.length(); j += k) { int sum = 0; for (int i = 0; i < k && i + j < s.length(); ++i) sum += (s[j + i] - '0'); ss += to_string(sum); } ss.swap(s); } return s; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment