Ac solution code


  • 0

    Solution1. Simplified - Special thanks to @yuyibestman

    This is an iterative solution: Add prefix '1' to the previous sequence (from the last one). Because the the previous sequence should differ 1 bit between the successive two numbers, so if we add prefix '1' to them, they should still differ 1 bit between the successive two numbers.

         There're two parts for sequence(i+1):
    	 n = 2: 00(1),   01(2),   11(3),    10(4) 
    =>   n = 3: 000(1),  011(2)   011(3)    010(4) - PART1
         n = 3: 110(4),  111(3)   101(2)    100(1) - PART2
    	 PART1: Same as sequence(i);
    	 PART2: Add prefix '1' to the sequence(i) (from the last one).
    

    JAVA Code:

    public List<Integer> grayCode(int n) {
       List<Integer>res = new LinkedList<Integer>();
       res.add(0);
       for (int i = 0; i < n; i++) {
    	   int size = res.size();
    	   for (int j = size - 1; j >= 0; j--) {// Add prefix '1' to the previous sequence (from the last one)
    		   res.add(res.get(j) | (1 << i));
    	   }
       }
       return res;
    }
    

    Solution2. DFS

    The basic idea is using DFS to change 1 bit of the last visited number each time. It's a bit more complex than solution1, but it can output all possible sequences if we want. So, still worth a shot ;)
    Changing 1 bit part is messed up, didn't figure out how to change 1 bit concisely, any advice would be appreciated!

    JAVA Code:

    public List<Integer> grayCode(int n) {
    	List<Integer> res = new LinkedList<Integer>();    	
    	res.add(0);
    	DFS(n, res);
    	return res;
    }    
    boolean DFS(int n, List<Integer> res) {
    	if (res.size() == 1 << n) return true;    	
    	int last = res.get(res.size() - 1);
    	for (int i = 0; i < n; i++) {    		
    		int cur = 0;
    		// change 1 bit
    		int bitI = (last >> i) & 1;    		
    		if (bitI == 1) cur = last - (1 << i);
    		else cur = last + (1 << i);    	
    		
    		if (!res.contains(cur)) {
    			res.add(cur);
    			if (DFS(n, res)) return true;
    			res.remove(res.size() - 1);
    		} 
    	}
    	return false;
    }
    

Log in to reply
 

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