罚出地球
这两天最大的乐子新闻，是 俄罗斯政府 对 谷歌 开出的天价罚单，金额高达 20000000000000000000000000000000000（不用数，共 35 位数字）。
这个数字离谱到天了，是打算把谷歌罚出地球 🤣🤣🤣
要知道，2023 年全球的 GDP 总和为 110 万亿美元（15 位数字）。
至于为什么会有这出闹剧，没有特别明确的原因，即使是官方人员（普京的发言人佩斯科夫）在回应相关问题时，也难以言喻的巨额罚款的目的，表示仅为了"希望引起谷歌的注意"。
谢谢，有被磕到。
开出天价罚单，消息传遍全球，仅是希望引起注意。
讲认真的，如果真要追溯俄罗斯政府和谷歌的争端，大概就是谷歌在 2020 年因其旗下视频平台 YouTube 封杀多个俄罗斯媒体账号败诉，从那开始谷歌被处以每日 10 万卢布的罚款，如果 9 个月内未缴纳罚款，罚款金额将每天翻一番，没有上限。
对此，你怎么看？
...
回归主题。
这周连续几天的算法题都给大家上了强度，周五了，也别放松。
题目描述
平台：LeetCode
题号：1787
给你一个整数数组 nums 和一个整数 k 。 区间 [left, right]``（left <= right）的异或结果是对下标位于 left 和 right（包括 left 和 right ）之间所有元素进行 XOR 运算的结果：nums[left] XOR nums[left+1] XOR ... XOR nums[right] 。
返回数组中「要更改的最小元素数」，以使所有长度为 k 的区间异或结果等于零。
示例 1：
输入：nums = [1,2,0,3,0], k = 1
输出：3
解释：将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0]
示例 2：
输入：nums = [3,4,5,2,1,7,3,4,7], k = 3
输出：3
解释：将数组 [3,4,5,2,1,7,3,4,7] 修改为 [3,4,7,3,4,7,3,4,7]
示例 3：
输入：nums = [1,2,4,1,2,5,1,2,6], k = 3
输出：3
解释：将数组[1,2,4,1,2,5,1,2,6] 修改为 [1,2,3,1,2,3,1,2,3]
提示：
基本分析
题目示例所包含的提示过于明显了，估计很多同学光看三个样例就猜出来了：「答案数组必然是每 个一组进行重复的。」
这样的性质是可由「答案数组中所有长度为 的区间异或结果为 」推导出来的：
-
假设区间 长度为 ，其异或结果为 。即
-
长度不变，将区间整体往后移动一位 ，其异或结果为 。即
-
两式结合，中间 区间的数值出现两次，抵消掉最终剩下 ，即推出 必然等于 。
即答案数组必然每 个一组进行重复。
也可以从滑动窗口的角度分析：窗口每滑动一格，会新增和删除一个值。对于异或而言，新增和删除都是对值本身做异或，因此新增值和删除值相等（保持窗口内异或值为 ）。
因此我们将这个一维的输入看成二维，从而将问题转化为：「使得最终每列相等，同时「首行」的异或值为 的最小修改次数。」
当然 和 未必成倍数关系，这时候最后一行可能为不足 个。这也是为什么上面没有说「每行异或结果为 」，而是说「首行异或结果为 」的原因：
动态规划
定义 为考虑前 列，且首行前 列异或值为 的最小修改次数，最终答案为 。
第一维的范围为 ，由输入参数给出；第二维为 ，根据题目给定的数据范围 0 <= nums[i] < 2^10 可得（异或为不进位加法，因此最大异或结果不会超过 ）。
为了方便，我们需要使用哈希表 记录每一列的数字分别出现了多少次，使用变量 统计该列有多少数字（因为最后一行可能不足 个）。
不失一般性的考虑 如何转移:
-
当前处于第 列：由于没有前一列，这时候只需要考虑怎么把该列变成 即可：
-
当前处于其他列：需要考虑与前面列的关系。
我们知道最终的 由两部分组成：一部分是前 列的修改次数，一部分是当前列的修改次数。 这时候需要分情况讨论：
-
仅修改当列的部分数：这时候需要从哈希表中遍历已存在的数，在所有方案中取 ： -
对整列进行修改替换：此时当前列的修改成本固定为 ，只需要取前 列的最小修改次数过来即可：
-
最终 在所有上述方案中取 。为了加速「取前 列的最小修改次数」的过程，我们可以多开一个 数组来记录前一列的最小状态值。
Java 代码：
class Solution {
public int minChanges(int[] nums, int k) {
int n = nums.length, max = 1024;
int[][] f = new int[k][max];
int[] g = new int[k];
for (int i = 0; i < k; i++) {
Arrays.fill(f[i], 0x3f3f3f3f);
g[i] = 0x3f3f3f3f;
}
for (int i = 0, cnt = 0; i < k; i++, cnt = 0) {
// 使用 map 和 cnt 分别统计当前列的「每个数的出现次数」和「有多少个数」
Map<Integer, Integer> map = new HashMap<>();
for (int j = i; j < n; j += k) {
map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);
cnt++;
}
if (i == 0) { // 第 0 列：只需要考虑如何将该列变为 xor 即可
for (int xor = 0; xor < max; xor++) {
f[0][xor] = Math.min(f[0][xor], cnt - map.getOrDefault(xor, 0));
g[0] = Math.min(g[0], f[0][xor]);
}
} else { // 其他列：考虑与前面列的关系
for (int xor = 0; xor < max; xor++) {
f[i][xor] = g[i - 1] + cnt; // 整列替换
for (int cur : map.keySet()) { // 部分替换
f[i][xor] = Math.min(f[i][xor], f[i - 1][xor ^ cur] + cnt - map.get(cur));
}
g[i] = Math.min(g[i], f[i][xor]);
}
}
}
return f[k - 1][0];
}
}
C++ 代码：
class Solution {
public:
int minChanges(vector<int>& nums, int k) {
int n = nums.size(), maxv = 1024;
vector<vector<int>> f(k, vector<int>(maxv, 0x3f3f3f3f));
vector<int> g(k, 0x3f3f3f3f);
for (int i = 0, cnt = 0; i < k; i++, cnt = 0) {
unordered_map<int, int> map;
for (int j = i; j < n; j += k) {
map[nums[j]] += 1;
cnt++;
}
if (i == 0) {
for (int xorVal = 0; xorVal < maxv; xorVal++) {
f[0][xorVal] = min(f[0][xorVal], cnt - map[xorVal]);
g[0] = min(g[0], f[0][xorVal]);
}
} else {
for (int xorVal = 0; xorVal < maxv; xorVal++) {
f[i][xorVal] = g[i - 1] + cnt;
for (auto& entry : map) {
f[i][xorVal] = min(f[i][xorVal], f[i - 1][xorVal ^ entry.first] + cnt - entry.second);
}
g[i] = min(g[i], f[i][xorVal]);
}
}
}
return f[k - 1][0];
}
};
Python 代码：
class Solution:
def minChanges(self, nums: List[int], k: int) -> int:
n, maxv = len(nums), 1024
f = [[0x3f3f3f3f] * maxv for _ in range(k)]
g = [0x3f3f3f3f] * k
for i in range(k):
mapping = defaultdict(int)
cnt = 0
for j in range(i, n, k):
mapping[nums[j]] += 1
cnt += 1
if i == 0:
for xorv in range(maxv):
f[0][xorv] = min(f[0][xorv], cnt - mapping[xorv])
g[0] = min(g[0], f[0][xorv])
else:
for xorv in range(maxv):
f[i][xorv] = g[i - 1] + cnt
for x, y in mapping.items():
f[i][xorv] = min(f[i][xorv], f[i - 1][xorv ^ x] + cnt - y)
g[i] = min(g[i], f[i][xorv])
return f[k - 1][0]
TypeScript 代码：
function minChanges(nums: number[], k: number): number {
const n = nums.length, max = 1024;
const f = new Array(k).fill(0).map(() => new Array(max).fill(0x3f3f3f3f));
const g = new Array(k).fill(0).map(() => 0x3f3f3f3f);
for (let i = 0, cnt = 0; i < k; i++, cnt = 0) {
const map = new Map<number, number>();
for (let j = i; j < n; j += k) {
map.set(nums[j], (map.get(nums[j]) || 0) + 1);
cnt++;
}
if (i === 0) {
for (let xor = 0; xor < max; xor++) {
f[0][xor] = Math.min(f[0][xor], cnt - (map.get(xor) || 0));
g[0] = Math.min(g[0], f[0][xor]);
}
} else {
for (let xor = 0; xor < max; xor++) {
f[i][xor] = g[i - 1] + cnt;
for (let cur of map.keys()) {
const curXor = Number(cur);
f[i][xor] = Math.min(f[i][xor], f[i - 1][xor ^ curXor] + cnt - (map.get(curXor) || 0));
}
g[i] = Math.min(g[i], f[i][xor]);
}
}
}
return f[k - 1][0];
};
-
时间复杂度：共有 个状态需要被转移（其中 固定为 ），每个状态的转移需要遍历哈希表，最多有 个数，复杂度为 。整体复杂度为 -
空间复杂度：，其中 固定为
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
