This is the 9th day of my participation in the More text Challenge. For details, see more text Challenge

Decoded xOR array (question number 1720)

The title

The unknown integer array ARR consists of n non-negative integers.

After encoding, it becomes another array of integers of length n-1, where encoded[I] = arr[I] XOR arr[I + 1]. For example, arr = [1,0,2,1] gets encoded = [1,2,3].

Give you the encoded array and the first element of the original array arr, first (arr[0]).

Please decode the original array arr. We can prove that the answer exists and is unique.

Example 1:

Input: encoded = [1,2,3], first = 1 If arr = [1,0,2,1] then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]Copy the code

Example 2:

Input: encoded = [6,2,7,3], first = 4Copy the code

Tip:

  • 2 <= n <= 104
  • encoded.length == n - 1
  • 0 <= encoded[i] <= 105
  • 0 <= first <= 105

link

Leetcode-cn.com/problems/de…

explain

This problem, this is the second grade elementary school knowledge.

In fact, this method is more than the dog, the specific will not be introduced, the length is longer, interested in the relevant information can be consulted.

It’s just a current method, or a sign, like addition, subtraction, multiplication and division.

The XOR method has the following characteristics:

  • The xor operation satisfies the commutative and associative laws
  • The xOR of any integer and itself is equal to0, i.e.,The radius x x = 0;
  • Sum of arbitrary integers0The result of xOR is equal to itself, i.eThe radius 0 x = 0 radius = x x.

⊕ here is XOR — the XOR operation.

Let’s look at the commutative and associative properties, which we learned in elementary school, and just like multiplication, you can add any element you want to both sides of the equation, so you start with the normal xor, and you get this 👇 :

Encoded [I - 1] = arr [I - 1) the radius arr encoded [I] [I - 1) the radius arr = arr [I - 1] [I - 1) the radius arr [I] the radius arr [I - 1] arr [I - 1) the radius encoded = [I - 1] Arr [I - 1) the radius arr [I - 1) the radius arr arr [I] [I - 1) the radius encoded [I - 1] = 0 radius arr arr [I] [I - 1) the radius encoded [I - 1] = arr [I]Copy the code

The whole derivation process is to use the three properties mentioned in 👆, so as to get back to the formula of arr[I], get this formula can be back to the original array ~

Your own answer

There is no

A better way (official solution)

The official solution is simpler 👇 :

var decode = function(encoded, first) {
    const n = encoded.length + 1;
    const arr = new Array(n).fill(0);
    arr[0] = first;
    for (let i = 1; i < n; i++) {
        arr[i] = arr[i - 1] ^ encoded[i - 1];
    }
    return arr;
};
Copy the code

Right? It’s that simple. There’s no extra operation.

But the performance is more general, 👇 introduce the author think better method.

Better both ways (save space)

The new encoded array contains a new object that stores the encoded array. The new object directly modifies the original array, known as the encoded array, and returns it.

var decode = function(encoded, first) {
  encoded.unshift(first)
  for (let i = 1; i < encoded.length; i++) {
    encoded[i] = encoded[i - 1] ^ encoded[i]
  }
  return encoded
};
Copy the code

Better Way (save time)

This is pretty much the same as the original method, slightly optimized.

var decode = function(encoded, first) {
  let cur = first
  let result = [first]
  for (let e of encoded) {
    cur = cur ^ e
    result.push(cur)
  }
  return result
};
Copy the code

Both methods are better than the official answer, so you can click here to see the original answer.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