• Leetcode 3448. Count Substrings Divisible By Last Digit
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3448. Count Substrings Divisible By Last Digit

1. 解題思路

這一題的話我們走的是一個累積數組的思路。

首先，我們使用一個cache數組記錄下任意段數字對$1$到$9$的余數，即任意cache[i][j] = int(s[:i]) % j。

然后，我們考察任意位置上所有前序數組對$1$到$9$的余數，即$\sum _{j=0}^i{s}_{ji}\equiv mod(k)$，而要求上述問題，我們可以反向求累積數組$\sum _{j=0}^i(s_i?s_j\times 10^{i?j})\equiv mod(k)$。

因此，我們可以用累計數組進行求解。

2. 代碼實現

給出python代碼實現如下：

class Solution:def countSubstrings(self, s: str) -> int:n = len(s)cache = [[0 for _ in range(10)] for _ in range(n)]mod = [0 for _ in range(10)]for i, ch in enumerate(s):digit = int(ch)for j in range(1, 10):mod[j] = (mod[j] * 10 + digit) % jcache[i][j] = mod[j]def update_cnt(cnt):ans = [[0 for j in range(i)] for i in range(10)]for i in range(1, 10):for j in range(i):r = (j * 10) % ians[i][r] += cnt[i][j]return ansans = 0cnt = [[0 for j in range(i)] for i in range(10)]for i in range(1, 10):cnt[i][0] += 1for i, ch in enumerate(s):cnt = update_cnt(cnt)digit = int(ch) if digit != 0:ans += cnt[digit][cache[i][digit]]for j in range(1, 10):cnt[j][cache[i][j]] += 1return ans

提交代碼評測得到：耗時9031ms，占用內存38.3MB。

需要注意的是，事實上上述代碼還可以進一步優化，因為至少1，2，5幾個數是必然滿足只要以對應的數字結尾就一定可以滿足條件，因此，我們事實上是可以對上述算法進行優化的，不過這里就不過多展開了，有興趣的讀者可以自行嘗試一下。