Leetcode每日一题 —— 3756. 连接非零数字并乘以其数字和 II

SomeBottle 2026-07-08 12:37 1

今天可能给一长串字符串，并有多次区间查询，思路上是昨天题的延续。

思路

看到区间查询能想到前缀和、差分数组和线段树，这题涉及到了区间数字和所以应该能按前缀和去做。

前缀和求区间数字和是老生常谈了，生成前缀和后区间和就是 preSum[r+1]-preSum[l] （这里假设前缀和数组下标全从 1 开始），但是题目还涉及到要把 [l, r] 间的数字拼接成一个数字得到 x。

昨天的题目，我们在按位拼接数字的时候每次迭代会将前一个拼成的数 \times 10 再加上当前数，这题其实也是一样，我们可以递推前缀拼成的数字：

// if s[i]!='0'

preCat[i+1] = preCat[i]*10 + (s[i]-'0')

// else

preCat[i+1] = preCat[i]

可以看到同一个前缀，每一次递推都会 \times 10。能这样递推就可以计算区间结果了，如果要找 [l, r] 区间拼成的数字，那就是：

num = preCat[r+1] - preCat[l]*(10^(区间内非 0 字符的数量))

这里非 0 字符的数量可以用另一个前缀和去跟踪（这样写好像有点麻烦，应该有更优解），10 的幂也可以预先计算生成。

得出两个递推式后就差不多理清思路了，不过注意因为输入规模可能很大，preCat 和 10 的幂的预生成都要取模，计算拼成的 num 时也要取模。

尤其像是计算 num 时，上式算出来可能是负数，一些编程语言里 % 取余后仍是负数，因此要加上一份模数再取余，这样才能得到非负模数。

代码

写得有点丑陋了，应该有更优的写法。

class Solution {

public:

    vector<int> sumAndMultiply(string s, vector<vector<int>>& queries) {

        // 首先前缀和能解决 sum 的问题

        // 问题是 x 的处理，因为 s 可能相当长，直接按位拼起来就算是 long long

        // 也无法表示 x 肯定涉及到一个取余问题，如果 preCat

        // 是前缀数字拼接得到的值 那么 preCat 的递推就是

        // preCat[i+1]=(preCat[i]*10 + (s[i]-'0')) % modulus

        // 相当于每次都把前缀构成的数字×10

        // 给定 [l, r] 区间，要找到这个区间数字按位拼一起得到的值

        // 那么应该是 preCat[r+1] - preCat[l]*(10^(r+1-l))

        // 这里 10^(r+1-l) 可以另外开个数组预处理

        int n = s.size();

        // 下标从 1 开始

        vector<int> preSum(n + 1, 0);

        vector<int> preNonZeroCnt(n + 1, 0);

        vector<long long> preCat(n + 1, 0);

        vector<long long> pow10(n + 1, 1);

        long long modulus = (long long)(1e9 + 7);

        for (int i = 0; i < n; i++) {

            preSum[i + 1] = preSum[i] + (s[i] - '0');

            pow10[i + 1] = (pow10[i] * 10) % modulus;

            if (s[i] != '0') {

                preNonZeroCnt[i + 1] = preNonZeroCnt[i] + 1;

                preCat[i + 1] = (preCat[i] * 10 + (s[i] - '0')) % modulus;

            } else {

                // 如果是 0，是不计入数字拼接的

                preNonZeroCnt[i + 1] = preNonZeroCnt[i];

                preCat[i + 1] = preCat[i];

            }

        }

        vector<int> res;

        for (vector<int>& q : queries) {

            // 额外加上 modulus 来保证得到非负模数

            int l = q[0], r = q[1];

            int sum = preSum[r + 1] - preSum[l];

            int powCnt = preNonZeroCnt[r + 1] - preNonZeroCnt[l];

            long long result =

                ((preCat[r + 1] - preCat[l] * pow10[powCnt] % modulus +

                  modulus) %

                 modulus * sum) %

                modulus;

            res.emplace_back((int)result);

        }

        return res;

    }

};

最新回复 (4)

时雨 07-08 12:42

1楼

好一阵没做每日一题了，抓紧去摸个鱼

Lvvvv 07-08 13:07

2楼

折腾不动了，感觉思路主打一个慢了。

新建一个类，统计总和，长度，10的长度次，拼接值。然后找一个结构维护区间信息就行。这里用ST表复习下。

class Mytype {

