Medium

题目描述

给你一个长度为 n 、下标从 0 开始的字符串 word ，该字符串由数字组成，另给你一个正整数 m 。

word 的 可整除数组 div 是长度为 n 的整数数组，并满足：

  • 如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
  • 否则，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

解题思路

这道题要求我们判断字符串的每个前缀表示的数字是否能被 m 整除。

核心思路：

直接计算每个前缀的数值会导致整数溢出，因为前缀可能非常大。我们可以利用模运算的性质来解决这个问题。

关键观察：

  • 对于前缀 word[0...i-1] 的余数为 remainder
  • 当我们添加新字符 word[i] 时，新前缀的值为：原前缀值 × 10 + word[i]
  • 根据模运算性质：(a × 10 + b) mod m = ((a mod m) × 10 + b) mod m

算法步骤：

  1. 初始化余数 remainder = 0
  2. 遍历字符串的每个字符
  3. 更新余数：remainder = (remainder × 10 + 当前数字) mod m
  4. 如果余数为 0，说明当前前缀能被 m 整除，设置 div[i] = 1，否则为 0

这种方法避免了大整数计算，时间复杂度为 O(n)，空间复杂度为 O(1)（除了结果数组）。

代码实现

class Solution {
public:
    vector<int> divisibilityArray(string word, int m) {
        vector<int> div(word.length());
        long long remainder = 0;
        
        for (int i = 0; i < word.length(); i++) {
            remainder = (remainder * 10 + (word[i] - '0')) % m;
            div[i] = (remainder == 0) ? 1 : 0;
        }
        
        return div;
    }
};

class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        div = []
        remainder = 0
        
        for char in word:
            remainder = (remainder * 10 + int(char)) % m
            div.append(1 if remainder == 0 else 0)
        
        return div

public class Solution {
    public int[] DivisibilityArray(string word, int m) {
        int[] div = new int[word.Length];
        long remainder = 0;
        
        for (int i = 0; i < word.Length; i++) {
            remainder = (remainder * 10 + (word[i] - '0')) % m;
            div[i] = remainder == 0 ? 1 : 0;
        }
        
        return div;
    }
}

/**
 * @param {string} word
 * @param {number} m
 * @return {number[]}
 */
var divisibilityArray = function(word, m) {
    let result = [];
    let remainder = 0;
    
    for (let i = 0; i < word.length; i++) {
        remainder = (remainder * 10 + parseInt(word[i])) % m;
        result.push(remainder === 0 ? 1 : 0);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，每次操作为常数时间
空间复杂度O(1)除了结果数组外，只使用常数额外空间

相关题目