格雷码

[编程题]格雷码

热度指数：10481 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

格雷码是一种二进制编码系统，如果任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。

给定一个非负整数n，表示代码的位数，打印格雷码的序列。格雷码序列必须以0开头。

例如：给定n=2，返回[0,1,3,2]. 格雷码的序列为：

注意：

对于一个给定的n，格雷码的序列不一定是唯一的，
例如：根据题目描述，[0,2,3,1]也是一个有效的格雷码序列

示例1

输入

输出

[0,1,3,2]

算法知识视频讲解

Java

雨露桥

/*给定n，返回n位格雷码序列。例如：n=2,返回[0(00), 1(01), 3(11), 2(10)]
 *n=1 返回 0 1
 *n=2 返回 0 1 3 2
 *n=3 返回 0 1 3 2 6 7 5 4
 *观察规律：3=1+2,2=0+2; 6=2+4,7=3+4,5=1+4,4=0+4
 */
import java.util.*;
public class Solution {
   public ArrayList<Integer> grayCode(int n) {
       ArrayList<Integer> list = new ArrayList<Integer>();
       list.add(0);
       if(n == 0)
           return list;
       list.add(1);
       if(n == 1)
           return list;
       for(int i = 1;i < n;i ++) { //循环次数
           int size = list.size();
           int increase = (int)Math.pow(2, i); //增量
           for(int j = size - 1;j >= 0;j --) {
               list.add(list.get(j) + increase);
           }
       }
       return list;
   }
}

编辑于 2018-05-17 16:44:54 回复(0)

Java

七仔0312

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> result = new ArrayList<>();
        if (n < 0)
            return result;
        if (n == 0) {
            result.add(0);
            return result;
        }
        result.add(0);
        result.add(1);
        for (int i = 2; i <= n; i++) {
            int size = result.size();
            for (int j = size - 1; j >= 0; j--) {
                result.add(result.get(j) + (1<<(i-1)));
            }
        }
        return result;
    }
}

发表于 2018-03-30 10:58:59 回复(2)

Java

pp11

    public static ArrayList<Integer> grayCode(int n) {
        if (n == 0) {
        	ArrayList<Integer> list = new ArrayList<Integer>();
        	list.add(0);
        	return list;
        }
        if (n == 1) {
        	ArrayList<Integer> list = new ArrayList<Integer>();
        	list.add(0);
        	list.add(1);
        	return list;
        }
        ArrayList<Integer> old = grayCode(n - 1);
        int tempAdd = 1 << n - 1;
        int len = old.size();
        for (int i = len - 1; i >= 0; --i) {
        	old.add(old.get(i) + tempAdd);
        }
        return old;
    }

发表于 2017-08-11 19:48:01 回复(0)

Java

城市里的养猫者

public List<Integer> grayCode(int n) {
    List<Integer> result = new LinkedList<>(); for (int i = 0; i < 1<<n; i++) result.add(i ^ i>>1); return result;
}