Gray Code（格雷码）】

【LeetCode-面试算法经典-Java实现】【089-Gray Code（格雷码）】

分类：LeetCode

【089-Gray Code（格雷码）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题

　　The gray code is a binary numeral system where two successive values differ in only one bit. 　　Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. 　　For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 – 001 – 111 – 310 – 2

　　Note: 　　For a given n, 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，输出长度为n的格雷码表。

解题思路

　　递归生成码表　　这种方法基于格雷码是反射码的事实，利用递归的如下规则来构造：　　1位格雷码有两个码字　　(n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0 　　(n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1

代码实现

算法实现类

import java.util.LinkedList;import java.util.List;public class Solution {public List<Integer> grayCode(int n) {List<Integer> result = new LinkedList<>();if (n >= 0) {// 格雷码的前半部分result.add(0);// 格雷码最高位的值（非0时）int t = 1;// 每一次外循环求出的是位数i+1位的格雷码表，其相当于长度为i+1位的格雷码表的前半部分for (int i = 0; i < n; i++) {// 求出的长度为i+1位格雷码表的后半部分，前半部分由长度为i位的格雷码表给出for (int j = result.size() – 1; j >= 0; j–) {result.add(result.get(j) ^ t);}// 最高位右移t <<= 1;}}return result;}}评测结果

　　点击图片，鼠标不释放，，拖动一段位置，释放后在新的窗口中查看完整图片。

特别说明欢迎转载，转载请注明出处【】

上一篇【LeetCode-面试算法经典-Java实现】【088-Merge Sorted Array（合并排序数组）】

顶2踩0

婚姻犹如一艘雕刻的船，看你怎样去欣赏它，又怎样驾驭它。

相关文章：

你感兴趣的文章：

标签云：