[OJ.leetcode] graycode

https://oj.leetcode.com/problems/gray-code/

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

/* testcase를 만들어보고 규칙을 찾아내는 것이 관건 n==1 0 - 1 n==2 00 01 -- 11 10 n==3 000 001 011 010 --- 110 111 101 100 찾은 규칙: 전체를 반으로 쪼개서, first half의 MSB를 0->1로 set하고 역순으로 나머지 half를 구성한다는 사실을 발견 000 001 011 010 에 MSB를 1로 set하고 이를 역순으로 나열하면 110 111 101 100 이 되고 이는 위 n==3인 케이스와 같고 이를 loop또는 recursive 로 구현하면 아래코드와 같고 accepted 확인 완료 class Solution { public: vector<int> grayCode(int n) { vector<int> input(1,0); if(n <= 0) return input; return graycode(n, 0, input); } vector<int> graycode(int n, int currentLength, vector<int> input) { vector<int> temp; if(currentLength < n) { for(int i=0; i<input.size() ; i++) { temp.push_back(input[i]+(1<<currentLength)); } for(int j=temp.size()-1; j>=0 ; j--) { input.push_back(temp[j]); } return graycode(n, currentLength+1, input); } if(currentLength == n) return input; } }; */ //bit별 xor로 구현한 좀 더 효율적인 solution 이진수 abcd에 대해 a^0, a^b, b^c, c^d가 해당 graycode의 각 bit가 된다는 사실을 발견 class Solution { public: vector<int> grayCode(int n) { vector<int> res; int range = pow(2,n)-1; for(int i=0; i<=range; i++) { res.push_back((i>>1)^i); } return res; } };