找出前缀异或的原始数组 图解题解

这道题到底在问什么

输入

pref = [5,2,0,3,1]

输出

[5,7,2,3,2]

输入

pref = [13]

输出

[13]

最优解：一步一步想明白

1. 3记牢这一句口诀:arr[i] 等于 pref[i-1] 异或 pref[i]。异或有个好脾气,一个数和自己异或等于 0,所以相邻两个前缀里公共的部分全抵消了,只剩当前项。下面先把这条抵消关系看清楚,再逐位还原。
2. 4舞台上这一行就是已知的 pref。它的每一位,都是原始数组 arr 从第 0 位一路异或到这一位的结果。比如 pref[3] 就是 arr[0]^arr[1]^arr[2]^arr[3]。现在 arr 是未知的,我们手上只有这行 pref,任务是把 arr 一位一位倒推回来。
3. 5看这两格。pref[1] 里含着 arr[0] 和 arr[1],pref[0] 就是 arr[0]。把这两个前缀异或一下,arr[0] 出现了两次,按位异或里一个数和自己相遇就变 0,于是 arr[0] 被消掉,只剩下 arr[1]。这就是还原的全部秘密:相邻两项一异或,公共的一大段全没了,精准留下当前这一项。
4. 6第 0 位有点特殊,它前面没有 pref[-1] 可用。不过任何数异或 0 都等于它自己,所以我们给它补一个虚拟前缀 0,arr[0] 就等于 0 异或 pref[0],也就是 pref[0] 本身。这样首项和后面所有项就能用同一条公式统一处理了。这里 arr[0] 直接就是 5。
5. 7把第 0 位的结果正式收进右边的面板。arr[0] 等于 pref[0],等于 5。右侧这张表就是我们逐步搭出来的答案数组,先记下第一格 arr[0] 等于 5,接着往后一位一位求。
6. 8轮到第 1 位。紫色指针停在 pref[1]=2,左边这格是 pref[0]=5。按口诀,arr[1] 就等于这相邻两个前缀异或起来。前面已经还原好的部分标成了蓝色,右边面板里也已经躺着 1 个结果。这一步先把要异或的两格锁定,下一帧算出它。
7. 9把这两个数拆成三位二进制看得更透。5 是 101,2 是 010。按位异或的规矩是:同一位上两个数字相同就写 0,不同就写 1。一位一位比下来,得到 111,换回十进制正是 7。异或就是这么算的,没有进位,各位互不干扰。
8. 10算出来了,arr[1] 等于 5 异或 2,结果是 7。把它收进右边面板的第 1 格。到这里已经还原出 2 个数了。继续往后,指针右移一位。
9. 11轮到第 2 位。紫色指针停在 pref[2]=0,左边这格是 pref[1]=2。按口诀,arr[2] 就等于这相邻两个前缀异或起来。前面已经还原好的部分标成了蓝色,右边面板里也已经躺着 2 个结果。这一步先把要异或的两格锁定,下一帧算出它。
10. 12算出来了,arr[2] 等于 2 异或 0,结果是 2。把它收进右边面板的第 2 格。到这里已经还原出 3 个数了。继续往后,指针右移一位。
11. 13轮到第 3 位。紫色指针停在 pref[3]=3,左边这格是 pref[2]=0。按口诀,arr[3] 就等于这相邻两个前缀异或起来。前面已经还原好的部分标成了蓝色,右边面板里也已经躺着 3 个结果。这一步先把要异或的两格锁定,下一帧算出它。
12. 14算出来了,arr[3] 等于 0 异或 3,结果是 3。把它收进右边面板的第 3 格。到这里已经还原出 4 个数了。继续往后,指针右移一位。
13. 15轮到第 4 位。紫色指针停在 pref[4]=1,左边这格是 pref[3]=3。按口诀,arr[4] 就等于这相邻两个前缀异或起来。前面已经还原好的部分标成了蓝色,右边面板里也已经躺着 4 个结果。这一步先把要异或的两格锁定,下一帧算出它。
14. 16把这两个数拆成三位二进制看得更透。3 是 011,1 是 001。按位异或的规矩是:同一位上两个数字相同就写 0,不同就写 1。一位一位比下来,得到 010,换回十进制正是 2。异或就是这么算的,没有进位,各位互不干扰。
15. 17算出来了,arr[4] 等于 3 异或 1,结果是 2。把它收进右边面板的第 4 格。到这里已经还原出 5 个数了。这也是最后一位,arr 全部求完。
16. 18还原完不能拍脑袋就交卷,回头验一遍才踏实。方法是反着来:拿刚求出的 arr,从左往右做前缀异或。设一个累加器 acc 从 0 开始,每读一个 arr[i] 就异或进去,得到的结果应该正好等于 pref[i]。如果每一位都对得上,说明我们还原的 arr 是对的。
17. 19验证第 0 位。把 arr[0]=5 异或进累加器,acc 从 0 变成 5。抬头看 pref[0] 正好是 5,两边一致。这说明 arr 的前 1 位异或起来确实等于 pref[0],还原是准的。继续验下一位。
18. 20验证第 1 位。把 arr[1]=7 异或进累加器,acc 从 5 变成 2。抬头看 pref[1] 正好是 2,两边一致。这说明 arr 的前 2 位异或起来确实等于 pref[1],还原是准的。继续验下一位。
19. 21验证第 2 位。把 arr[2]=2 异或进累加器,acc 从 2 变成 0。抬头看 pref[2] 正好是 0,两边一致。这说明 arr 的前 3 位异或起来确实等于 pref[2],还原是准的。继续验下一位。
20. 22验证第 3 位。把 arr[3]=3 异或进累加器,acc 从 0 变成 3。抬头看 pref[3] 正好是 3,两边一致。这说明 arr 的前 4 位异或起来确实等于 pref[3],还原是准的。继续验下一位。
21. 23验证第 4 位。把 arr[4]=2 异或进累加器,acc 从 3 变成 1。抬头看 pref[4] 正好是 1,两边一致。这说明 arr 的前 5 位异或起来确实等于 pref[4],还原是准的。五位全部验过,验证通过。
22. 24整道题回放一遍。核心只有一条:相邻两个前缀异或一次,公共段全抵消,arr[i] 就等于 pref[i-1] 异或 pref[i],首项特殊,直接等于 pref[0]。我们逐位求出 arr = [5, 7, 2, 3, 2],又反向把它累加异或还原出了原始的 pref,首尾对得上。这就是最终答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def findArray(self, pref: List[int]) -> List[int]:
        return [a ^ b for a, b in pairwise(chain([0], pref))]

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> findArray(vector<int>& pref) {
        int n = pref.size();
        vector<int> ans = {pref[0]};
        for (int i = 1; i < n; ++i) {
            ans.push_back(pref[i - 1] ^ pref[i]);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int[] findArray(int[] pref) {
        int n = pref.length;
        int[] ans = new int[n];
        ans[0] = pref[0];
        for (int i = 1; i < n; ++i) {
            ans[i] = pref[i - 1] ^ pref[i];
        }
        return ans;
    }
}

复杂度

面试官可能追问