首页 > 试题广场 >

格雷码

[编程题]格雷码

热度指数：10467 时间限制：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]

算法知识视频讲解

可乐猪

//随着n变大，前面的数不用动，后面的数倒着拿出来再在首部加1即可
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        result.push_back(0);
        for (int i = 0; i < n; i++) {
            const int hight_bit = 1 << i;
            for (int j = result.size() - 1; j >= 0; j--) //第二遍反着遍历，形成对称
                result.push_back(hight_bit | result[j]);
        }
        return result;
    }
};

编辑于 2016-09-01 20:00:20 回复(7)

RainDrop

//LeetCode上的题目，如下
import java.util.*;
public class Solution {
    public ArrayList<Integer> grayCode(int n) {
		ArrayList<Integer> arr = new ArrayList<Integer>();
        int num = 1 << n;
        for(int i = 0; i < num; ++i){
         	arr.add(i>>1^i);   
        }
        return arr;
    }
}

发表于 2016-03-26 12:08:09 回复(19)

viser_zj

class Solution {
public:
	vector<int> grayCode(int n) {
		vector<int> result(pow(2,n));
		for (int i=1;i<=n;++i)
		{
			int size = 1<<i;
			int flag = 1<<(i-1);
			int index = 0;
			for (int j=size-1;2*j>=size;--j)
			{
				result[j] = result[index++]|flag;  //左部插入1
			}
		}
		return result;
	}
};

当n=1时，为[0,1]
当n=2时，为[00,01,11,10]
当n=3时，为[000,001,011,010,110,111,101,100]
由此可以看出新的序列其实是在前面序列基础上插入新的值
其中前半部分的数值不变，后半部分的数值为上个序列中每个元素第n个位变1，逆向插入

发表于 2016-08-13 21:44:28 回复(1)

何恺明的小迷妹

这道题难在找 dp 方程
先看n=2 (00, 01, 11, 10) 
n = 3      ((000, 001, 011, 010), (100,101,111,110))
以此类推， n=k时，就是在n=k-1的前面加上0或者1，然后使得数据扩大2倍
DP转移方程如下：
dp[k] = dp[k-1] | 1<<n    其中     2^(n-1)=<k<2^n
class Solution {
public:
    vector<int> grayCode(int n) {
       vector<int> res(1,0);
       for(int i=0; i<n;i++){
           for(int j=res.size()-1; j>=0; j--){
               res.push_back(res[j]|1<<i); 
           } 
       }
       return res;
    }
};

发表于 2018-08-26 09:45:58 回复(0)

小白debug

class Solution {
public:
vector<int> grayCode(int n) {

    vector<int> res;

    res.push_back(0);
    for(int i = 0; i < n; ++i)
    {
        int high_bit = 1 << i;
        for(int j = res.size() - 1; j >=0 ; --j)
        {
            res.push_back(high_bit|res[j]);
        }
    }
    return res;
}

};

发表于 2018-08-17 13:44:54 回复(0)

我菜得抠脚

/*
*规律是，后面每一个list的元素等于前面list顺序遍历的结果在每个元素前面+“0”,再逆序遍历
*每个元素前面+"1"，可以先存储string格式方便处理，最后转换再返回int的集合
*就可以用动态规划解决了。
*/ 
public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> list=new ArrayList<>();
        ArrayList<String> pre=new ArrayList<>();
                 if(n==0) {
            list.add(0);
            return list;
        }
                 pre.add("0");
        pre.add("1");
        ArrayList<String> now;
        for(int i=2;i<=n;i++) {
            now=new ArrayList<>();
            for(int j=0;j<pre.size();j++) {
                String str = "0"+pre.get(j);
                now.add(str);
            }
            for(int j=pre.size()-1;j>=0;j--) {
                String str = "1"+pre.get(j);
                now.add(str);
            }
            pre=now;
        }

        for(int i=0;i<pre.size();i++) {
            int num=getNum(pre.get(i));
            list.add(num);
        }
        return list;
    }
    
    public int getNum(String str) {
        char[] array=str.toCharArray();
        int i=0;
        int res=0;
        while(i<array.length) {
            if(array[i]=='1') {
                res+=Math.pow(2, array.length-1-i);
            }
            i++;
        }
        return res;
    }

发表于 2018-06-18 14:10:33 回复(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

雨露桥

/*给定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)

NewBeeeee

//G(i)=i^(i/2)
import java.util.*;
class Solution{
    public ArrayList<Integer> grayCode(int n){
         ArrayList<Integer> result=new ArrayList<>();
         for(int i=0;i<1<<n;i++){
                result.add(i^i>>1);
          }
    }
}

发表于 2017-12-25 16:19:37 回复(0)

C/C++

nbgao

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        result.push_back(0);
        for(int i=0;i<n;i++)
        {
        	int high_bit = 1<<i;
        	for(int j=result.size()-1;j>=0;j--)
        	{
        		int num = high_bit | result[j];
        		result.push_back(num);
			}
		}
		return result;
    }
};

发表于 2017-08-01 01:25:54 回复(0)

LinuX18

class Solution {
public:
/**
n = 0: 0
n = 1: 0, 1
n = 2: 00, 01, 11, 10  (0, 1, 3, 2)
n = 3: 000, 001, 011, 010, 110, 111, 101, 100 (0, 1, 3, 2, 6, 7, 5, 4)
*/
/// 推广：n = i的gray code的前一半包括了n = i-1的所有gray code，而后一半则为前一半逆序后加上2^(i-1)。
vector<int> grayCode(int n)
{
    vector<int> res;
    res.push_back(0);
    int inc = 1;
    for(int i=1;i<=n;i++)
    {
        for(int j=res.size()-1;j>=0;j--)
            res.push_back(res[j]+inc);
        inc <<= 1;
    }
    return res;
}
};

