【LeetCode 89】格雷编码构建法和自然二进制编码转化法

梦里梦外; 2021-09-22 14:28 340阅读 0赞

# 题目： #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]

# 思考： #

*  首先，补充一下格雷码的含义：在一组数的编码中，若任意两个相邻的代码**只有一位二进制数不同**，则称这种编码为格雷码。例如，位数为2格雷码的其中一个序列：00，01，11，10，它们任意两个相邻的数值，只有一个位数不同。
 *  解题思路：如果我们书写三位的格雷码的一个序列：000，001，011，010，110，111，101，100。我们会发现一个奇怪的现象，前面四个数，跟后面四个数，第一位不同，后面刚好后四个数的顺序是前四个数的逆序。通过查阅资料，可知，这是由于格雷码是[反射二进制码][Link 1]，我们根据这一特点，利用递归的如下规则来构造：
    
     *  1位格雷码有两个，n位的格雷码有2\*n个
     *  (n+1)位格雷码中的前n个码字等于n位格雷码的码字，按顺序书写，加前缀0
     *  (n+1)位格雷码中的后n个码字等于n位格雷码的码字，按逆序书写，加前缀1
     *  n+1位格雷码的集合 = n位格雷码集合(顺序)加前缀0 + n位格雷码集合(逆序)加前缀1

# 代码: #

public List<Integer> grayCode(int n) { 
            List<Integer> list = new ArrayList<>();
            if (n == 0) { 
                list.add(0);
                return list;
            }
    
    		// 这里获得格雷码的二进制码的形式，再将二进制码转为数字
            String[] grayCode = getGrayCode(n);
            for (String s : grayCode
            ) { 
                list.add(Integer.parseInt(s, 2));
            }
            return list;
        }
    
        private String[] getGrayCode(int n) { 
            if (n == 1) { 
                return new String[]{ "0", "1"};
            }
    
            String[] temp = getGrayCode(n - 1);
            String[] result = new String[temp.length * 2];
            for (int i = 0; i < temp.length; i++) { 
         	    // n位格雷码集合(顺序)加前缀0 
                result[i] = "0" + temp[i];
                // n位格雷码集合(逆序)加前缀1
                result[result.length - i - 1] = "1" + temp[i];
            }
            return result;
        }

# 自然二进制做法： #

还有一种做法，是利用自然二进制码，直接转为格雷编码，方法为：`将自然二进制码右移一位，与原自然二进制码进行异或操作`，即可得到格雷编码。  
具体的代码：

public List<Integer> grayCode1(int n) { 
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < 1 << n; i++) { 
                result.add(i ^ i >> 1);
            }
            return result;
        }

# 自然二进制做法解析： #

关于这个规律，为什么能从自然二进制码转为格雷编码，这里按自己的理解解释一下：

*  对于自然二进制码，进行自增，有两种情况，一种是进位，一种是末位从0变成1。而格雷编码需要对应自然二进制码这两种自增情况时，都只发生一位的修改。
 *  而算法，是`将自然二进制码右移一位，与原自然二进制码进行异或操作`，对于一个n位的自然二进制数，该变化即保留了最高位不变，有n-1次异或操作，而该格雷码就是最高位加上n-1次异或操作的结果进行拼接。我们现在就需要讨论当`二进制编码自增，发生上述两种情况时，格雷编码是否能保证只发生了一位修改`。
 *  首先考虑，自然二进制码没有发生进位的情况。此时，最后一位，实际上只参与了一组异或计算，即n-1组异或操作，会有一组的值发生了变化，即符合只发生了一位的修改。（下面举例从 0010 -> 0011）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]
 *  第二种情况，即发生进位。比如进位，会导致后面m位都发生变化，即但后面m-1组的异或中，两个元素同时变，因此异或结果没有变。而第m组，只有一个参数发生变化，因此会导致异或计算结果不同。即总体发生一组值的变化，也符合发生了一位的修改。（下面举例从 0011 -> 0100）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 2]
 *  综上两种情况，可以推断该算法确实可以将自然二进制码转为格雷编码。

# 相关其他链接 #

[其他 LeetCode 题目][LeetCode]  
[LeetCode Top 100 Liked Questions 题目][LeetCode Top 100 Liked Questions]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/4fedcbd3d1834d3686b3042d784559d2.png
[Link 1]: http://www.baike.com/wiki/%E5%8F%8D%E5%B0%84%E4%BA%8C%E8%BF%9B%E5%88%B6%E7%A0%81
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]: /images/20210920/144e50c4fa0f4166a326b75970a98d9a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 2]: /images/20210920/0e9646346f894a6096e3432b59fef554.png
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html
[LeetCode Top 100 Liked Questions]: https://blog.csdn.net/applying/category_9466044.html