华为
昨天分享了 华为正式邮件 的事儿，在更早的 OC（电话确认录用）阶段，我就说过，这将会是又一次的大规模开奖。
果不其然，很多小伙伴都在 12-09 当天收到了邮件（又称收奖状）。
但更有意思的是，有收到的正式邮件的同学反映：自己甚至都没收到 HR 打的电话，就收到了正式邮件 🤣🤣🤣
啊这？
那这样的话，是不是之前没 OC，还在泡池子的同学，这次也有可能直接上岸？？（大家赶紧去看一下邮箱
上周我还说，华为 HR 每次打电话的时间点，要么是中午 12 点多，要么是晚上 10 点多，怀疑是在暗示些什么
现在看来人家是真的忙，连这么重要环节都直接跳过了
不过从侧面来看，至少能说明华为 HC 不少，总算是替"世界是个巨大的草台班子"找了个好借口
对此，你怎么看？
...
回归主题。
来一道经典算法题。
题目描述
平台：LeetCode
题号：1734
给你一个整数数组 perm，它是前 n 个正整数的排列，且 n 是个奇数。
它被加密成另一个长度为 n - 1 的整数数组 encoded，满足 encoded[i] = perm[i] XOR perm[i + 1]。
比方说，如果 perm = [1,3,2]，那么 encoded = [2,1]。
给你 encoded 数组，请你返回原始数组 perm。
题目保证答案存在且唯一。
示例 1：
输入：encoded = [3,1]
输出：[1,2,3]
解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]
示例 2：
输入：encoded = [6,5,4,6]
输出：[2,4,1,5,3]
提示：
n是奇数encoded.length = n - 1
基本分析
我们知道异或运算有如下性质：
相同数值异或，结果为 任意数值与 进行异或，结果为数值本身 异或本身满足交换律
本题与 1720. 解码异或后的数组 的主要区别是没有给出首位元素。
因此，求得答案数组的「首位元素」或者「结尾元素」可作为本题切入点。
数学 & 模拟
我们定义答案数组为 ans，ans 数组的长度为 n，且 n 为奇数。
即有 。
给定的数组 encoded 其实是 ，长度为 n - 1。
由于每相邻一位会出现相同的数组成员 ans[x]，考虑“每隔一位”进行异或：
从
encoded的第 位开始，每隔一位进行异或：可得 ，即除了ans数组中的 以外的所有异或结果利用
ans数组是n个正整数的排列，我们可得 ，即ans数组中所有元素的异或结果
将两式进行「异或」，可得 。
有了结尾元素后，问题变为与 1720. 解码异或后的数组 类似的模拟题。
Java 代码：
class Solution {
public int[] decode(int[] encoded) {
int n = encoded.length + 1;
int[] ans = new int[n];
// 求得除了 ans[n - 1] 的所有异或结果
int a = 0, b = 0;
for (int i = 0; i < n - 1; i += 2) a ^= encoded[i];
// 求得 ans 的所有异或结果
for (int i = 1; i <= n; i++) b ^= i;
// 求得 ans[n - 1] 后，从后往前做
ans[n - 1] = a ^ b;
for (int i = n - 2; i >= 0; i--) ans[i] = encoded[i] ^ ans[i + 1];
return ans;
}
}
C++ 代码：
class Solution {
public:
vector<int> decode(vector<int>& encoded) {
int n = encoded.size() + 1;
vector<int> ans(n);
// 求得除了 ans[n - 1] 的所有异或结果
int a = 0, b = 0;
for (int i = 0; i < n - 1; i += 2) a ^= encoded[i];
// 求得 ans 的所有异或结果
for (int i = 1; i <= n; i++) b ^= i;
// 求得 ans[n - 1] 后，从后往前做
ans[n - 1] = a ^ b;
for (int i = n - 2; i >= 0; i--) ans[i] = encoded[i] ^ ans[i + 1];
return ans;
}
};
Python 代码：
class Solution:
def decode(self, encoded: List[int]) -> List[int]:
n = len(encoded) + 1
ans = [0] * n
# 求得除了 ans[n - 1] 的所有异或结果
a, b = 0, 0
for i in range(0, n - 1, 2):
a ^= encoded[i]
# 求得 ans 的所有异或结果
for i in range(1, n + 1):
b ^= i
# 求得 ans[n - 1] 后，从后往前做
ans[n - 1] = a ^ b
for i in range(n - 2, -1, -1):
ans[i] = encoded[i] ^ ans[i + 1]
return ans
TypeScript 代码：
function decode(encoded: number[]): number[] {
const n = encoded.length + 1;
const ans = new Array(n).fill(0);
// 求得除了 ans[n - 1] 的所有异或结果
let a = 0, b = 0;
for (let i = 0; i < n - 1; i += 2) a ^= encoded[i];
// 求得 ans 的所有异或结果
for (let i = 1; i <= n; i++) b ^= i;
// 求得 ans[n - 1] 后，从后往前做
ans[n - 1] = a ^ b;
for (let i = n - 2; i >= 0; i--) ans[i] = encoded[i] ^ ans[i + 1];
return ans;
};
时间复杂度： 空间复杂度：构建同等数量级的答案数组。复杂度为
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
