89 Gray Code – Medium
Problem:
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.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0 01 - 1 11 - 3 10 - 2 Note: For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
Thoughts:
key idea is that to generate gray code list for n, add 1<<(n-1) with the reverse order of the list for gray code n-1.
0: {0}
1: {0} + {1} 1<<0 = 1
2: {0,1} + {11, 10} 1<< 1 = 10
3: {0, 1, 11, 10} + {110, 111, 101, 100}1 << 2 = 100
Solutions:
public class Solution {
public List<Integer> grayCode(int n) {
ArrayList<Integer> result = new ArrayList<Integer>();
result.add(0);
ArrayList<Integer> toAddAll = new ArrayList<Integer>();
for (int i = 0; i < n; i ++){
toAddAll.clear();
int offset = 1 << i;
for (int j = result.size() -1 ; j >= 0; j --){
int toAdd = result.get(j) + offset;
toAddAll.add(toAdd);
}
result.addAll(toAddAll);
}
return result;
}
}
Updated: 11/10/2016 This is an alternative, is a little bit more straightforward thinking, but this is taking more time than the solution above. Because it’s checking a lot of same element. But this solution is easier to come up with.
public class Solution {
public List<Integer> grayCode(int n) {
List<Integer> result = new LinkedList<Integer>();
result.add(0);
process(0, n, result);
return result;
}
private void process(int num, int n , List<Integer> result) {
for (int i = 0; i < n; i ++) {
int mask = 1 << i;
int tmp = num ^ mask;
if (!result.contains(tmp)) {
result.add(tmp);
process(tmp, n, result);
}
}
}
}