题目描述
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。
给定一个整数n，请返回n位的格雷码，顺序为从0开始。
测试样例：
1
返回：["0","1"]
代码如下：
package com.yzh.xuexi;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class GeLeiMa {
public static void main(String[] args) {
Scanner scanner =new Scanner(System.in);
while (scanner.hasNext()) {
int n=Integer.valueOf(scanner.nextLine());
List<String>list1=new ArrayList<>((int)Math.pow(2, n));
List<String>list2=new ArrayList<>((int)Math.pow(2, n));
List<String>result=geLeiMa(n, list1, list2);
StringBuilder stringBuilder=new StringBuilder((int)(Math.pow(2, n)*(n+3)+2));
stringBuilder.append("[");
for(String temp:result){
stringBuilder.append("\"");
stringBuilder.append(temp);
stringBuilder.append("\",");
}
stringBuilder.delete(stringBuilder.length()-1, stringBuilder.length());
stringBuilder.append("]");
System.out.println(stringBuilder.toString());
}
scanner.close();
}
private static List<String> geLeiMa(int n,List<String> list1,List<String> list2){
//递归出口
if (n==1) {
list1.add("0");
list1.add("1");
return list1;
}
//递归求n-1位的格雷码
list1=geLeiMa(n-1,list1,list2);
//根据n-1位的格雷码求n位的格雷码
//比如求n=3的gray码，首先知道n=2的gray码是(00,01,11,10)
//那么n=3的gray码其实就是对n=2的gray码首位添加0或1生成的，添加0后变成(000,001,011,010)
//添加1后需要顺序反向就变成(110,111,101,100)
//组合在一起就是(000,001,011,010,110,111,101,100)
for(String temp:list1){
list2.add("0"+temp);
}
for(int i=list1.size()-1;i>=0;i--){
list2.add("1"+list1.get(i));
}
list1.clear();
list1.addAll(list2);
list2.clear();
return list1;
}
}