题目描述

在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同, 则称这种编码为格雷码(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;
    }
 
}
05-11 13:49