專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近DeepSeek是異常火爆，不過每天提問一次還是正常的，如果提問多了就會出現“服務器繁忙，請稍后再試”，很是讓人頭疼。不過把深度思考(R1)關閉之后就正常了，這也算是一種解決方式吧。但關閉之后的回答感覺還是缺少了點什么，于是各種胡亂提問，終于迎來了DeepSeek的報復。關鍵我沒有上傳過圖片，也沒有打開攝像頭……

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第2575題：找出字符串的可整除數組。

問題描述

來源：LeetCode第2575題

難度：中等

給你一個下標從 0 開始的字符串 word ，長度為 n ，由從 0 到 9 的數字組成。另給你一個正整數 m 。word 的可整除數組 div 是一個長度為 n 的整數數組，并滿足：

1，如果 word[0,...,i] 所表示的數值能被 m 整除，div[i] = 1

2，否則，div[i] = 0

返回 word 的可整除數組。

示例1：

輸入：word = "998244353", m = 3 輸出：[1,1,0,0,0,1,1,0,0] 解釋：僅有 4 個前綴可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。

示例2：

輸入：word = "1010", m = 10 輸出：[0,1,0,1] 解釋：僅有 2 個前綴可以被 10 整除："10" 和 "1010" 。

• 1 <= n <= 10^5

• word.length == n

• word 由數字 0 到 9 組成

• 1 <= m <= 10^9

問題分析

這題讓計算前 i 個字符串表示的數字能否被 m 整除，能否整除直接求余即可，比如 a%b=0，就表示 a 能被 b 整除。

我們還知道對于所有正整數（負的不滿足）的取模運算都滿足下面幾個公式，

(a+b)%m=(a%m+b%m)%m

(a+b)%m=(a%m+b)%m

(a×10+b)%m=(a×10%m+b)%m

我們直接按照上面最后一個公式，根據當前整數的余數，計算出包含下一位字符所表示的整數的余數，如果余數為 0 ，則表示能被 m 整除。

JAVA：

public int[] divisibilityArray(String word, int m) {     int length = word.length();     int ans[] = new int[length];     long modSum = 0;     for (int i = 0; i < length; i++) {         modSum = modSum * 10 + word.charAt(i) - '0';         modSum %= m;         if (modSum == 0)// 能被m整除             ans[i] = 1;     }     return ans; }

C++：

public:     vector

  divisibilityArray(string word, int m) {         int length = word.length();         vector

  ans(length);         long modSum = 0;         for (int i = 0; i < length; i++) {             modSum = modSum * 10 + word[i] - '0';             modSum %= m;             if (modSum == 0)// 能被m整除                 ans[i] = 1;         }         return ans;     }

C：

int *divisibilityArray(char *word, int m, int *returnSize) {     int length = strlen(word);     int *ans = calloc(length, sizeof(int));     *returnSize = length;     long modSum = 0;     for (int i = 0; i < length; i++) {         modSum = modSum * 10 + word[i] - '0';         modSum %= m;         if (modSum == 0)// 能被m整除             ans[i] = 1;     }     return ans; }

Python：

def divisibilityArray(self, word: str, m: int) -> List[int]:     n = len(word)     ans = [0] * n     modSum = 0     for i, ch in enumerate(word):         modSum = modSum * 10 + int(ch)         modSum %= m         if modSum == 0:  # 能被m整除             ans[i] = 1     return ans

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。