Như chúng ta biết, mã Gray là hệ nhị phân mà hai giá trị liên tiếp chỉ khác nhau một bit. Cho số nguyên không âm n biểu thị tổng số bit trong mã. Ta phải in dãy mã Gray. Dãy mã Gray phải bắt đầu bằng 0. Ví dụ, n = 2, kết quả [0,1,3,2], vì: gray(0)=00, gray(1)=01, gray(2)=11, gray(3)=10.
Để giải quyết, ta làm theo các bước:
- tạo mảng ans
- tìm mã Gray cho mỗi số và thêm vào ans
- Để chuyển sang Gray, lấy số và thực hiện XOR sau khi dịch phải 1 bit.
Ví dụ
Hãy xem triển khai sau:
#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)); }Input
4
Output
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, ]