Java Solution with Recursive


  • 2
    B
    public class Solution {
        public List<Integer> grayCode(int n) {
            List<Integer> list = new ArrayList<Integer>();
            if (n==0) {
                list.add(0);
            } else {
                grayCode(n, 0, list);
            }
            return list;
        }
        public void grayCode(int n, int val, List<Integer> list) {
            int flag = Integer.bitCount(val)%2;
            if (n > 1) {
                grayCode(n-1, val<<1|(flag&1), list);
                grayCode(n-1, val<<1|(flag^1), list);
            } else {
                list.add(val<<1|(flag&1));
                list.add(val<<1|(flag^1));
            }
        }
    }

  • 2
    C

    Good solution. Bit manipulation may not be necessary for this problem.

    public class Solution {
        public List<Integer> grayCode(int n) {
            List<Integer> result = new ArrayList<>();
            if (n == 0) {
                result.add(0);
                return result;
            }
            List<Integer> prev = grayCode(n - 1);
            result.addAll(prev);
            for (int i = prev.size() - 1; i >= 0; i--) result.add(prev.get(i) + (int) Math.pow(2, n - 1));
            return result;
        }
    }

Log in to reply
 

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