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;
          }
      }