Java solution use a stack, easy to figure out, simple and interesting


  • 4
    S
    0		0
    1		1
    
    00  		0
    01		1		+1
    11		3		--------
    10		2		-1
    
    000		0
    001		1		+1
    011		3		+2
    010		2		-1	
    110		6		-----------
    111		7		+1			
    101		5		-2
    100		4		-1
    
    
    0000		0
    0001		1		+1
    0011		3		+2
    0010		2		-1
    0110		6		+4
    0111		7		+1
    0101		5		-2
    0100		4		-1
    1100		12		-----------
    1101		13		+1
    1111		15		+2	
    1110		14		-1
    1010		10		-4
    1011		11		+1
    1001		9		-2
    1000		8		-1
    

    From the above example, I believe you will find out that why use a stack here, all the post half is the pre half plus the Math.pow(2, i) in the symmetric form!!!

    public class Solution {
        public List<Integer> grayCode(int n) {
            List<Integer> list = new LinkedList<Integer>();
            Stack<Integer> stack = new Stack<Integer>();
            list.add(0);
            int i = 0;
            while(i < n) {
                int len = list.size();
                int inc = (int)(Math.pow(2, i));
                for(int j=0; j<len; j++) {
                    stack.push(list.get(j));
                }
                while(!stack.isEmpty()) {
                    list.add(stack.pop() + inc);
                }
                i++;
            }
            return list;
        }
    }

  • 0
    S

    Math.pow(2, i) should use 1 << i to replace, my mistake


Log in to reply
 

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