算法基础算法

频数前缀和：用前缀和的思想快速计算区间上各个值的计数信息

字数统计: 1.3k字   |   阅读时长: 6分
, ,

摘要: 用前缀和的思想表示前缀的某种状态

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们通过一个问题看一下如何用前缀和的思想表示前缀的一些其它指标，并且能够快速求出区间中的指标值。最常见的指标是频数。

对于数组 $a$，我们对其元素 $a[i]$ 定义某种指标（或者称为状态） $f(a[i])$，如果该指标满足有限可加性：

那么我们就可以通过前缀和的方式维护前缀上该指标 $f$ 的和，然后要求某个区间上的指标 $f(a[i..j])$ 的时候，通过前缀和的差就可以快速得到。具体做法如下。

定义 $s[i]$ 表示前缀 $[0, i-1]$ 上各个元素的指标的和：

于是区间 $[i, j]$ 上的指标为：

如果指标是区间所有元素的加法：$f(a[i..j]) = \sum\limits_{k=i}\limits^{j}a[k]$，也就是 $f(a[i]) = a[i]$，它是满足可加性的，这就是我们熟悉的前缀和。

如果指标是区间所有事件的和事件的概率：$f(a[i..j]) = \sum\limits_{k=i}\limits^{j}P(a[k])$，也就是 $f(a[i]) = P(a[i])$，而概率是满足可加性的，这也是一个例子。

本题中，$f(a[i..j])$ 的含义是 $a[i..j]$ 中某个字符的出现次数，或者某个字符出现次数的奇偶性，这两个指标都满足有限可加性，因此可以用前缀和的思想解决。

$1 题目

给你一个字符串 s，请你对 s 的子串进行检测。

每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], …, s[right]，并从中选择 最多 k 项替换成任何小写英文字母。

如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。

返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。

注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = “aaa” 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）

提示：

1
2
3
4
1 <= s.length, queries.length <= 10^5
0 <= queries[i][0] <= queries[i][1] < s.length
0 <= queries[i][2] <= s.length
s 中只有小写英文字母

示例：
输入：s = “abcda”, queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = “d”，回文。
queries[1] : 子串 = “bc”，不是回文。
queries[2] : 子串 = “abcd”，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = “abcd”，可以变成回文的 “abba”。 也可以变成 “baab”，先重新排序变成 “bacd”，然后把 “cd” 替换为 “ab”。
queries[4] : 子串 = “abcda”，可以变成回文的 “abcba”。

$2 题解

算法: 频数前缀和

1
vector<vector<int>> prefix_cnts(n + 1, vector<int>(26));

前缀状态：prefix_cnts[i + 1] 表示 [0..i] 的字符计数。

[l, r] 的字符计数为 prefix_cnts[r + 1] - prefix_cnts[l]。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<vector<int>> prefix_cnts(n + 1, vector<int>(26));
        for(int i = 1; i <= n; ++i)
        {
            prefix_cnts[i] = prefix_cnts[i - 1];
            ++prefix_cnts[i][s[i - 1] - 'a'];
        }
        int m = queries.size();
        vector<bool> result(m, false);
        for(int i = 0; i < m; ++i)
        {
            int l = queries[i][0], r = queries[i][1];
            int k = queries[i][2];
            vector<int> cnt(26);
            for(int j = 0; j < 26; ++j)
                cnt[j] = prefix_cnts[r + 1][j] - prefix_cnts[l][j];
            int x = 0;
            for(int c: cnt)
                if(c & 1)
                    ++x;
            x /= 2; // 需要的次数
            if(x <= k)
                result[i] = true;
        }
        return result;
    }
};

算法：状态压缩表示奇偶性

1
vector<int> prefix_cnts(n + 1);

前缀状态：prefix_cnts[i + 1] := [0..i] 的字符计数奇偶性。

[l, r] 的字符计数为 prefix_cnts[r + 1] - prefix_cnts[l]。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<int> prefix_cnts(n + 1);
        for(int i = 1; i <= n; ++i)
        {
            prefix_cnts[i] = prefix_cnts[i - 1];
            prefix_cnts[i] ^= 1 << (s[i - 1] - 'a');
        }
        int m = queries.size();
        vector<bool> result(m, false);
        for(int i = 0; i < m; ++i)
        {
            int l = queries[i][0], r = queries[i][1];
            int k = queries[i][2];
            int cnt;
            for(int j = 0; j < 26; ++j)
                cnt = prefix_cnts[r + 1] ^ prefix_cnts[l];
            int x = 0;
            for(int j = 0; j < 26; ++j)
                if(cnt >> j & 1)
                    ++x;
            x /= 2; // 需要的次数
            if(x <= k)
                result[i] = true;
        }
        return result;
    }
};
Share