2진수 한 자리만 차이가 나요. Gray Code.

2037 단어
제목은leetcode에서 유래했다.
제목: 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 Note: For a given n, a gray code sequence is not uniquely defined. For example, [0,2,3,1] is also a valid gray code sequence according to the above definition. For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
사고방식: 제목은 이런 규칙이 순서를 바꾸는 것이 하나만은 아니지만 내가 그것을 썼으면 좋겠다는 것이다.관찰을 통해 나는 그것의 위치 변화 순서는 01100123210 같은 것이어야 한다고 생각한다.
코드:
class Solution {
public:
    vector<int> grayCode(int n) {
         vector<int> v;
         v.push_back(0);
         if(n == 0)
            return v;
        
         int flag = 1;
         int num = 1<<n;
         int i = 0;
         int tmp = 0;
         for(;num>1;num--)
         {
             v.push_back(tmp^(1<<i));
             tmp ^= 1<<i;
             
             if(flag == 1)
            {
                if(i == n-1)
                {
                    i--;
                    flag = -1;
                }
                else
                    i++;
            }
            else
            {
                if(i == 0)
                {
                    i++;
                    flag = 1;
                }
                else
                    i--;
            }
         }
         return v;
    }
};

특이한 방법: 왜 i가 연속적으로 성장할 때 (i>>1)^i는 항상 비트 1의 변화를 일으킬까요?
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> v;
        int num = 1<<n;//num n gray          
        for(int i=0;i<num;i++)
            v.push_back((i>>1)^i); //   i            n^(n/2)
        return v;
    }
};

좋은 웹페이지 즐겨찾기