算法-A071-前缀异或和

Algorithms Comments

前缀异或和问题是通过 前缀和 + 状态压缩 + 哈希表来处理连续 xxx 问题，发现是有规律的

  • 通过前缀异或和获取每个位置的状态
  • 使用哈希表记录每个状态第一次出现的位置
  • 如果状态小于一定数量，可以通过状态压缩(BitMask)记录

问题

问题1：统计美丽子数组数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    long long beautifulSubarrays(vector<int>& nums) {
        long long res = 0;
        //计算前缀异或和！！！
        vector<int> temp(nums.size() + 1);
        for(int i = 0; i < nums.size(); i++) {
            temp[i + 1] = temp[i] ^ nums[i]; //temp[i] 表示包含了 nums[i] 的异或和
        }
        //计算数据对总数！！！
        unordered_map<int, int>dict;
        for(int x : temp) {
            //printf("%d %d \n", x, dict[x]);
            res += dict[x]++;   //这样算，每次 加1 类似 1 + 2 + 3 + n -> 计算 n个数字一共有多少个数据对
        }

        return res;
    }
};

这里有两个知识点：

  1. 子数组的异或和等于前缀和的异或和 AB ^ A = B
  2. 注意 res += dict[mod]++;,可以理解为动态计算 1 + 2 + 3 + .... + n

问题2：和可被 K 整除的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> dict;
        dict[0] = 1;
        int res = 0;
        int s = 0;
        for(int i = 0; i < nums.size(); i++) {
            s += nums[i];
						//当被除数为负数时取模结果为负数，需要纠正(保证取余一定为正)
            int mod = (s % k + k) % k;
            res += dict[mod]++;
        }
        return res;
    }
};

这里的知识点表示：

  1. C++取余是向0取整，所以就有

    1
    2
    3
    4
    5
    6
    7/4= 1
    7/(-4)= -1
    7%4= 3
    7%(-4)= 3
    (-7)/4= -1
    (-7)%4= -3

  2. 一个负数取余可能出现模为负数的情况，可以通过 mod = (s % k + k) % k 解决

问题3：找出最长的超赞子字符串

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
class Solution {
public:
    int longestAwesome(string s) {
        int temp = 0;
        unordered_map<int, int> dict;
        int l = 0;
        dict[0] = -1;
        for(int i = 0; i < s.size(); i++) {
            temp ^= (1 << (s[i] - '0'));

						//status1 与 status2 两个状态相同，那么所有的都出现了偶数次
            if(dict.count(temp) != 0) {
                l = max(l, i - dict[temp]);
            } else {
                dict[temp] = i;
            }
						//status1 与 status2 只差一位不同，找出这一位
            for(int k = 0; k < 10; k++) {
                if(dict.count(temp ^ (1 << k))) {
                    l = max(l, i - dict[temp ^ (1 << k)]);
                }
            }
        }
        return l;

    }
};

注意点：

  1. 为什么在查找 只差一位的情况时没有进行存储，因为当前前缀异或和的值是 temp

总结

  • 遇到奇偶个数校验，想到 XOR
  • 遇到有限的参数(小于20个)表状态， 想到状态压缩 （bitmask）
  • 遇到求最长的连续子串使得和为k 想到 前缀和 + 哈希表 记录第一次出现某一状态的位置。

顺序练习

  • 两数之和
  • 和为K的子数组
  • 和可被K整除的子数组
  • 使数组和能被 P 整除
  • 连续的子数组和
  • 连续数组
  • 面试题 17.05. 字母与数字
  • 最美子字符串的数目
  • 和相同的二元子数组
  • 每个元音包含偶数次的最长子字符串
  • 找出最长的超赞子字符串