403小N的改数组问题

解题思路

题目要求在一个正整数的表示中，恰好修改 k 位，使其成为 75 的倍数。要满足 75 的倍数条件，必须满足以下两点：

1. 末两位是 00、25、50 或 75：这是因为 75 是 25 和 3 的最小公倍数，所以数的末两位需要是上述之一以满足被 25 整除，同时整个数的数字之和需要被 3 整除。

2. 数字之和被 3 整除：这是因为一个数能被 75 整除当且仅当其各位数字之和能被 3 整除。

3. 状态参数：

   • i: 当前处理的位数位置。
   • left: 剩余可以修改的位数。
   • is_num: 是否已经开始形成有效数字（防止前导零）。
   • sum: 当前数字之和模 3 的值。

4. 递归终止条件：

   • 当处理到倒数第二位时，检查末两位是否可以组成 00, 25, 50, 75 之一，并且总修改次数与 left 相等，同时数字之和满足被 3 整除的条件。

5. 选择每一位数字：

   • 对于每一位，根据是否已经开始形成数字 (is_num) 决定当前位可以取的最小值（防止前导零）。
   • 尝试所有可能的数字（0-9），并相应地更新剩余修改次数和数字之和。

代码实现

from functools import cache
mod = int(1e9 + 7)
def solution(s: str, k: int) -> int:
    n = len(s)
    if n <= 1:
        return 0
    @cache
    def dfs(i, left, is_num, sum):
        if left < 0:
            return 0
        if i == n - 2:
            ans = 0
            for t in ["00", "25", "50", "75"]:
                if t == "00" and is_num == False:
                    continue
                cnt = (t[0] != s[i]) + (t[1] != s[i + 1])
                if cnt != left or (int(t[0]) + int(t[1]) + sum) % 3:
                    continue
                ans += 1
            return ans
        res = 0
        for j in range(0 if is_num else 1, 10):
            res += dfs(i + 1, left - (j != int(s[i])), is_num or j, (sum + j) % 3)
        return res % mod
    res = dfs(0, k, False, 0)
    return res

if __name__ == '__main__':
    print(solution(s = "3554", k = 2) == 7)
    print(solution(s = "6005", k = 1) == 2)
    print(solution(s = "911154", k = 3) == 187)

复杂度分析

• 时间复杂度：由于使用了记忆化搜索，状态数为 n * k * 2 * 3，其中 n 是数字长度，k 是允许修改的位数。同时枚举了每位被修改成哪个数字。因此，时间复杂度为 O(n * k * 2 * 3 * 10)。其中n为字符串s的长度。
• 空间复杂度：同样为 O(n * k * 2 * 3)，用于存储记忆化搜索的状态。