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.Solution:
public class Solution { public ArrayList<Integer> grayCode(int n) { ArrayList<Integer> solution = new ArrayList<Integer>(); grayCode(0, n, new boolean[(int)Math.pow(2,n)],solution); return solution; } public boolean grayCode(int number, int n, boolean[] used, ArrayList<Integer> solution) { used[number] = true; solution.add(number); if (solution.size()== (int) Math.pow(2,n)) return true; for(int i=0; i<n; i++) { int number2 = number ^ (1<<i); if(!used[number2]) { if(grayCode(number2, n, used, solution)) return true; } } solution.remove(solution.size()-1); used[number]=false; return false; } }
No comments :
Post a Comment