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 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.
------------------------------------------------------------
Analysis (backtracking):
Keys of the problem:
1. The goal of the problem is to test your backtracking coding ability. So our effort will pay on this first. In order to use backtracking, you need to know how gray code works or how can it be built with backtracking. See figure below, when n=1, the code is 0 and 1. And when n=2, you can see how it's built base on n=1! And the same way, n=3 is built base on n=2.
So based on this rule, we can code with backtracking. And the backtracking is a way from top to down, like we build n=N first, in the building of n=N, we call n=N-1. In N-1, we call N-2, ... and all the way to n=1.
2. Another thing is the representation of these digits. In above figure, all are binary digits. In codes, we use decimal. And we need to return decimal instead of binary digits. You can see the solution about this problem in following codes.
//////////////////////////////////////Codes (4ms in Leetcode)//////////////////////////////////////
//with
backtracking
class Solution {
public:
vector<int> grayCode(int n) {
int p_tmp = pow(2, n);
vector<int> s(p_tmp);
if (n > 1){
vector<int> v_tmp = grayCode(n-1);
//use bitwise calculation
int i_tmp = 1 << (n - 1);
for (int i = 0; i < (p_tmp); i++){
if (i < p_tmp / 2){
s[i] =
v_tmp[i];
}
else{
s[i] = i_tmp +
v_tmp[p_tmp - 1 - i];//bitwise addition equals
addition in decimal
}
}
return s;
}
else if (n == 1){
s[0] = 0;
s[1] = 1;
return s;
}
else {
s[0] = NULL;
return s;
}
}
};
/////////////////////////////////////////////////////////////////////////////////////////////
Analysis (iteration):
Keys of the problem:
While the backtracking using a way of top to down, iteration uses a reverse procedure: from down to top! Namely it builds the n=1 first, then build n=2 based on n=1, and then all the way forward to n=N.
//////////////////////////////////////Codes (4ms in Leetcode)//////////////////////////////////////
//////////////////////////////////////Codes (4ms in Leetcode)//////////////////////////////////////
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> s(pow(2, n));
vector<int> s_tmp(pow(2, n));
if (n > 0){
for (int i = 1; i < n+1; i++){
if (i > 1){
int p_tmp = 1<<(i-1);
int v_tmp = pow(2, i);
for (int j = 0; j < (v_tmp); j++){
if (j < v_tmp / 2){
s_tmp[j]
= s[j];
}
else{
s_tmp[j]
= p_tmp + s[v_tmp - 1 - j];//bitwise addition
equals addition in decimal
}
}
//update s, vector can be assigned to vector directly!
s = s_tmp;
}
else{
s[0] = 0; //Note: can't use push_back here! Think about why?
s[1] = 1;
}
}
return s;
}
else{
s[0] = NULL;
return s;
}
}
};
No comments:
Post a Comment