    int sum,len_pow10,con;

    static constexpr int mod = 1e9 + 7;

public:

    Mytype():sum(0),len_pow10(1),con(0){}

    Mytype(int sum_, int len_pow10_, int con_) :sum(sum_), len_pow10(len_pow10_), con(con_) {}

    

    Mytype& operator=(Mytype other) {

        swap(other);

        return *this;

    }

    Mytype& operator+=(const Mytype& other) {

        sum += other.sum;

        len_pow10 = (static_cast<long long>(len_pow10) * other.len_pow10) % mod;

        con = (static_cast<long long>(con) * other.len_pow10 % mod + other.con) % mod;

        return *this;

    }

    void swap(Mytype& other) noexcept {

        std::swap(sum,other.sum);

        std::swap(len_pow10,other.len_pow10);

        std::swap(con,other.con);

    }

    int get() const {

        return (static_cast<long long>(sum) * con) % mod;

    }

};



Mytype operator+(const Mytype& a, const Mytype& b) {

    Mytype res = a;

    res += b;

    return res;

}



class ST {

    int n,K;

    vector<vector<Mytype>> st;

public:

    explicit ST(const string& s) : n(s.size()) {

        K = std::bit_width(static_cast<unsigned long>(n)) - 1;

        st.assign(K + 1,vector<Mytype>(n));



        for(int i = 0; i < n; i++) {

            int val = s[i] - '0';

            int len_pow10 = val ? 10 : 1;

            st[0][i] = Mytype(val,len_pow10,val);

        }

        for(int i = 1; i <= K; i++) {

            for(int j = 0; j + (1 << i) <= n; j++) {

                st[i][j] = st[i - 1][j] + st[i - 1][j + (1 << (i - 1))];

            }

        }

    }

    int get(int l, int r) const {

        Mytype res = Mytype();

        for(int i = K ; i >= 0; i--) {

            if((1 << i) <= r - l + 1) {

                res += st[i][l];

                l += 1 << i;

            }

        }

        return res.get();

    }

};

class Solution {

public:

    vector<int> sumAndMultiply(string s, vector<vector<int>>& queries) {

        int n = s.size(),m = queries.size();

        ST sparse_table = ST(s);

        vector<int> res(m);

        for(int i = 0; i < m; i++) {

            int l = queries[i][0],r = queries[i][1];

            res[i] = sparse_table.get(l,r);

        }

        return res;

    }

};

编辑：len好像没啥用，去掉了（

snow 07-08 13:24

3楼

可离线区间查询，很好用莫队维护，时间复杂度 O((m+q)\sqrt{m})，击败了5%的人。

右端点移动

addR：相当于原有数字整体左移一位（乘10），再在末尾加上 d。

x = (x \times 10 + d) \pmod{MOD}

delR：先把末尾的 d 减去，然后整体右移一位取模，即乘以 10 的逆元。

x = (x - d) \times 10^{-1} \pmod{MOD}

左端点移动

addL：d 成为了新的最高位，乘上 10^{cnt}。

x = (d \times 10^{cnt} + x) \pmod{MOD}

delL：先将 cnt 减 1，然后减去最高位的贡献。

x = (x - d \times 10^{cnt}) \pmod{MOD}

constexpr int MOD = 1E9 + 7;

using i64 = long long;

i64 qpow(i64 a, i64 b) {

    i64 res = 1;

    while (b) {

        if (b & 1) res = res * a % MOD;

        a = a * a % MOD;

        b >>= 1;

    }

    return res;

}

class Solution {

public:

