Như chúng ta biết rằng mã màu xám là một hệ thống số nhị phân trong đó hai giá trị liên tiếp chỉ khác nhau một bit. Giả sử chúng ta có một số nguyên không âm n đại diện cho tổng số bit trong mã. Chúng ta phải in chuỗi mã màu xám. Chuỗi mã màu xám phải bắt đầu bằng 0. Vì vậy, nếu đầu vào là 2, thì kết quả sẽ là [0,1,3,2], điều này là do màu xám của 0 là 00, màu xám của 1 là 01, màu xám của 2 là 11 và màu xám của 3 là 10.
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -
- tạo một mảng ans
- tìm mã màu xám cho từng số và thêm chúng vào mảng ans.
- Để chuyển thành màu xám, chúng tôi sẽ lấy số và thực hiện XOR sau khi chuyển bit số 1 sang phải.
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> grayCode(int n) {
vector <int> ans;
for(int i =0; i<1<<n; i++){
ans.push_back(i^(i>>1));
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.grayCode(4));
} Đầu vào
4
Đầu ra
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, ]