3811.交替按位异或分割的数目
给你一个整数数组 nums 以及两个 互不相同 的整数 target1 和 target2。nums 的一个 分割 是指将其划分为一个或多个 连续且非空 的块，这些块在不重叠的情况下覆盖整个数组。
如果一个分割中各块元素的 按位异或 结果在 target1 和 target2 之间 交替 出现，且以 target1 开始，则称该分割是 有效的。
形式上，对于块 b1, b2, … ：
XOR(b1) = target1 XOR(b2) = target2（如果存在） XOR(b3) = target1，以此类推。 返回 nums 的有效分割方案数，结果对 $10^9 $+ 7 取余。
注意： 如果单个块的 按位异或 结果等于 target1，则该分割也是有效的。
1 <= nums.length <= $10^5$ 0 <= nums[i], target1, target2 <= $10^5$ target1 != target2
思路
方法一：递归+记忆化搜索
点击展开/折叠代码
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution
{
int mod = 1e9 + 7, t[2];
vector<vector<long long>> memo;
long long dfs(int i, int state, vector<int> &nums)
{
if (i == nums.size())
{
return 0;
}
if (memo[i][state] != -1)
{
return memo[i][state];
}
long long res = 0;
int cur = 0;
for (int j = i; j < nums.size(); j++)
{
cur ^= nums[j];
if (cur == t[state])
{
if (j == nums.size() - 1)
{
res = (res + 1) % mod;
}
else
{
res = (res + dfs(j + 1, state ^ 1, nums)) % mod;
}
}
}
return memo[i][state]=res;
}
public:
int alternatingXOR(vector<int> &nums, int target1, int target2)
{
int n = nums.size();
t[0] = target1;
t[1] = target2;
memo.resize(n, vector<long long>(2, -1));
return dfs(0, 0, nums);
}
};
时间复杂度：O(n)，其中n为数组nums的长度。 空间复杂度：O(n)，需要使用一个二维数组memo来存储中间结果。 不足以通过所有测试用例，超时。
方法二：动态规划
- 定义两个哈希表f1和f2，分别用于存储当前遍历到的位置i时，前缀异或值为target1和target2的分割方案数。
- 初始化f2[0] = 1，表示前缀异或值为0的分割方案数为1。
- 遍历数组nums，对于每个位置i，计算当前位置的前缀异或值pre。
- 计算以位置i结尾的分割方案数，即f1[target1 ^ pre] + f2[target2 ^ pre]。
- 如果当前位置是数组的最后一个元素，返回计算出的分割方案数。
- 更新f1[pre]和f2[pre]，分别加上以位置i结尾的分割方案数。
- 返回计算出的分割方案数。
- 时间复杂度：O(n)，其中n为数组nums的长度。
- 空间复杂度：O(n)，需要使用两个哈希表来存储分割方案数。
点击展开/折叠代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
int alternatingXOR(vector<int> &nums, int target1, int target2)
{
int mod = 1e9 + 7;
unordered_map<int, int> f1;
unordered_map<int, int> f2 = { {0, 1} };
int pre = 0;
for (int i = 0;; i++)
{
pre ^= nums[i];
int l1 = f2[target1 ^ pre];
int l2 = f1[target2 ^ pre];
if (i == nums.size() - 1)
{
return (l1 + l2) % mod;
}
f1[pre] = (l1 + f1[pre]) % mod;
f2[pre] = (l2 + f2[pre]) % mod;
}
}
};
