匹配子序列而非子串的个数 的算法 c++

在C++中，要计算一个整数数组`A`中所有可能连续子序列宽度之和的模`MOD`（这里`MOD`通常设置为1e9+7）并返回其余数，可以使用动态规划的方法，如下面的`sumSubseqWidths`函数所示[^1]：

class Solution {
public:
    int sumSubseqWidths(vector<int>& A) {
        int MOD = (int)(1e9 + 7);
        sort(A.begin(), A.end());
        int n = A.size();
        long res = 0;
        long p = 1; // 二进制累加因子
        for (int i = 0; i < n; ++i) {
            res = (res + (A[i] - A[n - 1 - i]) * p) % MOD; // 计算当前子序列宽度对MOD取余
            p = (p << 1) % MOD; // 更新累加因子
        }
        return (int)((res + MOD) % MOD); // 返回结果
    }
};

这段代码通过遍历数组，对于每个位置`i`，计算从`A[i]`到`A[n - 1 - i]`的子序列宽度，并乘以累加因子`p`，最后对`MOD`取余，保证结果在给定范围内。

相关问题

匹配子序列的个数的算法 c++

C++中有两种方法可以解决给定字符串`s`匹配一组子序列（words）的数量问题：

**方法一：分桶优化法 (时间复杂度O(nm))[^1]**

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>&& words) {
        vector<queue<string>> d(26); // 分桶依据单词首字母
        for(const auto &w : words) d[w[0] - 'a'].enqueue(w);

        int res = 0;
        for(char &c : s) { 
            auto &q = d[c - 'a'];
            while(!q.empty()) {
                auto t = q.front();
                q.dequeue();
                if(t.size() == 1) res++; // 如果字符匹配，计数加一
                else d[t[1] - 'a'].enqueue(t.substr(1));
            }
        }
        return res;
    }
};

在这个方法中，我们把每个单词按照第一个字符分组，然后遍历`s`，每次从对应桶中取出一个子串，如果当前字符匹配，就递减子串长度，直到遇到非空子串。

**方法二：朴素暴力法 (时间复杂度O(n*m*words.size()))**

class Solution {
public:
    bool isSubseq(string &s, string subS) {
        for(int i = 0, j = 0; i < s.size(); i++) {
            if(s[i] == subS[j]) {
                j++;
                if(j == subS.size()) return true;
            }
        }
        return false;
    }

    int numMatchingSubseq(string s, vector<string>&& words) {
        int res = 0;
        for(int i = 0; i < words.size(); i++) {
            if(isSubseq(s, words[i])) res++;
        }
        return res;
    }
};

这个方法更简单，但效率较低，因为它对于每一个`words`中的子串，都会独立地在`s`中进行逐字符的比较。