3756. 拼接非零数字并乘以数字和 II

Medium

题目描述

给你一个长度为 m 的数字字符串 s。还给你一个二维整数数组 queries，其中 queries[i] = [li, ri]。

对于每个 queries[i]，提取子字符串 s[li..ri]。然后执行以下操作：

通过按原始顺序拼接子字符串中的所有非零数字来形成一个新整数 x。如果没有非零数字，则 x = 0。
设 sum 为 x 中数字的和。答案是 x * sum。

返回一个整数数组 answer，其中 answer[i] 是第 i 个查询的答案。

由于答案可能很大，返回它们模 10^9 + 7 的结果。

示例 1：

输入：s = "10203004", queries = [[0,7],[1,3],[4,6]]

输出：[12340, 4, 9]

示例 2：

输入：s = "1000", queries = [[0,3],[1,1]]

输出：[1, 0]

示例 3：

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

输出：[444444137]

约束条件：

1 <= m == s.length <= 10^5
s 只包含数字
1 <= queries.length <= 10^5
queries[i] = [li, ri]
0 <= li <= ri < m

解题思路

这道题需要高效处理大量的区间查询，关键在于预处理和前缀和的运用。

核心思路：

预处理非零数字：遍历字符串，记录所有非零数字的值和位置
构建前缀数组：
- digitSum：非零数字的前缀和，用于快速计算某个区间内数字之和
- concatValue：拼接值的前缀信息，结合 pow10 数组可以快速计算拼接后的数字
位置映射：为每个原字符串位置预计算对应的第一个非零数字在压缩数组中的索引

算法步骤：

首先提取所有非零数字及其位置，构建压缩数组
计算前缀和数组：数字和的前缀、拼接值的前缀、10的幂次前缀
为每个查询 [l,r]，通过二分查找或预处理的映射找到对应的非零数字区间
利用前缀和快速计算拼接值 x 和数字和 sum，返回 (x * sum) % MOD

这种方法将单次查询的时间复杂度从 O(n) 降低到 O(1)，特别适合处理大量查询的场景。

推荐解法： 前缀和 + 预处理映射的方法，时间复杂度最优。

代码实现

class Solution {
public:
    vector<int> sumAndMultiply(string s, vector<vector<int>>& queries) {
        const int MOD = 1000000007;
        int n = s.length();
        
        // Extract non-zero digits and their positions
        vector<int> digits;
        vector<int> positions;
        
        for (int i = 0; i < n; i++) {
            if (s[i] != '0') {
                digits.push_back(s[i] - '0');
                positions.push_back(i);
            }
        }
        
        int m = digits.size();
        if (m == 0) {
            return vector<int>(queries.size(), 0);
        }
        
        // Build prefix arrays
        vector<long long> digitSum(m + 1, 0);
        vector<long long> concatValue(m + 1, 0);
        vector<long long> pow10(m + 1, 1);
        
        for (int i = 0; i < m; i++) {
            digitSum[i + 1] = (digitSum[i] + digits[i]) % MOD;
            concatValue[i + 1] = (concatValue[i] * 10 + digits[i]) % MOD;
            pow10[i + 1] = (pow10[i] * 10) % MOD;
        }
        
        // Precompute mapping from original positions to compressed indices
        vector<int> nextNonZero(n, -1);
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j < m && positions[j] < i) j++;
            if (j < m) nextNonZero[i] = j;
        }
        
        vector<int> result;
        for (auto& query : queries) {
            int l = query[0], r = query[1];
            
            int startIdx = nextNonZero[l];
            if (startIdx == -1 || positions[startIdx] > r) {
                result.push_back(0);
                continue;
            }
            
            int endIdx = startIdx;
            while (endIdx < m && positions[endIdx] <= r) {
                endIdx++;
            }
            endIdx--;
            
            // Calculate x using prefix concatenation
            long long x = (concatValue[endIdx + 1] - 
                          (concatValue[startIdx] * pow10[endIdx - startIdx + 1]) % MOD + MOD) % MOD;
            
            // Calculate sum using prefix sum
            long long sum = (digitSum[endIdx + 1] - digitSum[startIdx] + MOD) % MOD;
            
            result.push_back((x * sum) % MOD);
        }
        
        return result;
    }
};

