JAVA-----------Easy Version To Understand!!!!!!


  • 15
    H
    public static List<Integer> grayCode(int n) {
    	if (n < 0)
    		return new ArrayList<Integer>();
    	if (n == 0) {
    		List<Integer> list = new ArrayList<Integer>();
    		list.add(0);
    		return list;
    	}
    	List<Integer> tmp = grayCode(n - 1);
    	List<Integer> result = new ArrayList<Integer>(tmp);
    	int addNumber = 1 << (n - 1);
    	for (int i = tmp.size() - 1; i >= 0; i--) {
    		result.add(addNumber + tmp.get(i));
    	}
    
    	return result;
    }

  • 3
    H

    Not so easy to understand...Can you explain it?


  • 0
    C

    Look at the examples, you will find out they are symmetric if the first bit is cut off .

    n = 1

    0

    1

    n=2

    0 0

    0 1

    1 1

    1 0

    n=3

    0 0 0

    0 0 1

    0 1 1

    0 1 0

    1 1 0

    1 1 1

    1 0 1

    1 0 0


  • 8
    L

    I try to explain a little bit...

    n = 0: 0
    n = 1: 0, 1
    n = 2: 00, 01, 11, 10  (0, 1, 3, 2)
    n = 3: 000, 001, 011, 010, 110, 111, 101, 100 (0, 1, 3, 2, 6, 7, 5, 4)
    

    Take n=3 as the example, the first four sequences are exactly same as n=2 sequences.
    The second four sequences are derived of the following steps:

    1. reverse n=3 first half sequence: 010, 011, 001, 000
    2. Add 2^2 to each element of reversed n=2 sequence

    Now we can extend to n=i situation.
    The first half of n=i is the same sequence as n=i-1
    The second half of n=i is add 2^(i-1) to the reversed sequence of first half.

    Reference: http://bangbingsyb.blogspot.com/2014/11/leetcode-gray-code.html


  • 0
    L
    This post is deleted!

  • 0
    D

    C++ Equivalent code

    class Solution {
        vector<int> result;
    public:
        vector<int> grayCode(int n) {
            vector<int> result;
            if(n<0) return result;
            if(n==0) {result.push_back(0); return result;}
            result = grayCode(n-1);
            //cout<<result.size();
            int x=1<<n-1;
            for(int i=result.size()-1;i>=0;i--) {
                result.push_back(x+result[i]);
            }
            return result;
        }
    };
    

  • 3

    I come up with a similar solution, and it's more concise. Please check it out.

    /*
    n = 0: 0
    n = 1: 0 | 1
    n = 2: 00, 01 | 11, 10
    n = 3: 000, 001, 011, 010 | 110, 111, 101, 100
    f(n) = f(n - 1) | 2 ^ (n - 1) + f(n - 1)
    */
    public class Solution {
        public List<Integer> grayCode(int n) {
            List<Integer> res = new ArrayList<>();
            res.add(0);
            
            for(int i = 1; i <= n; i++) {
                int size = res.size(), base = 1 << (i - 1);
                for(int j = size - 1; j >= 0; j--) {
                    res.add(base + res.get(j));
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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