Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/decode-xored-array/

1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài

Có một mảng số nguyên bị ẩn arr chứa n số nguyên dương.
Mảng arr trên đã được mã hóa trở thành mảng encoded với kích thước n-1, với cách mã hóa là encoded[i] = arr[i] XOR arr[i + 1].
Cho bạn mảng encoded và số nguyên first, trong đó số nguyên first chính là phần tử đầu tiên của mảng arr.
Hãy trả về kết quả là mảng số nguyên bị ẩn arr ban đầu.

Điều kiện bài toán:

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

Bài toán minh họa 1:

Input: encoded = [1,2,3], first = 1
Output: [1,0,2,1]
Explanation: If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

Bài toán minh họa 2:

Input: encoded = [6,2,7,3], first = 4
Output: [4,2,0,7,4]

3. Phân tích

Ố kề, cơ bản thì yêu cầu bài toán cũng không quá đánh đố chúng ta lắm, cho các bạn một mảng đã được mã hóa encoded và số nguyên first, hãy trả về kết quả là mảng số nguyên ban đầu arr. Với công thức mã hóa đề bài đã cho là encoded[i] = arr[i] XOR arr[i + 1], cùng với việc biết được rằng first chính là phần tử đầu tiên của mảng arr, vậy ta có thể suy ra luôn mảng arr có kích thước lớn 1 so với mảng encoded.

int[] arr = new int[encoded.length+1];

Tiếp theo chúng ta cần phải hiểu cách toán tử thao tác bit đơn nhất XOR (kí hiệu là ^) hoạt động như thế nào, tại sao 1 XOR 0 lại ra 1, trong khi 0 XOR 2 lại ra 2.

Tôi sẽ giải thích cho các bạn cách thức hoạt động của toán tử XOR.
Trước hết ta cần biết bit là gì? Bit là đơn vị nhỏ nhất của dữ liệu máy tính, một bit chứa một giá trị nhị phân duy nhất (0 hoặc 1).
Vậy toán tử XOR làm công việc gì? Toán tử XOR trả về giá trị là 1 nếu chỉ một trong các toán hạng là 1 và trả về 0 trong các trường hợp khác.
Ví dụ:
leetcode-1720-1

Từ lí thuyết trên ta thử với phép toán 1 XOR 0 và 4 XOR 6 nhé:

System.out.println(1^0); // kết quả ra là 1.
System.out.println(4^6); // kết quả ra là 2.

Các bạn có thể dùng method Integer.toBinaryString() để quy đổi số thập phân sang số nhị phân.

  • Số 1 khi biểu diễn dưới dạng bit sẽ là 1.
  • Số 0 khi biểu diễn dưới dạng bit sẽ là 0.
  • Số 4 khi biểu diễn dưới dạng bit sẽ là 100.
  • Số 6 khi biểu diễn dưới dạng bit sẽ là 110.

Hãy xem thử 1 XOR 0 chạy như thế nào:
leetcode-1720-2

Tiếp theo là 4 XOR 6:
leetcode-1720-3
010 hay 10 là chuỗi nhị phân của 2.

Đến bước tiếp theo thôi!

4. Chạy code bằng cơm

Đầu tiên là ta cần có một mảng arr mà kích thước của nó bằng encoded.length+1. Và phần tử đầu tiên của mảng arr chính là số nguyên first được cho.
leetcode-1720-4

Tiếp theo chúng ta sẽ thực hiện phép toán so sánh XOR giữa first và phần tử đầu tiên của mảng encoded.
leetcode-1720-5

Cứ như vậy đến hết mảng, vậy là ta đã tìm được mảng ẩn arr chưa được mã hóa ban đầu.
leetcode-1720-6

Thế là xong!

5. Code thôi chờ gì nữa

Công thức đề bài cho để mã hóa là : encoded[i] = arr[i] XOR arr[i + 1].
Vậy nên để tìm được arr[i] ta chỉ cần đổi chỗ thôi: arr[i] = encoded[i] XOR arr[i + 1].
Code của chúng ta sẽ có dạng như sau:

 public int[] decode(int[] encoded, int first) {
     int[] res = new int[encoded.length + 1];
     res[0] = first;

     for (int i = 0; i + 1 < res.length; i++) {
         res[i + 1] = encoded[i] ^ res[i];
     }

     return res;
 }

6. Kết thúc

Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!