掌握二进制转化成十进制运算的法则
11=1_2^0 + 12^1 = 3
方法一：
public class Solution {
public List grayCode(int n) {
List list = new ArrayList();
if(n == 0){
list.add(0);
return list;
} else if (n == 1) {
list.add(0);
list.add(1);
return list;
} else {
list.addAll(grayCode(n-1));
}
int pow = 1;
for(int i = 1; i < n; i++) {
pow = 2;
}
int size = list.size();
for(int i = 1; i <= size; i++) {
list.add((int)list.get(pow-i) + pow);
}
return list;
}
}
方法二：位运算，原理相同
/_
n = 0: 0
n = 1: 0 | 1
n = 2: 00, 01 | 11, 10
n = 3: 000, 001, 011, 010 | 110, 111, 101, 100
f(n) = f(n - 1) | 2 ^ (n - 1) + f(n - 1)
*/
public List grayCode(int n){
List list = new ArrayList();
list.add(0);
for(int i = 1; i <= n; i++) {
int size = list.size();
int base = 1 << (i-1);
for(int j = size-1; j >= 0; j--) {
list.add(list.get(j) + base);
}
}
return list;
}
Shawngbk
commented
7 years ago
掌握二进制转化成十进制运算的法则 11=1_2^0 + 12^1 = 3 方法一： public class Solution { public List grayCode(int n) {
List list = new ArrayList();
if(n == 0){
list.add(0);
return list;
} else if (n == 1) {
list.add(0);
list.add(1);
return list;
} else {
list.addAll(grayCode(n-1));
}
int pow = 1;
for(int i = 1; i < n; i++) {
pow = 2;
}
int size = list.size();
for(int i = 1; i <= size; i++) {
list.add((int)list.get(pow-i) + pow);
}
return list;
}
}
方法二：位运算，原理相同
/_
n = 0: 0
n = 1: 0 | 1
n = 2: 00, 01 | 11, 10
n = 3: 000, 001, 011, 010 | 110, 111, 101, 100
f(n) = f(n - 1) | 2 ^ (n - 1) + f(n - 1)
*/
public List grayCode(int n){
List list = new ArrayList();
list.add(0);
for(int i = 1; i <= n; i++) {
int size = list.size();
int base = 1 << (i-1);
for(int j = size-1; j >= 0; j--) {
list.add(list.get(j) + base);
}
}
return list;
}