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 - 2Note:
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.
A: 递归调用而已
class Solution { public: vector<int> grayCode(int n) { if(n==0) return vector<int>{0}; auto sub = grayCode(n-1); int subSize = sub.size(); for(int i =subSize -1 ; i>=0; i--){ sub.push_back(sub[i] + pow(2,n-1)); } return sub; } };
Error:
1: 刚开始,base情况设为了n == 1
2: 后面要加的时候,没有逆序
-------------------第二遍,迭代,基于binary的一个个位置的从0变1, 就把之前的list都copy下来,再0变1. -----------
public class Solution { public List<Integer> grayCode(int n) { List<Integer> al = new LinkedList(); al.add(0); int start = 0; for(int i =0;i<n;i++){ List<Integer> copyAL = new LinkedList(al); for(int j =copyAL.size()-1;j>=0;j--) al.add( (1<<i) +copyAL.get(j)); } return al; } }
Mistakes:
1: curList 必须先initialize (刚开始,是在n ==0, 和n==1的时候,initilize了,但是, 其余的情况,就忘了initialize了)
2:输入为0 的时候,输入应该是 【0】, 而不是空的----------》这个是应该面试的时候问明白。
0 | |
Output: | [] |
Expected: | [0] |
Learned:
1: 直接把一个数组,转换成String是不太容易的。 结果会有【】 出现。 例如下面:
int[] iArray= {2,3};
String str = Arrays.toString(tmp);
System.out.println(str);
因此,要把“,” 去掉, 还有前后的[] 也要去掉。
String temp = Arrays.toString(iArray).replace(", ", " ");
String encoded = temp.substring(1, temp.length()-2);
No comments:
Post a Comment