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
就是找规律,把上一层得到的结果逆序前面一位置1,然后把这些新数加回结果中
public class Solution { //Time: O(n^2) Space: O(n^2) public ArrayList<Integer> grayCode(int n) { ArrayList<Integer> res = new ArrayList<Integer>(); res.add(0); if (n <= 0) { return res; } res.add(1); for (int i = 1; i < n; i++) { for (int j = res.size() - 1; j >= 0; j--) { int cur = res.get(j); cur |= (1 << i); res.add(cur); } } return res; } }
No comments:
Post a Comment