[M数学] lc2575. 找出字符串的可整除数组(数学与取模运算结合)

文章目录

• • 1. 题目来源
  • 2. 题目解析

1. 题目来源

确定字符串中的哪些字符对应的数字可以被某个数整除，并将这些位置记录在一个数组中

2. 题目解析

一道中等题，通过率只有30%，编码只用了30s…1A…

思路：

• 常见取模运算规则：对于整数运算(a \times 10 + b) \% m来说，
• 它等于(a \% m \times 10 + b \% m) \% m。
• 根据上述规律，
• 可以推导出判断当前字符串表示的数值是否能被m整除的方法：
• 即判断前一个字符串关于m的余数加上当前位数字之和是否能被m整除。
• 需要注意的是，
• 在这种操作中使用int可能会导致溢出问题，
• 因此建议将数据类型设置为long long来避免溢出。

• 时间复杂度 ：O(n)
• 空间复杂度 ：O(1)

    class Solution {
    public:
    typedef long long LL;
    vector<int> divisibilityArray(string word, int m) {
        vector<int> res;
        LL x = 0;