教育改变生活

标题: leetcode真题-格雷码 [打印本页]

作者: 一秉 时间: 2020-6-9 22:20
标题: leetcode真题-格雷码
题目：格雷码是一个二进制数字系统，其中两个连续的值仅相差一位。
给定一个代表代码中位数总数的非负整数n，则打印格雷码序列。格雷码序列必须以0开头。
示例：
输入：  2
输出： [0,1,3,2]
说明：
00 - 0
01 - 1
11 - 3
10 - 2
对于给定的  n，格雷码序列可能没有唯一定义。
例如，[0,2,3,1]也是有效的格雷码序列。
解析：
假设我们找到了GrayCode（n-1）的解决方案，即一个包含2 ^（n-1）个元素的向量（向量中的元素都是字符串，如“ 00010”），我们需要做的是追加每个元素一个“ 0”，然后复制向量，将其反转，然后将我们刚刚附加的所有“ 0”替换为“ 1”。最后，我们合并这两个列表，仅此而已。
代码：
class Solution {
public List<Integer> grayCode(int n) {
      List<Integer> res = new ArrayList<Integer>();
      res.add(0);

      int offset = 1;
      for(int i = 1 ; i <= n ; i ++) {
         for (int j = res.size() - 1; j >= 0 ; j --) {
            res.add(res.get(j) + offset);
         }
         offset <<= 1;
      }

      return res;
}
}

欢迎光临教育改变生活 (http://bbs.goldoar.com/)