发表于 2017-07-13 20:47:06 回复(0)

xcx920317

/*递归
先顺序往下在高位加0
再逆序往上在高位加1
组成的新排列满足要求
*/

class Solution {

public:

vector<int> grayCode(int n) {

vector<int>v;

if(n==0){

v.push_back(0);

return v;

}

v = grayCode(n-1);

int len = (int)v.size();

for(int i = 0 ;i < len;i++){

v.push_back(v[len-i-1]+pow(2,n-1));

}

return v;

}

};

发表于 2017-07-01 16:34:58 回复(0)

QuestCompleted

func grayCode( n int ) []int {
    // write code here
    ans := make([]int, 1<<n)
    for i := 0; i < len(ans); i++ {
        ans[i] = i^(i>>1)
    }
    return ans
}

发表于 2021-08-15 00:31:16 回复(0)

Python

拿到心仪offer

class Solution:
    def grayCode(self , n ):
        array=[0]
        a=[]
        for i in range(1,n+1):
            a=reversed(array)
            a=list(a)
            for j in range(len(a)):
                a[j]+=2**(i-1)
            array+=a
        return array

n=0， array=[0]

n=1，array=[0,1]

n=2，array=[0,1,3,2]

先从n=0开始，n=1时，array中的1是0加上2^（i-1）得到，以此类推，n=2中的3 2是由[0,1]反转加上2^（i-1）得到

发表于 2021-05-07 22:16:30 回复(0)

C/C++

华科不平凡

这道题目可以用普通的循环来做，也可以用动态规划来做，相比起来动态规划的思路更加清晰，代码逻辑更加紧密。

当n为1时，输出0,1，n为2时，输出00,01,11,10，当n为3时，输出00,01,11,10,110,111,101,100。

规律：11,10是在1,0高位上+1得到；110,111,101,100是在10,11,01,00高位上+1得到，代码如下：

//
// Created by jt on 2020/8/25.
//
class Solution {
public:
    /**
     *
     * @param n int整型
     * @return int整型vector
     */
    vector<int> grayCode(int n) {
        // write code here
        vector<int> res(1, 0);
        for (int i = 0; i < n; ++i) {
            int topBit = 1 << i;
            for (int j = res.size() - 1; j >= 0; --j) {
                res.push_back(topBit | res[j]);
            }
        }
        return res;
    }
};

编辑于 2020-08-25 17:54:08 回复(0)

大白菜1号

vector<int> grayCode(int n) { // write code here
    int m = 0;
    vector<int> result = {0};
    while(m < n){
        for(int i = result.size() - 1;i >= 0;i--){
            result.push_back(result[i] + pow(2, m));
        }
        m++;  }
    return result;
}

经典找规律

发表于 2020-08-16 15:20:09 回复(0)

C/C++

字节内推小跟班

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        for(int i = 0; i < 1 << n; i++)
            ans.push_back(i ^ i >> 1);
        return ans;
    } 
};

发表于 2020-04-19 12:47:02 回复(0)

AustinTao

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int>res;
        res.push_back(0);
        if(n<1)return res;
        for(int i=0;i<n;i++)
        {
            int size=res.size();
            int highbit=1<<i;
            for(int j=size-1;j>=0;j--)
            {
                res.push_back(res[j]|(highbit));
            }
        }
        return res;
    }
};

很巧妙的题，难在递推规律

发表于 2020-03-15 17:00:04 回复(0)

野猪佩琪🐗

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(0);
        int head = 1;
        for(int i=1;i<=n;i++){
            for(int j=list.size()-1;j>=0;j--){
                list.add(head+list.get(j));    //把n-1位的格雷码从后往前把1插到第一位，并加到list
                                               //加上原来的n-1位的格雷码就成为了n位的格雷码
            }
            head <<= 1;
        }
        return list;
    }
}
//参考了leetcode的第一个题解

发表于 2020-02-18 16:46:20 回复(0)

ponmmains

import java.util.*;

public class Solution {

public ArrayList<Integer> grayCode(int n) {
Map<Integer, Boolean> map = new HashMap<>();
ArrayList<Integer> list = new ArrayList<>();

if (n == 0){
list.add(0);
return list;
}

int[] nums = new int[n];
Arrays.fill(nums, 0);
int val = 0;
boolean flag = false;
while (true) {
map.put(val, true);
list.add(val);
flag = false;
for (int i = n - 1; i >= 0; i--) {
nums[i] = (nums[i] + 1) % 2;
val = 0;
for (int j = 0; j < n; j++)
val = val * 2 + nums[j];
if (map.containsKey(val))
nums[i] = (nums[i] + 1) % 2;
else {
flag = true;
break;
}
}
if (!flag)
break;
}

return list;
}
}

发表于 2019-11-24 16:49:02 回复(0)