2026-04-10：连接非零数字并乘以其数字和Ⅱ。用go语言，对每个查询区间 [l, r]，按以下步骤处理字符串中的连续片段 s[l..r]： 1.在该子串

福大大架构师每日一题

发布于 2026-04-14 16:25:59

270

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2026-04-10：连接非零数字并乘以其数字和Ⅱ。用go语言，对每个查询区间 [l, r]，按以下步骤处理字符串中的连续片段 s[l..r]：

1.在该子串中按从左到右的顺序，把所有“非零”字符数字依次拼接成一个新整数 x；如果子串里没有非零数字，则令 x = 0。

2.计算 x 的各位数字之和，得到 sum。

3.计算结果为 x * sum，并对 1000000007 取模。

把每个查询对应的取模结果依次放入数组 answer，返回 answer。

1 <= m == s.length <= 100000。

s 仅由数字组成。

1 <= queries.length <= 100000。

queries[i] = [li, ri]。

0 <= li <= ri < m。

输入： s = "9876543210", queries = [[0,9]]。

输出： [444444137]。

解释：

s[0..9] = "9876543210"

x = 987654321

sum = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45

因此，答案是 987654321 * 45 = 44444444445。

返回结果为 44444444445 mod (1000000007) = 444444137。

题目来自力扣3756。

算法执行详细过程

一、全局预处理：预计算10的幂

1. 目的：因为要拼接数字（比如拼接9、8得到98=9×10+8），需要频繁用到10^k，且所有计算都要对1e9+7取模，提前计算好所有可能用到的10的幂，避免重复计算浪费时间。
2. 规则：
- • 定义常量mod=1e9+7（取模值）、maxN=100001（字符串最大长度）；
- • 初始化数组pow10，pow10[0]=1（10的0次方等于1）；
- • 循环计算：pow10[i] = (pow10[i-1] × 10) % mod，直到计算到pow10[100000]。
3. 作用：后续拼接数字时，直接从数组中取值，时间复杂度为O(1)。

二、核心预处理：遍历字符串，生成3个前缀数组

这一步是离线预处理，只遍历一次字符串s，生成三个辅助前缀数组，所有查询都直接用这三个数组计算，这是保证高效的关键。输入样例：s = "9876543210"（长度10，索引0~9）

前置说明

前缀数组的下标i代表：字符串前i个字符（s[0]~s[i-1]） 的统计结果，方便区间计算。

1. 生成 sumD 数组：数字和前缀和

• 作用：记录字符串前i个字符中，所有数字的总和；
• 计算规则：sumD[i+1] = sumD[i] + 当前字符的数字；
• 样例计算：前1个字符9 → sumD[1]=9；前2个字符9、8 → sumD[2]=17； ... 前9个字符9~1 → sumD[9]=45；前10个字符9~0 → sumD[10]=45（0不影响和）。

2. 生成 sumNonZero 数组：非零数字个数前缀和

• 作用：记录字符串前i个字符中，非零数字的总个数；
• 计算规则：遇到非零数字+1，遇到0不变；
• 样例计算：前9个字符9~1 → 9个非零数字，sumNonZero[9]=9；前10个字符9~0 → 还是9个非零数字，sumNonZero[10]=9。

3. 生成 preNum 数组：非零数字拼接数前缀和

• 作用：记录字符串前i个字符中，所有非零数字按顺序拼接成的数（模mod后的值）；
• 计算规则：遇到非零数字d：preNum[i+1] = (preNum[i] × 10 + d) % mod（拼接逻辑：原数左移一位+新数字）；遇到0：preNum[i+1] = preNum[i]（0直接跳过，不拼接）；
• 样例计算：依次拼接9→98→987→...→987654321，最终preNum[10] = 987654321 % mod。

三、处理每一个查询

对每个查询[l, r]（闭区间，对应字符串s[l]~s[r]），分4步计算结果：

步骤1：转换区间

查询的[l, r]是闭区间，转换为前缀数组的计算区间：l → l，r → r+1。

步骤2：计算区间内的核心参数

1. 区间非零数字个数：length = sumNonZero[r+1] - sumNonZero[l] 样例：查询[0,9] → length=9-0=9。
2. 区间数字和sum：sum = sumD[r+1] - sumD[l] 样例：sum=45-0=45。
3. 区间拼接数x：公式：x = (preNum[r+1] - preNum[l] × pow10[length] % mod + mod) % mod 原理：
- • 前缀拼接数preNum[r+1] = 左边前缀拼接数 × 10^非零个数 + 区间拼接数；
- • 移项得：区间拼接数 = 总拼接数 - 左边前缀拼接数×10^非零个数；
- • 加mod再取模，保证结果为正数。样例：x=987654321。

步骤3：计算最终结果

结果 = (x × sum) % mod 样例：987654321 × 45 = 44444444445，对1e9+7取模得到444444137。

步骤4：存储结果

将每个查询的结果存入答案数组，最终返回答案数组。

时间复杂度 & 额外空间复杂度

1. 总时间复杂度

• 全局预处理10的幂：O(maxN) = O(10⁵)，常数级；
• 字符串遍历生成前缀数组：O(n)，n是字符串长度（≤10⁵）；
• 处理所有查询：O(q)，q是查询次数（≤10⁵）；
• 总时间复杂度：O(n + q) （线性复杂度，完美适配题目10⁵量级的输入要求）

