leetcode打卡-1720解码异或后的数组

五一这几天玩的有点嗨，今天看书脑子嗡嗡的，还是先整点简单题适应一下学习节奏好了。

题目描述

未知整数数组arr由n个非负整数组成。

经编码后变为长度为n - 1的另一个整数数组encoded ，其中encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1]经编码后得到encoded = [1,2,3]。

给你编码后的数组encoded和原数组arr的第一个元素first(arr[0])。

请解码返回原数组arr。可以证明答案存在并且是唯一的。

示例：

输入：encoded = [6,2,7,3], first = 4

输出：[4,2,0,7,4]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/decode-xored-array

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

1. 位运算性质计算

异或满足交换律和结合律，对原式进行计算可得：

• arr[i] ^ arr[i + 1] = encoded[i]
• arr[i] ^ arr[i + 1] ^ encoded[i] = encoded[i] ^ encoded[i] = 0
• arr[i] ^ arr[i + 1] ^ arr[i + 1] ^ encoded[i] = 0 ^ arr[i + 1]
• arr[i] ^ encoded[i] = arr[i + 1]

所以遍历encoded数组即可迭代算出完整的arr数组.

代码如下：

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        # arr[i] ^ arr[i + 1] = encoded[i]，用异或的性质运算得出
        # arr[i + 1] = arr[i] ^ encoded[i]
        length = len(encoded)
        arr = [0] * (length + 1)
        arr[0] = first

        for i in range(length):
            arr[i + 1] = arr[i] ^ encoded[i]

        return arr

练习一下Rust实现

impl Solution {
    pub fn decode(encoded: Vec<i32>, first: i32) -> Vec<i32> {
        let len = encoded.len();
        let mut arr = vec![first; len + 1];
        for i in 0..len {
            arr[i + 1] = encoded[i] ^ arr[i];
        }
        arr
    }
}

• 时间复杂度: O(n)
• 空间复杂度: O(1)

总结

几种位运算的基本规则要记牢。