Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 0df8e90

Browse filesBrowse files
yanglbmeyanglbme
authored
feat: add solutions to lc problem: No.1720 (doocs#3146)
No.1720.Decode XORed Array
1 parent 4d9760a commit 0df8e90
Copy full SHA for 0df8e90

File tree

Expand file treeCollapse file tree

6 files changed

+99
-21
lines changed
Open diff view settings
Filter options
Expand file treeCollapse file tree

6 files changed

+99
-21
lines changed
Open diff view settings
Collapse file

‎solution/1700-1799/1720.Decode XORed Array/README.md‎

Copy file name to clipboardExpand all lines: solution/1700-1799/1720.Decode XORed Array/README.md
+41-6Lines changed: 41 additions & 6 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,29 @@ tags:
6161

6262
<!-- solution:start -->
6363

64-
### 方法一
64+
### 方法一：位运算
65+
66+
根据题目描述，有：
67+
68+
$$
69+
\text{encoded}[i] = \text{arr}[i] \oplus \text{arr}[i + 1]
70+
$$
71+
72+
如果我们将等式两边同时异或上 $\text{arr}[i]$，那么就会得到：
73+
74+
$$
75+
\text{arr}[i] \oplus \text{arr}[i] \oplus \text{arr}[i + 1] = \text{arr}[i] \oplus \text{encoded}[i]
76+
$$
77+
78+
即：
79+
80+
$$
81+
\text{arr}[i + 1] = \text{arr}[i] \oplus \text{encoded}[i]
82+
$$
83+
84+
根据上述推导，我们可以从 $\text{first}$ 开始，依次计算出数组 $\text{arr}$ 的每一个元素。
85+
86+
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组的长度。
6587

6688
<!-- tabs:start -->
6789

@@ -98,9 +120,10 @@ class Solution {
98120
class Solution {
99121
public:
100122
vector<int> decode(vector<int>& encoded, int first) {
101-
vector<int> ans{{first}};
102-
for (int i = 0; i < encoded.size(); ++i)
103-
ans.push_back(ans[i] ^ encoded[i]);
123+
vector<int> ans = {{first}};
124+
for (int x : encoded) {
125+
ans.push_back(ans.back() ^ x);
126+
}
104127
return ans;
105128
}
106129
};
@@ -111,13 +134,25 @@ public:
111134
```go
112135
func decode(encoded []int, first int) []int {
113136
ans := []int{first}
114-
for i, e := range encoded {
115-
ans = append(ans, ans[i]^e)
137+
for i, x := range encoded {
138+
ans = append(ans, ans[i]^x)
116139
}
117140
return ans
118141
}
119142
```
120143

144+
#### TypeScript
145+
146+
```ts
147+
function decode(encoded: number[], first: number): number[] {
148+
const ans: number[] = [first];
149+
for (const x of encoded) {
150+
ans.push(ans.at(-1)! ^ x);
151+
}
152+
return ans;
153+
}
154+
```
155+
121156
<!-- tabs:end -->
122157

123158
<!-- solution:end -->
Collapse file

‎solution/1700-1799/1720.Decode XORed Array/README_EN.md‎

Copy file name to clipboardExpand all lines: solution/1700-1799/1720.Decode XORed Array/README_EN.md
+43-8Lines changed: 43 additions & 8 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,29 @@ tags:
5959

6060
<!-- solution:start -->
6161

62-
### Solution 1
62+
### Solution 1: Bit Manipulation
63+
64+
Based on the problem description, we have:
65+
66+
$$
67+
\text{encoded}[i] = \text{arr}[i] \oplus \text{arr}[i + 1]
68+
$$
69+
70+
If we XOR both sides of the equation with $\text{arr}[i]$, we get:
71+
72+
$$
73+
\text{arr}[i] \oplus \text{arr}[i] \oplus \text{arr}[i + 1] = \text{arr}[i] \oplus \text{encoded}[i]
74+
$$
75+
76+
Which simplifies to:
77+
78+
$$
79+
\text{arr}[i + 1] = \text{arr}[i] \oplus \text{encoded}[i]
80+
$$
81+
82+
Following the derivation above, we can start with $\text{first}$ and sequentially calculate every element of the array $\text{arr}$.
83+
84+
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array.
6385

6486
<!-- tabs:start -->
6587

@@ -69,8 +91,8 @@ tags:
6991
class Solution:
7092
def decode(self, encoded: List[int], first: int) -> List[int]:
7193
ans = [first]
72-
for e in encoded:
73-
ans.append(ans[-1] ^ e)
94+
for x in encoded:
95+
ans.append(ans[-1] ^ x)
7496
return ans
7597
```
7698

@@ -96,9 +118,10 @@ class Solution {
96118
class Solution {
97119
public:
98120
vector<int> decode(vector<int>& encoded, int first) {
99-
vector<int> ans{{first}};
100-
for (int i = 0; i < encoded.size(); ++i)
101-
ans.push_back(ans[i] ^ encoded[i]);
121+
vector<int> ans = {{first}};
122+
for (int x : encoded) {
123+
ans.push_back(ans.back() ^ x);
124+
}
102125
return ans;
103126
}
104127
};
@@ -109,13 +132,25 @@ public:
109132
```go
110133
func decode(encoded []int, first int) []int {
111134
ans := []int{first}
112-
for i, e := range encoded {
113-
ans = append(ans, ans[i]^e)
135+
for i, x := range encoded {
136+
ans = append(ans, ans[i]^x)
114137
}
115138
return ans
116139
}
117140
```
118141

142+
#### TypeScript
143+
144+
```ts
145+
function decode(encoded: number[], first: number): number[] {
146+
const ans: number[] = [first];
147+
for (const x of encoded) {
148+
ans.push(ans.at(-1)! ^ x);
149+
}
150+
return ans;
151+
}
152+
```
153+
119154
<!-- tabs:end -->
120155

121156
<!-- solution:end -->
Collapse file

‎solution/1700-1799/1720.Decode XORed Array/Solution.cpp‎

Copy file name to clipboard
+4-3Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,10 @@
11
class Solution {
22
public:
33
vector<int> decode(vector<int>& encoded, int first) {
4-
vector<int> ans{{first}};
5-
for (int i = 0; i < encoded.size(); ++i)
6-
ans.push_back(ans[i] ^ encoded[i]);
4+
vector<int> ans = {{first}};
5+
for (int x : encoded) {
6+
ans.push_back(ans.back() ^ x);
7+
}
78
return ans;
89
}
910
};
Collapse file

‎solution/1700-1799/1720.Decode XORed Array/Solution.go‎

Copy file name to clipboard
+2-2Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
func decode(encoded []int, first int) []int {
22
ans := []int{first}
3-
for i, e := range encoded {
4-
ans = append(ans, ans[i]^e)
3+
for i, x := range encoded {
4+
ans = append(ans, ans[i]^x)
55
}
66
return ans
77
}
Collapse file

‎solution/1700-1799/1720.Decode XORed Array/Solution.py‎

Copy file name to clipboard
+2-2Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
class Solution:
22
def decode(self, encoded: List[int], first: int) -> List[int]:
33
ans = [first]
4-
for e in encoded:
5-
ans.append(ans[-1] ^ e)
4+
for x in encoded:
5+
ans.append(ans[-1] ^ x)
66
return ans
Collapse file

‎solution/1700-1799/1720.Decode XORed Array/Solution.ts‎

Copy file name to clipboard
+7Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
function decode(encoded: number[], first: number): number[] {
2+
const ans: number[] = [first];
3+
for (const x of encoded) {
4+
ans.push(ans.at(-1)! ^ x);
5+
}
6+
return ans;
7+
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.