V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hakunamatata11
V2EX  ›  推广

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

  •  
  •   hakunamatata11 · 2020-08-12 18:38:00 +08:00 · 986 次点击
    这是一个创建于 1324 天前的主题,其中的信息可能已经有所发展或是发生改变。

    格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个二进制的差异。 给定一个非负整数 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;
        }
    }
    
    

    点这里查看更多题解

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5344 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 08:04 · PVG 16:04 · LAX 01:04 · JFK 04:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.