【题目】
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integernrepresenting the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, givenn= 2, return[0,1,3,2]
. Its
gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a givenn, a gray code sequence is not uniquely defined.
For example,[0,2,3,1]
is also a valid gray code sequence according
to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
【题意】
格雷码是一个二进制数字集合,相邻两数间只有一个位元改变。
给定一个非负整数n代表的比特位的总数,打印格雷码序列。格雷码序列必须从0开始。
例如,给定n=2,返回[0,1,3,2]。它的格雷码序列为:
00 - 0
01 - 1
11 - 3
10 - 2
注意:
对于给定的n,格雷码序列不是唯一地。
例如,按上述定义[0,2,3,1]也是一个有效的格雷码序列。
现在,判定系统只能够判断基于格雷码序列的一个实例。我们对此深感抱歉。
【分析】
思路1:
格雷码 (Gray Code) 的定义请参考 wikipedia http://en.wikipedia.org/wiki/Gray_code。
-
自然二进制码转换为格雷码:
保留自然二进制码的最高位作为格雷码的最高位,格雷码次高位为二进制码的高位与次高位异或,其余各位与次高位的求法类似。
例如,将自然二进制码 1001,转换为格雷码的过程是:
保留最高位;然后将第 1 位的 1 和第 2 位的 0 异或,得到 1,作为格雷码的第 2 位;将第 2 位的 0 和第 3 位的 0 异或,得到 0,
作为格雷码的第 3 位;将第 3 位的 0 和第 4 位的 1 异或,得到 1,作为格雷码的第 4 位,最终,格雷码为 1101。
- 格雷码转换为自然二进制码:
保留格雷码的最高位作为自然二进制码的最高位,次高位为自然二进制高位与格雷码次高位异或,其余各位与次高位的求法类似。
例如,将格雷码 1000 转换为自然二进制码的过程是:
保留最高位 1,作为自然二进制码的最高位;然后将自然二进制码的第 1 位 1 和格雷码的第 2 位 0 异或,得到1,
作为自然二进制码的第 2 位;将自然二进制码的第 2 位 1 和格雷码的第 3 位 0 异或,得到 1,作为自然二进制码的第 3 位;
将自然二进制码的第 3 位 1 和格雷码的第 4 位 0 异或,得到 1,作为自然二进制码的第 4 位,最终,自然二进制码为 1111。
-
格雷码有数学公式,整数 n 的格雷码是
这题要求生成 n 比特的所有格雷码。最简单的方法,利用数学公式,对从 0~ 2^n - 1的所有整数,转化为格雷码。
思路2:
n 比特的格雷码,可以递归地从 n - 1 比特的格雷码生成。
n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到,如右图所示一般。
红色的最高位加一即保持不变。
蓝色的最高位加一;n = 1时原格雷码十进制加1 ; n = 2时 加2 ; n = 3时 加 4 ;n= 4时 加 8............
【代码1】
/*********************************
* 日期:2014-01-23
* 作者:SJF0115
* 题号: Gray Code
* 来源:http://oj.leetcode.com/problems/gray-code/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
//数学公式,时间复杂度 O(2^n),空间复杂度 O(1)
vector<int> grayCode(int n) {
int count = 1 << n;
vector<int> code;
for(int i = 0;i < count;i++){
code.push_back(binaryToGrayCode(i));
}
return code;
}
private:
int binaryToGrayCode(int n){
return n ^ (n >> 1);
}
};
int main() {
Solution solution;
vector<int> result;
result = solution.grayCode(3);
int n = result.size();
for(int i = 0;i < n;i++){
printf("%d ",result[i]);
}
printf("\n");
return 0;
}
【代码2】
/*********************************
* 日期:2014-01-23
* 作者:SJF0115
* 题号: Gray Code
* 来源:http://oj.leetcode.com/problems/gray-code/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
class Solution {
public:
//镜射排列
vector<int> grayCode(int n) {
int i,j,count,c;
vector<int> code;
//初始为0位
code.push_back(0);
for(i = 0;i < n;i++){
count = code.size();
c = 1 << i;
//添加镜面反射的那一部分(最高位加1)
//要反着遍历才能对称
for(j = count - 1;j >= 0;j--){
code.push_back(code[j] + c);
}
}
return code;
}
};
int main() {
Solution solution;
vector<int> result;
result = solution.grayCode(3);
int n = result.size();
for(int i = 0;i < n;i++){
printf("%d ",result[i]);
}
printf("\n");
return 0;
}
格雷码转二进制数
二进制码第n位 = 二进制码第(n+1)位+格雷码第n位。因为二进制码和格雷码皆有相同位数,所以二进制码可从最高位的左边位元取0,以进行计算。(注:遇到1+1时结果视为0)
例如: 格雷码0111,为4位数,所以其所转为之二进制码也必为4位数,因此可取转成之二进制码第五位为0,即0 b3 b2 b1 b0。
0+0=0,所以b3=0
0+1=1,所以b2=1
1+1取0,所以b1=0
0+1取1,所以b0=1
因此所转换为之二进制码为0101
分享到:
相关推荐
颜色分类leetcode 格雷码结构光重建 使用投影仪和相机重建 3D 场景 这个 repo 使用投影仪和相机来扫描场景并创建 3D 模型。 为了实现这一点,结构光图案被投射到场景上。 这是用相机捕获以确定密集对应关系。 该存储...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
vs code LeetCode 插件
LeetCode 解决VS Code中的LeetCode问题 英文文件| 文件 :exclamation_mark: 注意 :exclamation_mark: -登录LeetCode端点的解决方法注意:如果使用的是leetcode-cn.com ,则可以忽略此部分。 最近,我们发现。 此问题...
leetcode卡 Code #纯属leetcode打卡
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
leetcode-codelist 食用指南(持续更新中...) 文件名说明:leetcode-题号-题目类型 目前更新重点-每日一题 tips:闲暇时间刷刷题,面试之前不用慌。 常见思路整理 前缀和 327 区间和的个数 差分 动态规划 845 最长...
LeetCode刷题插件,可在VS Code中快速刷题,比较适合第一轮刷题,快速熟悉算法解题策略
leetcode题库 常见数据结构和算法,面试题的实现。主要采用C语言实现 leetcode leetcode是题目解法,按照题目的编号进行命名,文件开头注明了题目名称和链接。 algorthms algorthms是一些算法和数据结构的练习 ...
leetcode中文版
Code 挑战 这是我提交给 Lambda School CS Unit 2 构建周的已接受 Leet 代码挑战的集合。 如果您想自己尝试,这些链接将带您进入代码挑战。 要查看我接受的答案,只需转到与代码挑战名称匹配的文件即可。 第一天MVP ...
leetcode下载 前言 模仿 leetcode 的一个在线代码编辑器,可以在线运行查看结果。 主要功能实现 通过把字符串代码保存在 .java 文件中,然后通过 JavaCompiler 去动态编译生成 .class 文件,然后通过自定义类加载器 ...
leetcode 分类 Code-interview 基于Cracking code Interview这本书和leetcode分类总结
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
leetcode题库 my-leetcode-code leetcode代码管理 此代码列表为本人在leetcode目前已解决题库代码 代码环境为python3
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
leetcode刷题之动态规划
100个leetCode详细解答
上班时间刷leetcode LeetCode 记录自己的刷题思路,js代码不在维护,以后以py代码为主。 规范如下: 文件名格式[题号][题目名字],文件内容:题目描述、关键思路、解题代码、tag、复杂度 刷题相关思考 刷题开始于...