class Solution:
    def sumAndMultiply(self, s: str, queries: List[List[int]]) -> List[int]:
        MOD = 10**9 + 7
        n = len(s)
        
        # Extract non-zero digits and their positions
        digits = []
        positions = []
        
        for i in range(n):
            if s[i] != '0':
                digits.append(int(s[i]))
                positions.append(i)
        
        m = len(digits)
        if m == 0:
            return [0] * len(queries)
        
        # Build prefix arrays
        digit_sum = [0] * (m + 1)
        concat_value = [0] * (m + 1)
        pow10 = [1] * (m + 1)
        
        for i in range(m):
            digit_sum[i + 1] = (digit_sum[i] + digits[i]) % MOD
            concat_value[i + 1] = (concat_value[i] * 10 + digits[i]) % MOD
            pow10[i + 1] = (pow10[i] * 10) % MOD
        
        # Precompute mapping from original positions to compressed indices
        next_non_zero = [-1] * n
        j = 0
        for i in range(n):
            while j < m and positions[j] < i:
                j += 1
            if j < m:
                next_non_zero[i] = j
        
        result = []
        for l, r in queries:
            start_idx = next_non_zero[l]
            if start_idx == -1 or positions[start_idx] > r:
                result.append(0)
                continue
            
            end_idx = start_idx
            while end_idx < m and positions[end_idx] <= r:
                end_idx += 1
            end_idx -= 1
            
            # Calculate x using prefix concatenation
            x = (concat_value[end_idx + 1] - 
                 (concat_value[start_idx] * pow10[end_idx - start_idx + 1]) % MOD) % MOD
            
            # Calculate sum using prefix sum
            sum_val = (digit_sum[end_idx + 1] - digit_sum[start_idx]) % MOD
            
            result.append((x * sum_val) % MOD)
        
        return result

public class Solution {
    public int[] SumAndMultiply(string s, int[][] queries) {
        const int MOD = 1000000007;
        int n = s.Length;
        
        // Extract non-zero digits and their positions
        List<int> digits = new List<int>();
        List<int> positions = new List<int>();
        
        for (int i = 0; i < n; i++) {
            if (s[i] != '0') {
                digits.Add(s[i] - '0');
                positions.Add(i);
            }
        }
        
        int m = digits.Count;
        if (m == 0) {
            return new int[queries.Length];
        }
        
        // Build prefix arrays
        long[] digitSum = new long[m + 1];
        long[] concatValue = new long[m + 1];
        long[] pow10 = new long[m + 1];
        pow10[0] = 1;
        
        for (int i = 0; i < m; i++) {
            digitSum[i + 1] = (digitSum[i] + digits[i]) % MOD;
            concatValue[i + 1] = (concatValue[i] * 10 + digits[i]) % MOD;
            pow10[i + 1] = (pow10[i] * 10) % MOD;
        }
        
        // Precompute mapping from original positions to compressed indices
        int[] nextNonZero = new int[n];
        for (int i = 0; i < n; i++) nextNonZero[i] = -1;
        
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j < m && positions[j] < i) j++;
            if (j < m) nextNonZero[i] = j;
        }
        
        int[] result = new int[queries.Length];
        for (int q = 0; q < queries.Length; q++) {
            int l = queries[q][0], r = queries[q][1];
            
            int startIdx = nextNonZero[l];
            if (startIdx == -1 || positions[startIdx] > r) {
                result[q] = 0;
                continue;
            }
            
            int endIdx = startIdx;
            while (endIdx < m && positions[endIdx] <= r) {
                endIdx++;
            }
            endIdx--;
            
            // Calculate x using prefix concatenation
            long x = (concatValue[endIdx + 1] - 
                     (concatValue[startIdx] * pow10[endIdx - startIdx + 1]) % MOD + MOD) % MOD;
            
            // Calculate sum using prefix sum
            long sum = (digitSum[endIdx + 1] - digitSum[startIdx] + MOD) % MOD;
            
            result[q] = (int)((x * sum) % MOD);
        }
        
        return result;
    }
}

var sumAndMultiply = function(s, queries) {
    const MOD = 1000000007;
    const result = [];
    
    for (const [l, r] of queries) {
        let nonZeroDigits = '';
        
        for (let i = l; i <= r; i++) {
            if (s[i] !== '0') {
                nonZeroDigits += s[i];
            }
        }
        
        if (nonZeroDigits === '') {
            result.push(0);
            continue;
        }
        
        let x = BigInt(nonZeroDigits);
        let sum = 0;
        
        for (const digit of nonZeroDigits) {
            sum += parseInt(digit);
        }
        
        const answer = (x * BigInt(sum)) % BigInt(MOD);
        result.push(Number(answer));
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n + q)	n为字符串长度，q为查询数量。预处理O(n)，每个查询O(1)
空间复杂度	O(n)	存储非零数字、位置、前缀数组和映射数组

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析