348分割数字串获取3的倍数问题

问题理解

我们需要将一个数字串分割成多个子串，使得这些子串中是 3 的倍数的数量最大化。每个子串不能包含前导零（除了数字 0 本身）。

• 使用一个数组 f 来记录以每个位置结尾的子串中，最多有多少个是 3 的倍数的子串。
• 使用一个数组 last 来记录每个余数（0, 1, 2）最后一次出现的位置。

算法步骤

1. 初始化：

   • 初始化 last 数组为 [-1, -1, -1]，表示每个余数（0, 1, 2）还没有出现过。
   • 初始化 f 数组为 [0] * n，其中 n 是字符串的长度。

2. 处理第一个字符：

   • 计算第一个字符的余数，并更新 last 数组。
   • 如果第一个字符的余数是 0，则 f[0] 设为 1，表示第一个字符本身就是一个 3 的倍数。

3. 动态规划更新：

   • 从第二个字符开始遍历字符串。
   • 对于每个字符，计算当前字符与前面字符的和的余数 j。
   • 如果 last[j] 不是 -1，说明前面有一个位置的余数与当前余数相同，可以形成一个 3 的倍数的子串，更新 f[i]。
   • 如果 j 是 0，说明当前字符本身就是一个 3 的倍数，更新 f[i]。
   • 更新 last[j] 为当前位置 i。

4. 返回结果：

   • 最终结果是 f 数组的最后一个元素 f[-1]，表示整个字符串中最多有多少个是 3 的倍数的子串。

解题代码

def solution(s: str) -> int:
    n = len(s)
    last = [-1, -1, -1]
    last[int(s[0]) % 3] = 0
    f = [0] * n
    if last[0] == 0:
        f[0] = 1
    j = int(s[0]) % 3
    for i in range(1, n):
        f[i] = f[i - 1]
        j = (j + int(s[i])) % 3
        if last[j] >= 0:
            f[i] = max(f[i], f[last[j]] + 1)
        elif j == 0:
            f[i] = max(f[i], 1)
        last[j] = i
    return f[-1]


if __name__ == '__main__':
    print(solution("1123") == 2)
    print(solution("300") == 3)
    print(solution("987654321") == 6)

复杂度分析

$s$ 的长度是 $n$，时间复杂度是 $O(n)$，空间复杂度是 $O(n)$。