อย่างที่เราทราบดีว่าโค้ดสีเทาเป็นระบบเลขฐานสองซึ่งค่าที่ต่อเนื่องกันสองค่าต่างกันในหนึ่งบิตเท่านั้น สมมติว่าเรามีจำนวนเต็มไม่เป็นลบ n แทนจำนวนบิตทั้งหมดในโค้ด เราต้องพิมพ์ลำดับของรหัสสีเทา ลำดับรหัสสีเทาต้องขึ้นต้นด้วย 0 ดังนั้นหากอินพุตเป็น 2 ผลลัพธ์จะเป็น [0,1,3,2] เนื่องจากสีเทาของ 0 คือ 00 สีเทาของ 1 คือ 01 สีเทาของ 2 คือ 11 และสีเทาของ 3 คือ 10
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างอาร์เรย์หนึ่งอัน
- ค้นหารหัสสีเทาสำหรับแต่ละหมายเลขแล้วเพิ่มลงในอาร์เรย์
- ในการแปลงเป็นสีเทา เราจะนำตัวเลขและดำเนินการ XOR หลังจากเลื่อนตัวเลข 1 บิตไปทางขวา
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
#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));
} อินพุต
4
ผลลัพธ์
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, ]
