89. Gray Code
by Botao Xiao
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; } }
Subscribe via RSS