『Leetcode 5239』循环码排列

『题目』：

 给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：

• p[0] = start
• p[i] 和 p[i+1] 的二进制表示形式只有一位不同
• p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同

『限制条件』：

1 <= n <= 16
0 <= start < 2^n

『输入输出』

输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
     所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]

输出：n = 3, start = 2
输出：[2,6,7,5,4,0,1,3]
解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)

『题解』：

这道题要用格雷码转换，格雷码才是循环二进制码，公式为：保留二进制码的最高位作为格雷码的最高位，而次高位格雷码为二进制码的高位与次高位相异或。可以参考格雷码与二进制码的转换

『实现』：

import java.util.ArrayList;
import java.util.List;

public class test3 {


    int D2G(int x)
    {
        return x^(x>>1);
    }


    public List<Integer> circularPermutation(int n, int start) {

        List<Integer> ans = new ArrayList<>();

        int tag = 0;
        int index = 0;

        int length = (1 << n) -1;
        int[] G = new int[length + 1];

        for(int i = 0;i <= length;i++)
        {
            G[i] = D2G(i);
            if(start == G[i])
            {
                tag = i;
            }

        }


        while(index <= length)
        {

            ans.add(new Integer(G[tag]));
            tag = (tag + 1) % (length + 1);
            index++;
        }

        return ans;
    }

    public static void main(String[] args) {

        test3 of = new test3();
        System.out.println(of.circularPermutation(2,3));
    }
}