89-グレイ符号化

89-グレイ符号化

グレイ符号化はバイナリデジタルシステムであり,このシステムでは2つの連続した数値は1桁の差しかない.
符号化総ビット数を表す非負の整数nが与えられ、そのグレイ符号化シーケンスが印刷される.グレイ符号化シーケンスは0で始まる必要があります.
例1:

 : 2
 : [0,1,3,2]
 :
00 - 0
01 - 1
11 - 3
10 - 2

  n， 。
 ，[0,2,3,1]  。

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

例2:

 : 0
 : [0]
 :   0  。
       n  ，  2n。  n = 0  ，  20 = 1。
      ，  n = 0  ，  [0]。

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/gray-code著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.

    public List grayCode(int n) {
        List res = new ArrayList<>();
        if(n == 0) {
            res.add(0);
            return res;
        }

        res.add(0);
        res.add(1);
        int i = 1;
        while (n > 1){
            Deque tmp = new LinkedList<>();
            for(Integer item : res) {
                tmp.addFirst(item + (int) Math.pow(2, i));
            }
            res.addAll(tmp);
            n--;
            i++;
        }
        return res;
    }

    public List grayCode(int n) {
        /**
         , G(i) = i ^ (i/2);
          n = 3: 
        G(0) = 000, 
        G(1) = 1 ^ 0 = 001 ^ 000 = 001
        G(2) = 2 ^ 1 = 010 ^ 001 = 011 
        G(3) = 3 ^ 1 = 011 ^ 001 = 010
        G(4) = 4 ^ 2 = 100 ^ 010 = 110
        G(5) = 5 ^ 2 = 101 ^ 010 = 111
        G(6) = 6 ^ 3 = 110 ^ 011 = 101
        G(7) = 7 ^ 3 = 111 ^ 011 = 100
        **/
        List ret = new ArrayList<>();
        for(int i = 0; i < 1<>1);
        return ret;
    }