Leetcode 每日一题:86. 格雷编码

自己尝试

对于怎么操作比特,没思路。即使自己知道是考察 位运算符 ,但由于之前没有做过类似的题目,不知道如何下手。。。

别人的算法

格雷码定义公式

最离谱的。。。三行搞定。我猜应该是我没有格雷编码相关的知识所致。。。

class Solution {
    public List<Integer> grayCode(int n) {
        /**
        关键是搞清楚格雷编码的生成过程, G(i) = i ^ (i/2);
        如 n = 3: 
        G(0) = 000, 
        G(1) = 1 ^ 0 = 001 ^ 000 = 001
        G(2) = 2 ^ 1 = 010 ^ 001 = 011 
        G(3) = 3 ^ 1 = 011 ^ 001 = 010
        G(4) = 4 ^ 2 = 100 ^ 010 = 110
        G(5) = 5 ^ 2 = 101 ^ 010 = 111
        G(6) = 6 ^ 3 = 110 ^ 011 = 101
        G(7) = 7 ^ 3 = 111 ^ 011 = 100
        **/
        List<Integer> ret = new ArrayList<>();
        for(int i = 0; i < 1<<n; ++i)
            ret.add(i ^ i>>1);
        return ret;
    }
}

对称生成法

题解题解 2

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<>();

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

        return ans;
    }
}

但题解 1 并没有解释为什么要逆序构造???

题解只是说明了 n + 1 的格雷编码可以有 n 长度的格雷编码构成

看了题解 2 ,明白了为什么需要逆序对称构造了。

由于相邻的两个数,只能有一位的差异。所以在构造 2^n^ + 1 位时,必须从 2^n^ 构造,这样才满足要求。

这时候,当构造 2^n^ + 2 位时,由于对称的特性,需要从 2^n^ - 1 位构造。这样的话,2^n^ - 1, 2^n^ , 2^n^ + 1, 2^n^ + 2 这 4 个位就都满足相互间两两都只有一个位的差异

这就是逆序对称构造的原因!!!

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3011 引用 • 8158 回帖 • 549 关注
  • 算法
    375 引用 • 252 回帖 • 20 关注
  • 每日一题
    8 引用 • 4 回帖

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...