??前面的話??

大家好！本篇文章將介紹力扣[1720. 解碼異或后的陣列]題解，展示代碼語言暫時為：C語言與Java語言，（后續會更新C++代碼）

📒博客主頁：未見花聞的博客主頁
🎉歡迎關注🔎點贊👍收藏??留言📝
📌本文由未見花聞原創，CSDN首發！
📆首發時間：🌴2021年11月12日🌴
??堅持和努力一定能換來詩與遠方！
💭刷題推薦書籍：📚《劍指offer第1版》，📚《劍指offer第2版》
💬參考在線編程網站：🌐牛客網🌐力扣
博主的碼云gitee，平常博主寫的程式代碼都在里面，
博主的github，平常博主寫的程式代碼都在里面，
🙏作者水平很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！

??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 = [1,2,3], first = 1
輸出：[1,0,2,1]
解釋：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]
輸入：encoded = [6,2,7,3], first = 4
輸出：[4,2,0,7,4]

提示：

2 < = n < = 104 2 <= n <= 104 2<=n<=104
e n c o d e d . l e n g t h = = n ? 1 encoded.length == n - 1 encoded.length==n?1
0 < = e n c o d e d [ i ] < = 105 0 <= encoded[i] <= 105 0<=encoded[i]<=105
0 < = f i r s t < = 105 0 <= first <= 105 0<=first<=105

💡解題思路

做這道題之前我們需要知道異或這個運算子的性質：

1. 相同兩個數進行異或運算時，結果為 0 0 0，即 a ^ a = 0 a\ \hat{}\ a=0 a ^ a=0
2. 任何數異或 0 0 0，數值不改變，如 a ^ 0 = a a\ \hat{}\ 0=a a ^ 0=a
3. 異或運算滿足交換律與結合律，如 a ^ b ^ c = b ^ a ^ c a\ \hat{}\ b\ \hat{}\ c=b\ \hat{}\ a\ \hat{}\ c a ^ b ^ c=b ^ a ^ c， a ^ ( b + c ) = a ^ b + a ^ c a\ \hat{}\ (b+c)=a\ \hat{}\ b+a\ \hat{}\ c a ^ (b+c)=a ^ b+a ^ c
4. 異或運算具有自反性，即 a ^ b ^ a = b ^ a ^ a = b ^ 0 = b a\ \hat{}\ b\ \hat{}\ a=b\ \hat{}\ a\ \hat{}\ a=b\ \hat{}\ 0=b a ^ b ^ a=b ^ a ^ a=b ^ 0=b

知道這些性質就能解決這道題了！
這道題告訴了我們異或后的陣列 e n c o d e d encoded encoded和原陣列 a r r arr arr的第一個元素 f i r s t first first，其中根據題意（假設陣列下標為 i i i）：
e n c o d e d [ i ] = a r r [ i ] ^ a r r [ i + 1 ] encoded[i]=arr[i]\ \hat{}\ arr[i+1] encoded[i]=arr[i] ^ arr[i+1]
當 i = 0 i=0 i=0時， a r r [ i ] = f i r s t arr[i]=first arr[i]=first，根據異或運算的自反性，有以下推導：
a r r [ 0 ] ^ a r r [ 1 ] ^ f i r s t = e n c o d e d [ 0 ] ^ f i r s t = a r r [ 1 ] arr[0]\ \hat{}\ arr[1]\ \hat{}\ first=encoded[0]\ \hat{}\ first=arr[1] arr[0] ^ arr[1] ^ first=encoded[0] ^ first=arr[1]
讓 f i r s t = a r r [ 1 ] first = arr[1] first=arr[1]，得:
a r r [ 1 ] ^ a r r [ 2 ] ^ f i r s t = e n c o d e d [ 1 ] ^ f i r s t = a r r [ 2 ] arr[1]\ \hat{}\ arr[2]\ \hat{}\ first=encoded[1]\ \hat{}\ first=arr[2] arr[1] ^ arr[2] ^ first=encoded[1] ^ first=arr[2]
再讓 f i r s t = a r r [ 2 ] first = arr[2] first=arr[2]，以此類推能夠求出陣列 a r r arr arr所有元素，
a r r [ i ] ^ a r r [ i + 1 ] ^ a r r [ i ] = e n c o d e d [ i ] ^ a r r [ i ] = a r r [ i + 1 ] arr[i]\ \hat{}\ arr[i+1]\ \hat{}\ arr[i]=encoded[i]\ \hat{}\ arr[i]=arr[i+1] arr[i] ^ arr[i+1] ^ arr[i]=encoded[i] ^ arr[i]=arr[i+1]
a r r [ i + 1 ] = e n c o d e d [ i ] ^ a r r [ i ] arr[i+1]=encoded[i]\ \hat{}\ arr[i] arr[i+1]=encoded[i] ^ arr[i]
調整 f i r s t first first使 f i r s t = a r r [ i ] first=arr[i] first=arr[i]，能夠得到下面結論：
a r r [ i + 1 ] = e n c o d e d [ i ] ^ f i r s t arr[i+1]=encoded[i]\ \hat{}\ first arr[i+1]=encoded[i] ^ first
代碼表示就是：

int i = 0;
arr[0] = first;
for (i = 0; i < encodedSize; i++) 
{
    arr[i + 1] = encoded[i] ^ first;
    first = arr[i + 1]; 
}

所以將陣列 a r r arr arr首個元素與陣列 e n c o d e d encoded encoded首個元素異或就能得到原陣列 a r r arr arr第2個元素，同理陣列 a r r arr arr第2個元素與陣列 e n c o d e d encoded encoded第2個元素異或就能得到原陣列 a r r arr arr第3個元素，以此類推遍歷一遍 e n c o d e d encoded encoded陣列，就能將原陣列 a r r arr arr所有元素都求出來，

🔑源代碼

C語言：

int* decode(int* encoded, int encodedSize, int first, int* returnSize){
    int* arr = (int*)malloc(sizeof(int) * (encodedSize + 1));
    int i = 0;
    arr[0] = first;
    for (i = 0; i < encodedSize; i++) 
    {
        arr[i + 1] = encoded[i] ^ first;
        first = arr[i + 1]; 
    }
    *returnSize = encodedSize + 1;
    return arr;
}

Java語言：

class Solution {
    public int[] decode(int[] encoded, int first) {
        int[] arr = new int[encoded.length + 1];
        arr[0] = first;
        for (int i = 0; i < encoded.length; i++) {
            arr[i + 1] = encoded[i] ^ first;
            first = arr[ i+ 1];
        }
        return arr;
    }
}

🌱總結

本題的解題關鍵為異或運算的自反性，