Medium
题目描述
给你一个整数数组 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 = [2,3,1,4], target1 = 1, target2 = 5
输出: 1
解释：
[2, 3] 的异或值是 1，匹配 target1。
剩余块 [1, 4] 的异或值是 5，匹配 target2。
这是唯一有效的交替分割，所以答案是 1。
示例 2：
输入: nums = [1,0,0], target1 = 1, target2 = 0
输出: 3
解释：
[1, 0, 0] 的异或值是 1，匹配 target1。
[1] 和 [0, 0] 的异或值分别是 1 和 0，匹配 target1 和 target2。
[1, 0] 和 [0] 的异或值分别是 1 和 0，匹配 target1 和 target2。
因此，答案是 3。
示例 3：
输入: nums = [7], target1 = 1, target2 = 7
输出: 0
解释：
[7] 的异或值是 7，不匹配 target1，所以不存在有效分割。
约束条件：
- 1 <= nums.length <= 10^5
- 0 <= nums[i], target1, target2 <= 10^5
- target1 != target2
解题思路
这是一道经典的动态规划问题。核心思路是利用前缀异或和哈希表来高效计算有效分割数量。
关键观察：
- 我们需要找到所有可能的分割点，使得每个块的异或值交替匹配 target1 和 target2
- 使用前缀异或可以快速计算任意区间的异或值：
XOR(nums[i..j]) = prefix[j+1] ^ prefix[i] - 对于位置 i，如果我们想让 nums[last..i] 的异或值等于某个目标值 target，那么需要找到满足条件的前一个分割点 last
动态规划状态设计：
- 用两个哈希表分别记录当前期望下一个块异或值为 target1 和 target2 的前缀异或值的出现次数
- dp1[xor] 表示下一个块需要异或值为 target1 时，前缀异或为 xor 的方案数
- dp2[xor] 表示下一个块需要异或值为 target2 时，前缀异或为 xor 的方案数
转移过程：
- 初始状态：dp1[0] = 1（空前缀，下一个块需要 target1）
- 对于每个位置 i 和当前前缀异或 curr_xor：
- 如果存在前缀 prev_xor 使得 curr_xor ^ prev_xor = target1，则更新 dp2
- 如果存在前缀 prev_xor 使得 curr_xor ^ prev_xor = target2，则更新 dp1
这种方法时间复杂度为 O(n)，空间复杂度为 O(n)。
代码实现
class Solution {
public:
int alternatingXOR(vector<int>& nums, int target1, int target2) {
const int MOD = 1e9 + 7;
unordered_map<int, int> dp1, dp2;
dp1[0] = 1; // 初始状态：空前缀，下一个块需要target1
int curr_xor = 0;
for (int num : nums) {
curr_xor ^= num;
// 计算新的dp值
unordered_map<int, int> new_dp1, new_dp2;
// 如果当前块异或值应该是target1，那么下一个块需要target2
int need_xor1 = curr_xor ^ target1;
if (dp1.count(need_xor1)) {
new_dp2[curr_xor] = (new_dp2[curr_xor] + dp1[need_xor1]) % MOD;
}
// 如果当前块异或值应该是target2，那么下一个块需要target1
int need_xor2 = curr_xor ^ target2;
if (dp2.count(need_xor2)) {
new_dp1[curr_xor] = (new_dp1[curr_xor] + dp2[need_xor2]) % MOD;
}
// 保留原有状态并添加新状态
for (auto& p : dp1) new_dp1[p.first] = (new_dp1[p.first] + p.second) % MOD;
for (auto& p : dp2) new_dp2[p.first] = (new_dp2[p.first] + p.second) % MOD;
dp1 = new_dp1;
dp2 = new_dp2;
}
// 最后一个块必须让整个分割有效，检查是否能以target1结束
int need_final = curr_xor ^ target1;
return dp1.count(need_final) ? dp1[need_final] : 0;
}
};
class Solution:
def alternatingXOR(self, nums: List[int], target1: int, target2: int) -> int:
MOD = 10**9 + 7
dp1 = {0: 1} # 下一个块需要target1的前缀异或值计数
dp2 = {} # 下一个块需要target2的前缀异或值计数
curr_xor = 0
for num in nums:
curr_xor ^= num
new_dp1 = {}
new_dp2 = {}
# 如果当前块异或值应该是target1
need_xor1 = curr_xor ^ target1
if need_xor1 in dp1:
new_dp2[curr_xor] = new_dp2.get(curr_xor, 0) + dp1[need_xor1]
new_dp2[curr_xor] %= MOD
# 如果当前块异或值应该是target2
need_xor2 = curr_xor ^ target2
if need_xor2 in dp2:
new_dp1[curr_xor] = new_dp1.get(curr_xor, 0) + dp2[need_xor2]
new_dp1[curr_xor] %= MOD
# 保留原有状态
for xor_val, count in dp1.items():
new_dp1[xor_val] = new_dp1.get(xor_val, 0) + count
new_dp1[xor_val] %= MOD
for xor_val, count in dp2.items():
new_dp2[xor_val] = new_dp2.get(xor_val, 0) + count
new_dp2[xor_val] %= MOD
dp1, dp2 = new_dp1, new_dp2
# 检查能否以target1结束
need_final = curr_xor ^ target1
return dp1.get(need_final, 0)
public class Solution {
public int AlternatingXOR(int[] nums, int target1, int target2) {
const int MOD = 1000000007;
var dp1 = new Dictionary<int, int> { { 0, 1 } };
var dp2 = new Dictionary<int, int>();
int currXor = 0;
foreach (int num in nums) {
currXor ^= num;
var newDp1 = new Dictionary<int, int>();
var newDp2 = new Dictionary<int, int>();
// 如果当前块异或值应该是target1
int needXor1 = currXor ^ target1;
if (dp1.ContainsKey(needXor1)) {
newDp2[currXor] = (newDp2.GetValueOrDefault(currXor, 0) + dp1[needXor1]) % MOD;
}
// 如果当前块异或值应该是target2
int needXor2 = currXor ^ target2;
if (dp2.ContainsKey(needXor2)) {
newDp1[currXor] = (newDp1.GetValueOrDefault(currXor, 0) + dp2[needXor2]) % MOD;
}
// 保留原有状态
foreach (var pair in dp1) {
newDp1[pair.Key] = (newDp1.GetValueOrDefault(pair.Key, 0) + pair.Value) % MOD;
}
foreach (var pair in dp2) {
newDp2[pair.Key] = (newDp2.GetValueOrDefault(pair.Key, 0) + pair.Value) % MOD;
}
dp1 = newDp1;
dp2 = newDp2;
}
int needFinal = currXor ^ target1;
return dp1.GetValueOrDefault(needFinal, 0);
}
}
var alternatingXOR = function(nums, target1, target2) {
const MOD = 1e9 + 7;
let dp1 = new Map([[0, 1]]);
let dp2 = new Map();
let currXor = 0;
for (const num of nums) {
currXor ^= num;
const newDp1 = new Map();
const newDp2 = new Map();
// 如果当前块异或值应该是target1
const needXor1 = currXor ^ target1;
if (dp1.has(needXor1)) {
newDp2.set(currXor, (newDp2.get(currXor) || 0) + dp1.get(needXor1));
newDp2.set(currXor, newDp2.get(currXor) % MOD);
}
// 如果当前块异或值应该是target2
const needXor2 = currXor ^ target2;
if (dp2.has(needXor2)) {
newDp1.set(currXor, (newDp1.get(currXor) || 0) + dp2.get(needXor2));
newDp1.set(currXor, newDp1.get(currXor) % MOD);
}
// 保留原有状态
for (const [xorVal, count] of dp1) {
newDp1.set(xorVal, (newDp1.get(xorVal) || 0) + count);
newDp1.set(xorVal, newDp1.get(xorVal) % MOD);
}
for (const [xorVal, count] of dp2) {
newDp2.set(xorVal, (newDp2.get(xorVal) || 0) + count);
newDp2.set(xorVal, newDp2.get(xorVal) % MOD);
}
dp1 = newDp1;
dp2 = newDp2;
}
const needFinal = currXor ^ target1;
return dp1.get(needFinal) || 0;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n) - 遍历数组一次，每次操作哈希表的时间为常数 |
| 空间复杂度 | O(n) - 最坏情况下哈希表存储所有不同的前缀异或值 |