[leetcode] Amazon 面试题：格雷编码

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个二进制的差异。 给定一个非负整数 n，表示该代码中所有二进制的总数，请找出其格雷编码顺序。一个格雷编码顺序必须以 0 开始，并覆盖所有的 2n 个整数。

• 对于给定的 n，其格雷编码顺序并不唯一。
• 当 n = 2 时，根据上面的定义，[0,1,3,2] 和 [0,2,3,1] 都是有效的格雷编码顺序。

点这里在线做题

样例 1:

输入: 1 输出: [0, 1] 

样例 2:

输入: 2 输出: [0, 1, 3, 2] 解释: 0 - 00 1 - 01 3 - 11 2 - 10 

最简单的做法是利用位运算. 在《计算机组成与设计》一书上有介绍. 一个数字对应的格雷编码的计算方式是:

• 将其二进制第一位(从高位数)与 0 异或, 得到的结果为格雷码的第一位
• 之后依次将原数的第 i 位与生成的格雷码第 i-1 位做异或运算, 即可得到格雷码的第 i 位.

public class Solution { public ArrayList<Integer> grayCode(int n) { ArrayList<Integer> result = new ArrayList<Integer>(); for (int i = 0; i < (1 << n); i++) result.add(i ^ (i >> 1)); return result; } } ////////// 递归版本 public class Solution { public ArrayList<Integer> grayCode(int n) { ArrayList<Integer> result = new ArrayList<Integer>(); if (n <= 1) { for (int i = 0; i <= n; i++){ result.add(i); } return result; } result = grayCode(n - 1); ArrayList<Integer> r1 = reverse(result); int x = 1 << (n-1); for (int i = 0; i < r1.size(); i++) { r1.set(i, r1.get(i) + x); } result.addAll(r1); return result; } public ArrayList<Integer> reverse(ArrayList<Integer> r) { ArrayList<Integer> rev = new ArrayList<Integer>(); for (int i = r.size() - 1; i >= 0; i--) { rev.add(r.get(i)); } return rev; } } 

点这里查看更多题解