【LeetCode系列】1720. 解码异或后的数组

⭐️前面的话⭐️

大家好!本篇文章将介绍力扣[1720. 解码异或后的数组]题解,展示代码语言暂时为:C语言与Java语言。(后续会更新C++代码)

?博客主页:未见花闻的博客主页
?欢迎关注?点赞?收藏⭐️留言?
?本文由未见花闻原创,CSDN首发!
?首发时间:?2021年11月12日?
✉️坚持和努力一定能换来诗与远方!
?刷题推荐书籍:?《剑指offer第1版》,?《剑指offer第2版》
?参考在线编程网站:?牛客网?力扣
博主的码云gitee,平常博主写的程序代码都在里面。
博主的github,平常博主写的程序代码都在里面。
?作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!



1


⭐️1720. 解码异或后的数组⭐️

?题目详情

一个未知整数数组 arrn个非负整数组成。经编码后变为长度为 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==n1

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

来源:力扣(LeetCode)链接:1720. 解码异或后的数组

?解题思路

做这道题之前我们需要知道异或这个运算符的性质:

  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;
    }
}

?总结

本题的解题关键为异或运算的自反性。

觉得文章写得不错的老铁们,点赞评论关注走一波!谢谢啦!

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码

)">
< <上一篇
下一篇>>