3ms, beat 100%, can be improved into no extra space


  • 0
    Z
    class Solution {
    public:
        vector<int> grayCode(int n) {
            vector<int> v;
            v.push_back(0);
            if(n<=0) return v;
            int size = pow(2,n);
            int ar[size];
            ar[0] = 0;
            ar[1] = 1;
            grayCode(ar,1,n);
            for(int i=1;i<size;++i)
                v.push_back(ar[i]);
            return v;
        }
    private:
        void grayCode(int ar[],int cur,int n)
        {
            if(cur < n)
            {
                int num = pow(2,cur);
                int bit = 1 << cur;
                for(int i=0;i<num;++i)
                    ar[num+i] = bit | ar[num-i-1];
                grayCode(ar,cur+1,n);
            }
        }
    };

  • 0
    Z

    @zhangwbnn

    class Solution {
    public:
        vector<int> grayCode(int n) {
            vector<int> v;
            if(n<0) return v;
            v.push_back(0);
            if(n==0) return v;
            v.push_back(1);
            grayCode(v,1,n);
            return v;
        }
    private:
        void grayCode(vector<int>& v,int cur,int n)
        {
            if(cur < n)
            {
                int num = v.size();
                int bit = 1 << cur;
                for(int i=0;i<num;++i)
                {
                    int tmp =  bit | v[num-i-1];
                    v.push_back(tmp);
                }
                grayCode(v,cur+1,n);
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.