2. 总额外空间复杂度

• 固定数组：pow10[100001] → O(1)；
• 前缀数组：sumD、preNum、sumNonZero，长度均为n+1 → O(n)；
• 答案数组：长度为查询次数q → O(q)；
• 总额外空间复杂度：O(n + q) （线性空间，符合题目内存要求）

总结

1. 核心思路：离线预处理+前缀和，用一次遍历生成辅助数组，让每个查询都能O(1)计算；
2. 关键处理：跳过0、拼接数字用10的幂快速计算、全程取模避免溢出；
3. 效率：时间O(n+q)、空间O(n+q)，完美适配题目10万级数据规模。

Go完整代码如下：

package main

import (
    "fmt"
)

const mod = 1_000_000_007
const maxN = 100_001

var pow10 = [maxN]int{1}

func init() {
    // 预处理 10 的幂
    for i := 1; i < maxN; i++ {
        pow10[i] = pow10[i-1] * 10 % mod
    }
}

func sumAndMultiply(s string, queries [][]int) []int {
    n := len(s)
    sumD := make([]int, n+1)       // s 的前缀和
    preNum := make([]int, n+1)     // s 的前缀对应的数字（模 mod）
    sumNonZero := make([]int, n+1) // s 的前缀中的非零数字个数
    for i, ch := range s {
        d := int(ch - '0')
        sumD[i+1] = sumD[i] + d
        preNum[i+1] = preNum[i]
        sumNonZero[i+1] = sumNonZero[i]
        if d > 0 {
            preNum[i+1] = (preNum[i]*10 + d) % mod
            sumNonZero[i+1]++
        }
    }

    ans := make([]int, len(queries))
    for i, q := range queries {
        l, r := q[0], q[1]+1
        length := sumNonZero[r] - sumNonZero[l]
        x := preNum[r] - preNum[l]*pow10[length]%mod + mod // +mod 保证结果非负
        ans[i] = x * (sumD[r] - sumD[l]) % mod
    }
    return ans
}

func main() {
    s := "9876543210"
    queries := [][]int{{0, 9}}
    result := sumAndMultiply(s, queries)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

MOD = 1_000_000_007
MAX_N = 100_001

# 预处理10的幂
pow10 = [1] * MAX_N
for i in range(1, MAX_N):
    pow10[i] = pow10[i-1] * 10 % MOD

def sum_and_multiply(s: str, queries: list) -> list:
    n = len(s)
    sumD = [0] * (n + 1)          # s的前缀和
    preNum = [0] * (n + 1)        # s的前缀对应的数字（模MOD）
    sumNonZero = [0] * (n + 1)    # s的前缀中的非零数字个数
    
    for i, ch in enumerate(s):
        d = ord(ch) - ord('0')
        sumD[i+1] = sumD[i] + d
        preNum[i+1] = preNum[i]
        sumNonZero[i+1] = sumNonZero[i]
        if d > 0:
            preNum[i+1] = (preNum[i] * 10 + d) % MOD
            sumNonZero[i+1] += 1
    
    ans = []
    for q in queries:
        l, r = q[0], q[1] + 1
        length = sumNonZero[r] - sumNonZero[l]
        x = (preNum[r] - preNum[l] * pow10[length] % MOD + MOD) % MOD
        ans.append(x * (sumD[r] - sumD[l]) % MOD)
    
    return ans

def main():
    s = "9876543210"
    queries = [[0, 9]]
    result = sum_and_multiply(s, queries)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <string>

using namespace std;

constint MOD = 1000000007;
constint MAX_N = 100001;

vector<int> pow10(MAX_N, 1);

// 初始化函数，预处理10的幂
void init() {
    for (int i = 1; i < MAX_N; i++) {
        pow10[i] = (long long)pow10[i-1] * 10 % MOD;
    }
}

vector<int> sumAndMultiply(conststring& s, const vector<vector<int>>& queries) {
    int n = s.length();
    vector<int> sumD(n + 1, 0);        // s的前缀和
    vector<int> preNum(n + 1, 0);      // s的前缀对应的数字（模mod）
    vector<int> sumNonZero(n + 1, 0);  // s的前缀中的非零数字个数

    for (int i = 0; i < n; i++) {
        int d = s[i] - '0';
        sumD[i+1] = sumD[i] + d;
        preNum[i+1] = preNum[i];
        sumNonZero[i+1] = sumNonZero[i];
        if (d > 0) {
            preNum[i+1] = ((long long)preNum[i] * 10 + d) % MOD;
            sumNonZero[i+1]++;
        }
    }

    vector<int> ans(queries.size());
    for (size_t i = 0; i < queries.size(); i++) {
        int l = queries[i][0];
        int r = queries[i][1] + 1;
        int length = sumNonZero[r] - sumNonZero[l];
        long long x = preNum[r] - (long long)preNum[l] * pow10[length] % MOD + MOD;
        x %= MOD;
        ans[i] = (x * (sumD[r] - sumD[l])) % MOD;
    }
    return ans;
}

int main() {
    init();  // 初始化pow10数组

    string s = "9876543210";
    vector<vector<int>> queries = {{0, 9}};
    vector<int> result = sumAndMultiply(s, queries);

    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;

    return0;
}