我是靠谱客的博主 潇洒海燕,这篇文章主要介绍轻松破解Amazon面试题:格雷编码,现在分享给大家,希望可以做个参考。

格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个二进制的差异。

给定一个非负整数 n ,表示该代码中所有二进制的总数,请找出其格雷编码顺序。一个格雷编码顺序必须以 0 开始,并覆盖所有的 2n 个整数。

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

→在线做题地址

样例 1:

复制代码
1
2
3
输入: 1 输出: [0, 1]

样例 2:

复制代码
1
2
3
4
5
6
7
8
输入: 2 输出: [0, 1, 3, 2] 解释: 0 - 00 1 - 01 3 - 11 2 - 10

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

  • 将其二进制第一位(从高位数)与0异或, 得到的结果为格雷码的第一位
  • 之后依次将原数的第i位与生成的格雷码第i-1位做异或运算, 即可得到格雷码的第i位.
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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; } }

点这里还可以查看更多题解

最后

以上就是潇洒海燕最近收集整理的关于轻松破解Amazon面试题:格雷编码的全部内容,更多相关轻松破解Amazon面试题内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(59)

评论列表共有 0 条评论

立即
投稿
返回
顶部