89. Gray Code

89. Gray Code

Question

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Example 1:

Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1

Example 2:

Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
             A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
             Therefore, for n = 0 the gray code sequence is [0].

Thinking:

• Method 1:回溯法
  • 1： 0， 1
  • 2： 00， 01， 11， 10 （除了第一个字符均是对称）
  • 3： 000， 001， 011， 010， 110， 111， 101， 100（对称）

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        if(n == 0){
            result.add(0);
            return result;
        }else{
            List<String> tempRes = new ArrayList<>();
            backtrace(n, tempRes);
            for(String s : tempRes){
                result.add(binary2Int(s));
            }
            return result;
        }
    }
    private static void backtrace(int n, List<String> result){
        if(n == 1){
            String[] a = {"0", "1"};
            result.addAll(Arrays.asList(a));
        }else{
            backtrace(n - 1, result);
            int size = result.size();
            for(int i = 0; i < size; i++){
                result.add(result.get(size - 1 - i));
            }
            List<String> temp = new ArrayList<>();
            for(int i = 0; i < size; i ++)
                temp.add("0" + result.get(i));
            for(int i = size; i < 2 * size; i++)
                temp.add("1" + result.get(i));
            result.clear();
            result.addAll(temp);
        }
    }
    private static int binary2Int(String s){
        int len = s.length();
        int result = 0;
        for(int i = len - 1; i >= 0; i--){
            int cur = s.charAt(i) - '0';
            result = result * 2 + cur;
        }
        return result;
    }
}

二刷

还是参考了一刷的结果，要记住对称这个特点。这道题还是比较tricky。

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = null;
        if(n == 0){
            result = new LinkedList<>();
            result.add(0);
        }else{
            List<String> temp = new LinkedList<>();
            backtrace(temp, n);
            result = getResult(temp);
        }
        return result;
    }
    private void backtrace(List<String> temp, int index){
        if(index == 1){
            temp.addAll(Arrays.asList("0", "1"));
        }else{
            backtrace(temp, index - 1);
            int size = temp.size();
            List<String> save = new LinkedList<>();
            for(int i = 0; i < size; i++)
                temp.add(temp.get(size - 1 - i));
            for(int i = 0; i < size; i++)
                save.add("0" + temp.get(i));
            for(int i = size; i < 2 * size; i++)
                save.add("1" + temp.get(i));
            temp.clear();
            temp.addAll(save);
        }
        
    }
    private List<Integer> getResult(List<String> res){
        int size = res.size();
        List<Integer> result = new LinkedList<>();
        for(String ss : res)
            result.add(stringToInteger(ss));
        return result;
    }
    private Integer stringToInteger(String s){
        char[] arr = s.toCharArray();
        int res = 0;
        for(int i = 0; i < arr.length; i++){
            res *= 2;
            res += arr[i] - '0';
        }
        return res;
    }
}

Amazon session

• Method 1: recursion w/o memory;

    class Solution {
        private List<Integer> result;
        private int n;
        private Set<String> visited;
        public List<Integer> grayCode(int n) {        
            this.result = new ArrayList<>();
            if(n == 0){
                this.result.add(0);
                return this.result;
            }
            this.n = n;
            this.visited = new HashSet<>();
            String init = "";
            for(int i = 0; i < n; i++){
                init += 0;
            }
            visited.add(init);
            dfs(init);
            return this.result;
        }
        private void dfs(String cur){
            this.result.add(parseBinaryInt(cur));
            if(result.size() == Math.pow(2, n)) return;
            else{
                for(int i = 0; i < cur.length(); i++){
                    char c = cur.charAt(i);
                    String next = cur.substring(0, i) + (c == '0' ? '1': '0') + cur.substring(i + 1);
                    if(!visited.contains(next)){
                        visited.add(next);
                        dfs(next);
                    }
                }
            }
        }
        private int parseBinaryInt(String s){
            char[] arr = s.toCharArray();
            int num = 0;
            for(char c : arr){
                int diff = c - '0';
                num = num * 2 + diff;
            }
            return num;
        }
    }