1ms Java Solution with explaination


  • 7
    E
    public class Solution {
    //analyze the pattern
    //n=0  -> 0
    //n=1  -> 0, 1
    //n=2  -> (00,  01),  (10,  11)
    //n=3  -> (000, 001, 010, 011), (111, 110, 101, 100)
    
    //so the pattern is when n=n  -> add 0 in front of all the result of (n-1)'s binary value (This is just same as all the result of (n-1)
    //                               and add 1 in front of all the result of(n-1)'s binary value (This need to calculate.)
    
    
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList();
        result.add(0);
        
        for(int i=1; i<=n; i++){
            int front=1;
            //Create the correct value for binary format (10...0) which the value has i digi
            //so shift 1 to right (i-1) times
            for(int j=1; j<i; j++){
                front = front<<1;
            }
            
            //add the new generated value to the result list
            //the new generated value is the last result add front value
            int size=result.size();
            //we want to loop through the (n-1) result from end to start. This is just because want to make the test case match the Leetcode answer. You can use other way loop through the (n-1) result.
            for(int k=size-1; k>=0; k--){
                result.add(result.get(k)+front);
            }
        }
        
        return result;
    }
    

    }


  • 0
    R

    Your pattern analysis is wrong, n=2 -> 00, 01, 11, 10. n=3 -> 000, 001, 011, 010, 110, 111, 101, 100


  • 0
    E

    Thanks, Ryanmax. You are right. It was the typo, and I just corrected it.


  • 2
    T

    I noticed 3 things while reading your code:


    Tip: size == front in every iteration, because you double the elements in result each time and i advances by one which results in one more front << 1 == front * 2.


    so shift 1 to right (i-1) times

    VS the operator shifiting left

    front<<1;
    

    and also there's a direct operation for it, no need to loop

    int front = 1 << (i - 1);
    

    This is just because want to make the test case match the Leetcode answer. You can use other way loop through the (n-1) result.

    This is simply not true. If you don't reverse the walk you simply ignore the reflective property of the Grey code, notice how after the kth line the last k-1 bits are reflections of the elements before.

    0000 ----\
    ----     |
    0001 ---\|
    ----    ||
    0011 --\||
    0010 -\|||
    ----  |||| k = 3, reflection above and below
    0110 -/|||
    0111 --/||
    0101 ---/|
    0100 ----/
    

    This relfectivity makes sure that only one bit is flipped, consider what happens if we don't do a reverse walk when adding the prefix (front == 0b100):

    000, 001, 011, 010, !, 100, 101, 111, 110
    

    at ! the numbers differ in two bits: counting from right startin from 0 you need to flip bit 1 and bit 2 to go from 010 to 100. Moving a bit is not allowed here. In other words XOR of two consecutive gray code elements must be a power of 2.


  • 0
    S

    Some simplification:

    public class Solution {
        public List<Integer> grayCode(int n) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            list.add(0);
            if(n == 0) return list;
            list.add(1);
            if(n == 1) return list;
            int reflect_adder = 1;
            for(int i = 1; i < n; ++i){
                reflect_adder = reflect_adder << 1;
                for(int j = reflect_adder - 1; j >= 0; j--)
                    list.add(list.get(j) + reflect_adder);
            }
            return list;
        }
    }

Log in to reply
 

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