在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。
给定一个整数n，请返回n位的格雷码，顺序为从0开始。
测试样例：
1
返回：["0","1"]
[编程题]生成格雷码
classGrayCode {public:vector<string> getGray(intn) {// write code herevector<string> result;// intl=pow(2,n);if(n==0)returnresult;if(n==1){result.push_back("0");result.push_back("1");returnresult;}result=getGray(n-1);ints=result.size();for(inti=s-1;i>-1;i--){result.push_back("1"+result[i]);result[i]="0"+result[i];}returnresult;}};对称关系，最后只一次遍历一半，然后不必依赖计算出的长度，直接ｐｕｓｈ。
编辑于 2016-04-02 23:33:19
回复(0)
更多回答
classGrayCode {
public:
vector<string> getGray(intn) {
if(n == 1){
vector<string> results;
results.push_back("0");
results.push_back("1");
returnresults;
}
else{
vector<string> last = getGray(n - 1);
intlastsize = last.size();
intcurrentsize = 2*lastsize;
vector<string> current(currentsize);
for(inti = 0; i<lastsize; i++){
current[i] = '0'+ last[i];
current[currentsize - 1- i] = '1'+ last[i];
}
returncurrent;
}
}
};
发表于 2015-10-29 16:47:42
回复(0)
要去发现格雷码的规律，我是借鉴了网上的一些经验写的，也是醉了，发现自己对递归这一块还不熟悉
importjava.util.*;
publicclassGrayCode {
publicString[] getGray(intn) {
//总共需要的位数
String grayCode[]=newString[(int)Math.pow(2,n)];
if(n==1){
//如果是1挺好办的
grayCode[0]="0";
grayCode[1]="1";
returngrayCode;
}
//递归前n-1的格雷码
String last[]=getGray(n-1);
//格雷码计算方式，前一次格雷码分两部分
//前半部分的二进制码前加 0
//后半部分的二进制码前加1
for(int i=0;i<last.length;i++){
grayCode[i]="0"+last[i];
grayCode[grayCode.length-i-1]="1"+last[i];
}
returngrayCode;
}
}
编辑于 2015-10-21 16:23:02
回复(0)
public String[] getGray(int n) {
// write code here
if (n < 1) {
System.out.println("格雷码长度必须大于等于1");
return null;
}
int count = 1 << n;
String[] strArr = new String[count];
if (n == 1) {
strArr[0] = "0";
strArr[1] = "1";
return strArr;
} else {
String[] strArr1 = getGray(n - 1);
for (int i = 0; i < strArr1.length; i += 1) {
strArr[i] = "0" + strArr1[i];
}
for (int i = 0; i < strArr1.length; i += 1) {
strArr[strArr.length - i-1] = "1" + strArr1[i];
}
return strArr;
}
}
发表于 2016-03-27 15:29:41
回复(0)
今天才弄懂什么是格雷码，题目给的n代表位数而不是一个整数，格雷码的n个位数意味着有2的n次方个二进制数，每个二进制数为n位，每个二进制数相比，都只有一位二进制码不相同；比如n=1,{0，1}；n=2,{00,01,11,10};n=3,{000,001,011,010,110,111,101,100}
void gray(vector<string>& v,int bit,int n)
{
if(bit==n)
return;
vector<string> temp;
for(int i=0;i<v.size();i++)
temp.push_back("0"+v[i]);
for(int i=v.size()-1;i>=0;i--)
temp.push_back("1"+v[i]);
v.swap(temp);
gray(v,bit+1,n);
}
vector<string> getGray(int n) {
// write code here
vector<string> v;
v.push_back("0");
v.push_back("1");
if(n==1)
return v;
gray(v,1,n);
return v;
}
发表于 2015-10-11 13:55:21
回复(0)
classGrayCode {
public:
vector<string>
getGray(intn) {
// write code
here
vector<string> str;
if(n==1)
{
str.push_back("0");
//str.push_back(",");
str.push_back("1");
returnstr;
}
else
{
str =
getGray(n-1);
vector<string> str1;
str1 = str;
for(inti =
str1.size()-1; i >=0; i--)
{
str.push_back(str1[i]);
}
for(inti =0; i
< str.size()/2; i++)
{
str[i].insert(0,"0");
}
for(inti =
str.size()/2; i < str.size(); i++)
{
str[i].insert(0,"1");
}
}
returnstr;
}
};
发表于 2016-04-28 22:34:30
回复(0)
# -*- coding:utf-8-*-from sys importexitclassGrayCode:def getGray(self, n):# write code heredef _getGray(x):count=2**xans=[]ifx<1:exit(-1)elif x==1:ans.append("0")ans.append("1")returnanselse:temp=_getGray(x-1)j=len(temp)fori in range(j):ans.append("0"+temp[i])whilej>0:ans.append("1"+temp[j-1])j-=1returnansreturn_getGray(n)
发表于 2016-03-30 14:10:36
回复(0)
using System.Collections.Generic;
class GrayCode
{
publicstring[] getGray(int n)
{
string[] Gray = {"0", "1"};
if(n == 1)
return Gray;
string[] LastRank = getGray(n - 1);
List<string> ThisRank = new List<string>();
for(int Index = 0; Index < LastRank.Length; Index++)
ThisRank.Add("0"+ LastRank[Index]);
for(int Index = LastRank.Length - 1; Index >= 0; Index--)
ThisRank.Add("1"+ LastRank[Index]);
return ThisRank.ToArray();
}
}
编辑于 2016-03-26 14:20:21
回复(0)
直接使用递归生成n位格雷码，每次分别在n-1位格雷码（递归生成n-1位的格雷码）的首位添加0和1得到n位格雷码，然后将首位添加1的n位格雷码反转顺序。
import java.util.*;
public class GrayCode {
public String[] getGray(int n) {
// write code here
return (String[])helper(n).toArray(new String[n]);
}
private ArrayList<String> helper(int n) {
ArrayList<String> gray = new ArrayList<>();
if(n == 1){
gray.add("0");
gray.add("1");
return gray;
}
ArrayList<String> last_gray = helper(n - 1);
// 在首位添加"0"
for(int i = 0; i < last_gray.size(); i++)
gray.add("0" + last_gray.get(i));
// 在首位添加"1"
for(int i = last_gray.size() - 1; i >= 0; i--)
gray.add("1" + last_gray.get(i));
return gray;
}
}
发表于 2021-02-08 11:08:06
回复(0)
public class gerryCode {
// 1 : 0 1
//2 : 00 01 11 10
//3 :["000","001","011","010","110","111","101","100"]
public String[] getGray(int n) {
Queue<StringBuilder> queue = new LinkedList<>();
getGray(n,queue);
String[] res = new String[queue.size()];
int i = 0;
while ( !queue.isEmpty()){
res[i] = queue.poll().toString();
i++;
}
return res;
}
public void getGray(int n, Queue<StringBuilder> queue){
// Base
if( n == 1){
queue.add(new StringBuilder().append(0));
queue.add(new StringBuilder().append(1));
return;
}
getGray(n-1,queue);
int size = queue.size();
while (size > 0){
int i;
i = size & (byte)1;
StringBuilder poll = queue.poll();
StringBuilder nextSb = new StringBuilder(poll);
poll.append(i);
nextSb.append(1-i);
queue.offer(poll);
queue.offer(nextSb);
size --;
}
}
public static void main(String[] args) {
gerryCode gerryCode = new gerryCode();
System.out.println(Arrays.toString(gerryCode.getGray(3)));
}
}
发表于 2019-10-29 09:31:00
回复(0)
参考大神的公式
package com.special.improve;
import java.util.Arrays;
import java.util.Scanner;
/**
* 腾讯01-格雷码
*
* 公式： G(n) = n XOR (n / 2)
* 还有就是公式得到是十进制形式，要转换成二进制
*
* Create by Special on 2018/3/5 19:05
*/
public class Pro043Improve1 {
/**
* 十进制转二进制，且包括前导向性0
* @param num
* @param n
* @return
*/
public static String convertToString(int num, int n){
char[] results = new char[n];
Arrays.fill(results, '0');
int index = n;
while(num != 0){
results[--index] = (num & 1) == 0 ? '0' : '1';
num >>>= 1;
}
return new String(results);
}
public static String[] getGray(int n) {
int numbers = (int) Math.pow(2, n);
String[] result = new String[numbers];
for(int i = 0; i < numbers; i++){
result[i] = convertToString(i ^ (i >> 1), n);
}
return result;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int n = input.nextInt();
String[] results = getGray(n);
for(int i = 0; i < results.length; i++){
System.out.print(results[i] + " ");
}
System.out.println();
}
}
}
发表于 2018-03-05 19:13:46
回复(0)
class GrayCode {
public:
vector<string> getGray(int n) {
vector<string> g; if(n==1){ g.push_back("0"); g.push_back("1"); return g; } vector<string> s = getGray(n-1); for(int i=0;i<s.size();i++) g.push_back("0"+s[i]); for(int i=s.size()-1;i>=0;i--) g.push_back("1"+s[i]); return g;
}
};
发表于 2017-11-09 03:38:15
回复(0)
class GrayCode {
public:
vector<string> grr;
void GR( vector<string> gr ,int n){
grr.clear();
string a ="0";
string b ="1";
string temp;
for(int i=0;i<gr.size();i++){
grr.push_back(gr[i] + a);
grr.push_back(gr[i] + b);
temp = a; a = b; b = temp;
}
if( grr.size() < pow(2,n) )
GR(grr,n);
}
vector<string> getGray(int n) {
vector<string> gr;
gr.push_back("0");
gr.push_back("1");
if(n>1){
GR(gr,n);
return grr;
}
else
return gr;
}
};
发表于 2017-07-18 18:50:06
回复(1)
//标准递归，通俗易懂
class GrayCode {
public:
vector<string> result;
int length;
vector<string> getGray(int n) {
string gray = "";
for(int i=0;i<n;i++)
gray += '0';
length = n;
gray[0] = '0';
generateGray(gray, 1, 0);
gray[0] = '1';
generateGray(gray, 1, 1);
return result;
}
void generateGray(string &gray, int l, int x)
{
if(l==length)
{
result.push_back(gray);
return;
}
else
{
if(x==0)
{
gray[l] = '0';
generateGray(gray, l+1, 0);
gray[l] = '1';
generateGray(gray, l+1, 1);
}
else
{
gray[l] = '1';
generateGray(gray, l+1, 0);
gray[l] = '0';
generateGray(gray, l+1, 1);
}
}
}
};
发表于 2017-03-29 16:46:08
回复(0)
class GrayCode {
public:
vector<string> getGray(int n) {
string ini(n);
return gray(ini,n);
}
vector<string> gray(string ini,int num){
vector<string> s;
if(num==1){
s.push_back(ini);
ini[ini.size()-1]='1';
s.push_back(ini);
return s;
}
s=gray(ini,num-1);
auto tem=s;
int m=s.size();
auto i=tem.end();
while(m--){
--i;
(*i)[(*i).size()-num]='1';
s.push_back(*i);
}
return s;
}
};
编辑于 2017-03-04 20:38:20
回复(0)
public String[] getGray(int n) {
if(n == 1) {
return new String[]{"0", "1"};
}
String[] temp = getGray(n - 1);
String[] strings = new String[temp.length * 2];
for(int i = 0,j = temp.length; i < temp.length *2; i++) {
if(i < temp.length) {
strings[i] = "0" + temp[i];
} else {
j--;
strings[i] = "1" + temp[j];
}
}
return strings;
}
发表于 2016-09-10 23:58:47
回复(0)
递归的思路就是n位gray码是由n-1位gray码生成
classGrayCode {public:vector<string> getGray(intn) {// write code hereif( n == 1){returnvector<string>{"0","1"};}vector<string> && s = getGray( n - 1);vector<string> result;result.reserve( s.size() * 2);for( inti = 0; i < s.size(); ++i )result.push_back("0"+s[i]);for( inti = s.size() - 1; i >=0; --i )result.push_back("1"+s[i]);returnresult;}};
编辑于 2016-09-08 10:08:36
回复(0)
//格雷码递归实现
public class GrayCode {
public String[] getGray(int n) {
// write code here
int m=1<<n;
String[]str=new String[m];
if(n==1){
str[0]="0";
str[1]="1";
return str;
}
String[]tem=getGray(n-1);
int j=0;
for(int i=0;i<m;i++){
if(i<m/2){//前半部分前边添加“0”
str[i]="0"+tem[j++];
}else{//后半部分添加“1”，并倒序
str[i]="1"+tem[--j];
}
}
return str;
}
}
发表于 2016-09-02 22:25:39
回复(0)
class GrayCode {
public:
vector<string> getGray(int n) {
// write code here
vector<string> vc;
vc.push_back("0");
vc.push_back("1");
int cc=1;
while(cc<n)
{
vector<string> vc_new;
for(int i =0;i<vc.size();i++)
vc_new.push_back("0"+vc[i]);
for(int i=vc.size()-1;i>=0;i--)
vc_new.push_back("1"+vc[i]);
vc = vc_new;
cc++;
}
return vc;
}
};
发表于 2016-08-18 12:06:52
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-11-11 14:48:17
-
2022-10-16 14:49:22 -
2022-10-08 21:36:19
-
2022-09-28 16:04:33 -
2022-09-23 20:38:19
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
