leetcode - 解碼異或后的數(shù)組

題意

未知 整數(shù)數(shù)組 arr 由 n 個(gè)非負(fù)整數(shù)組成。

經(jīng)編碼后變?yōu)殚L(zhǎng)度為 n - 1 的另一個(gè)整數(shù)數(shù)組 encoded，其中 encoded[i] = arr[i] XOR arr[i + 1]。例如，arr = [1,0,2,1] 經(jīng)編碼后得到 encoded = [1,2,3] 。

給你編碼后的數(shù)組 encoded 和原數(shù)組 arr 的第一個(gè)元素 first（arr[0]）。

請(qǐng)解碼返回原數(shù)組 arr ?？梢宰C明答案存在并且是唯一的。

示例

示例 1：

輸入：encoded =?[1,2,3], first = 1
輸出：[1,0,2,1]
解釋?zhuān)喝?arr =?[1,0,2,1]?，那么 first = 1 且 encoded =?[1 XOR 0, 0 XOR 2, 2 XOR 1]?=?[1,2,3]

示例 2：

輸入：encoded =?[6,2,7,3], first = 4
輸出：[4,2,0,7,4]

提示

• 2 <= n <= 104

• encoded.length == n - 1

• 0 <= encoded[i] <= 105

• 0 <= first <= 105

出處

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

思路

這題考的是異或的交換律，會(huì)這題就是送分。簡(jiǎn)單的說(shuō) a ^ b = c, 那么a ^ c = b也是成立的。所以這題我們知道 first，倒推回去也很簡(jiǎn)單。

代碼

/**
?*?@param?{number[]}?encoded
?*?@param?{number}?first
?*?@return?{number[]}
?*/
const?decode?=?function?(encoded,?first)?{
??const?arr?=?[first];
??for?(let?i?=?0;?i?????const?res?=?encoded[i]?^?arr[i];
????arr.push(res);
??}
??return?arr;
};

export?default?decode;

測(cè)試

import?decode?from?'../../code/leetcode/1720';

describe('test?function?decode:?',?()?=>?{
??test('test?case?encoded?=?[1,2,3],?first?=?1',?()?=>?{
????const?res?=?decode([1,?2,?3],?1);
????expect(res).toEqual([1,?0,?2,?1]);
??});

??test('test?case?encoded?=?[6,2,7,3],?first?=?4',?()?=>?{
????const?res?=?decode([6,?2,?7,?3],?4);
????expect(res).toEqual([4,?2,?0,?7,?4]);
??});
});

說(shuō)明

本文首發(fā)于 GitHub 倉(cāng)庫(kù)https://github.com/ataola/coding，線上閱讀地址：https://zhengjiangtao.cn/coding/，轉(zhuǎn)載請(qǐng)注明出處，謝謝！