专栏：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算法文档 。