class Solution { public List<Integer> circularPermutation(int n, int start) { } }
因为题目要求相邻两位的二进制表示形式只有一位不一样, 首尾的二进制表示形式也只有一位不一样 并且还规定了该排列以哪一个值开头.
通过对题目示例分析可以看出当以0为开头时 当n等于1时:排列为[0,1] 二进制表示方式为(00,01)
当n等于2时,排列为[0, 1, 3, 2] 二进制表示方式为(00,01,11,10)
当n等于3时,排列为[0, 1, 3, 2, 6, 7, 5, 4] 二进制表示方式为(000,001,011,010,110,111,101,100)
可以看出来n的排列 左半边是n-1的排列,右半边是左半边加上2^n-1然后再反向添加到后面 所以解题步骤 1)先求出以0开头的序列,然后根据传入的z进行重新连接即可 2)求n的排列先递归求出n-1的排列,递归终止条件为n=1的时候 3)得到n-1的排列记为tail,对其进行增值并且逆转,然后再添加到其后面
public List<Integer> circularPermutation(int n,int start){ /** * n = 2 start = 3 * n = 3 start = 2 * 先得到处理好后的结果,将其以p[0]=start开头 * 比如是[0,1,3,2]要处理成[3,2,0,1] * 比如是[0,1,3,2,6,7,5,4]处理成[2,6,7,5,4,0,1,3] */ List<Integer> list = build(n); List<Integer> result = new ArrayList<Integer>(); //在list中找到start的位置 Integer index = list.indexOf(start); result.addAll(list.subList(index, list.size())); result.addAll(list.subList(0, index)); return result; } /** * 返回n的排列(0,1,2,....2^n-1) * 使其满足p[i]和p[i+1]的二进制表示形式只有一位不同 * 满足p[0]和p[2^n-1]的二进制表示形式也只有一位不同 * 例如 当n等于1时 返回 [0,1] * (00,01) * 当n等于2时 返回 [0,1,3,2] * (00,01,11,10) * 当n等于3时 返回 [0, 1, 3, 2, 6, 7, 5, 4] * (000,001,011,010,110,111,101,100) * * 求n的排列可以发现结果是n-1的排列加上2^n-1然后反向添加在后面 * @param n * @return */ private List<Integer> build(int n){ List<Integer> result = new ArrayList<Integer>(); //n等于1直接返回结果[0,1] if(n == 1){ result.add(0); result.add(1); return result; } //得到n-1的排列 ArrayList<Integer> tail; tail = (ArrayList<Integer>) build(n-1); result = (List<Integer>) tail.clone(); //对其元素进行加上2^n-1并且倒置过来 Integer index = tail.size()-1; while(index >=0){ tail.set(index, (int) (tail.get(index)+Math.pow(2, n-1))); --index; } Collections.reverse(tail); //添加到结果中. result.addAll(tail); return result; }