    vector<int> sumAndMultiply(string s, vector<vector<int>>& queries) {

        int m = s.size();

        int sz = max(1, (int)sqrt(m));

        int bnum = ceil(1.0 * m / sz);

        vector<int> bel(m);

        for (int i = 1; i <= bnum; i++) {

            for (int j = (i - 1) * sz; j < min(m, i * sz); j++) {

                bel[j] = i;

            }

        }   

        int q = queries.size();

        vector<array<int, 3>> Q(q);

        for (int i = 0; i < q; i++) {

            Q[i] = {i, queries[i][0], queries[i][1]};

        }

        sort(Q.begin(), Q.end(), [&](const auto &a, const auto &b){

            return (bel[a[1]] ^ bel[b[1]]) ? (bel[a[1]] < bel[b[1]]) : ((bel[a[1]] & 1) ? a[2] < b[2] : a[2] > b[2]);

        });

        vector<i64> pw10(m + 1);

        pw10[0] = 1;

        for (int i = 1; i <= m; i++) {

            pw10[i] = pw10[i - 1] * 10 % MOD;

        }

        int l = 0, r = -1;

        i64 x = 0, sum = 0, cnt = 0;

        vector<int> ans(q);

        i64 inv10 = qpow(10, MOD - 2);

        auto addR = [&](int idx) -> void {

            int d = s[idx] - '0';

            if (d == 0) return;

            x = (x * 10 + d) % MOD;

            sum = (sum + d) % MOD;

            cnt++;

        };

        auto addL = [&](int idx) -> void {

            int d = s[idx] - '0';

            if (d == 0) return;

            x = (d * pw10[cnt] + x) % MOD;

            sum = (sum + d) % MOD;

            cnt++;

        };

        auto delR = [&](int idx) -> void {

            int d = s[idx] - '0';

            if (d == 0) return;

            x = (x - d + MOD) % MOD;

            x = x * inv10 % MOD; 

            sum = (sum - d + MOD) % MOD;

            cnt--;

        };

        auto delL = [&](int idx) -> void {

            int d = s[idx] - '0';

            if (d == 0) return;

            cnt--;

            x = (x - d * pw10[cnt] % MOD + MOD) % MOD;

            sum = (sum - d + MOD) % MOD;

        };

        for (int i = 0; i < q; i++) {

            auto [id, ql, qr] = Q[i];

            while (l > ql) addL(--l);

            while (r < qr) addR(++r);

            while (l < ql) delL(l++);

            while (r > qr) delR(r--);

            ans[id] = (x * sum) % MOD;

        }

        return ans;

    }

};

魔法师 07-08 17:33

4楼

思路

其实一开始就想到了用前缀和，但是直觉觉得要在过程中MOD的话求解会像求逆元那样很麻烦，就换了别的思路。早上用模拟和它的优化版本尝试了下，超时了。所以现在还是回到了前缀和，手工算了下，发现其实还挺简单的。原理佬友已经说过了，就不再重复了。

代码

class Solution {

    private static final int MOD = 1_000_000_007;

    private static final int[] pow10 = new int[100001];



    static {

        pow10[0] = 1;

        for (int i = 1; i < 100001; i++) {

            pow10[i] = (int) (pow10[i - 1] * 10L % MOD);

        }

    }



    public int[] sumAndMultiply(String s, int[][] queries) {

        int m = s.length();

        int[] preSum = new int[m + 1];

        int[] preLen = new int[m + 1];

        long[] preNum = new long[m + 1];

        for (int i = 1; i <= m; i++) {

            int num = s.charAt(i - 1) - '0';

            if (num > 0) {

                preSum[i] = preSum[i - 1] + num;

                preLen[i] = preLen[i - 1] + 1;

                preNum[i] = (preNum[i - 1] * 10 + num) % MOD;

            } else {

                preSum[i] = preSum[i - 1];

                preLen[i] = preLen[i - 1];

                preNum[i] = preNum[i - 1];

            }

        }

        int[] ans = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {

            int[] query = queries[i];

            int l = query[0];

            int r = query[1];

            long val = (preNum[r + 1] - preNum[l] * pow10[preLen[r + 1] - preLen[l]] % MOD + MOD) % MOD;

            ans[i] = (int) ((preSum[r + 1] - preSum[l]) * val % MOD);

        }

        return ans;

    }

}

* 帖子来源Linux.do

附近帖子

↑【稳定不掉号 · 长期售后】世事宜 ssyai —— ChatGPT / Claude / Cursor 订阅代充,低价质保,掉号包补,支持开票
↑你所在的行业，新人的成长空间是不是也在明显变小？
↑ollama是真的快
↑劝君莫惜金缕衣，劝君惜取少年时
↑大伙的手机多少钱？
📍 Leetcode每日一题 —— 3756. 连接非零数字并乘以其数字和 II
↓新收了一台MacBook Pro自用，看看什么水平
↓Github限制Star和Watch列表读取权限，大量star-history图片将受此影响无法读取
↓各位佬，有玩无人机的吗，7月1之后可以畅飞吗
↓新开的tello现在不能直接开国际漫游了，各位佬有破的方式嘛
↓没了claudecode，能平替的项目是什么呢

飞读

SomeBottle

主题数
1

帖子数
1

注册排名
3

随机推荐