Simple 2ms java solution


  • 4
    B
    public class Solution {
        public List<Integer> grayCode(int n) {
            if(n == 0) return Arrays.asList(0);
            List<Integer> prev = grayCode(n-1);
            List<Integer> next = new ArrayList<Integer>(prev);
            int pow = 1 << (n-1);
            for(int i=prev.size()-1; i >= 0; i--){
                next.add(prev.get(i) | pow);
            }
            return next;
        }
    }

  • 2
    T

    I did a similar thing, just non-recursively (1ms):

    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        result.add(0);
        for (int prefix = 0b1; Integer.numberOfTrailingZeros(prefix) < n; prefix <<= 1) {
            for (int i = result.size() - 1; 0 <= i; --i) { // tip: result.size() == prefix
                result.add(prefix | result.get(i));
            }
        }
        return result;
    }
    

    (prev and next are both stored in result. Even though we're adding elements to the end of the same list we're just walking backwards anyway. It doesn't matter if the collection changes under us, because the numbers we're interested in won't change.


Log in to reply
 

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