leetcode 89. Gray Code 按照index递归DFS解决 + Grey码生成公式 + 位运算直接计算

清疚 2022-06-08 01:27 77阅读 0赞

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return \[0,1,3,2\]. Its gray code sequence is:

00 - 0  
01 - 1  
11 - 3  
10 - 2  
Note:  
For a given n, a gray code sequence is not uniquely defined.

For example, \[0,2,3,1\] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

这个是学习信号与处理的时候讲到的格雷码，就是相邻的元素的数量差异最小。这个直接按照镜子的映射关系来设置就可以了。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    /*
     * 格雷码，就是按照index递归解决
     * */
    public class Solution 
    {
        List<Integer> res=new ArrayList<>();
        public List<Integer> grayCode(int n) 
        {
            if(n<=0)
            {
                res.add(0);
                return res;
            }
    
            List<List<Integer>> flag=new ArrayList<List<Integer>>();
            ByReci(0,n,flag);
            return res;
        }
        private void ByReci(int index, int n,List<List<Integer>> flag) 
        {
            if(index==n)
            {
                for(int i=0;i<flag.size();i++)
                {
                    List<Integer> one=flag.get(i);
                    int sum=0;
                    for(int j=0;j<one.size();j++)
                        sum+=one.get(j)*Math.pow(2, j);
    
                    res.add(sum);
                }
            }else
            {
                if(index==0)
                {
                    List<Integer> one=new ArrayList<>();
                    one.add(0);
                    List<Integer> two=new ArrayList<>();
                    two.add(1);
                    flag.add(one);
                    flag.add(two);
                    ByReci(index+1,n, flag);
                }else
                {
                    for(int i=0;i<flag.size();i++)
                        flag.get(i).add(0);
                    for(int i=flag.size()-1;i>=0;i--)
                    {
                        List<Integer> one=new ArrayList<>(flag.get(i));             
                        one.remove(one.size()-1);
                        one.add(1);
                        flag.add(one);
                    }
                    ByReci(index+1, n, flag);               
                }
            }
        }
    }

下面是C++的做法，我是网上看到的做法，使用公式和位运算来计算完成的，很棒的做法，可以参考这个链接[LeetCode — 89. Gray Code][LeetCode _ 89. Gray Code]

代码如下：

#include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    /*
        参考这个链接：http://blog.csdn.net/makuiyu/article/details/44926463
        此题要求生成n位格雷码，共计有2^n个。
        根据上面公式G(N) = B(n) XOR (B(n)/2)，即可逐步生成所有格雷码。
    */
    class Solution 
    {
    public:
        vector<int> grayCode(int n) 
        {
            vector<int> res;
            int size = 1 << n;
            for (int i = 0; i < size; i++)
                res.push_back(i^(i>>1));
            return res;
        }
    };

[LeetCode _ 89. Gray Code]: http://blog.csdn.net/makuiyu/article/details/44926463