LintCodeグレイ符号化

1424 ワード

タイトル


グレイ符号化はバイナリデジタルシステムであり,このシステムでは2つの連続した数値は1つのバイナリの差しかない.
非負の整数nが与えられ、コード内のすべてのバイナリの総数を表し、そのグレイ符号化順序を見つけてください.1つのグレイ符号化順序は0で開始され、すべての2 n個の整数を上書きしなければならない.
注意事項
与えられたnの場合、そのグレイ符号化順序は一意ではない.
以上の定義によれば、[0,2,3,1]も有効なグレイ符号化順序である.
サンプルはn=2を与え、[0,1,3,2]を返します.そのグレイ符号化順序は以下の通りである.
00 - 0 01 - 1 11 - 3 10 - 2

ぶんせき


再帰を使って作ることができます.法則は次のとおりです.
一部はn-1ビットグレイコード、さらに1<

コード#コード#

public class Solution {
    /**
     * @param n a number
     * @return Gray code
     */
     public ArrayList grayCode(int n) {
        ArrayList result = new ArrayList();
        if (n <= 1) {
            for (int i = 0; i <= n; i++){
                result.add(i);
            }
            return result;
        }
        result = grayCode(n - 1);
        ArrayList r1 = reverse(result);
        int x = 1 << (n-1);
        for (int i = 0; i < r1.size(); i++) {
            r1.set(i, r1.get(i) + x);
        }
        result.addAll(r1);
        return result;
    }
    
    public ArrayList reverse (ArrayList r) {
        ArrayList rev = new ArrayList();
        for (int i = r.size() - 1; i >= 0; i--) {
            rev.add(r.get(i));
        }
        return rev;
    }
}