1  /**
 2       * The gray code is a binary numeral system where two successive values differ in only one bit.
 3       * 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.
 4       * For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
 5       * 00 - 0
 6       * 01 - 1
 7       * 11 - 3
 8       * 10 - 2
 9       * Note:
10       * For a given n, a gray code sequence is not uniquely defined.
11       * For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
12       * For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
13       * Solution : find the rule!!!!
14       * @param n
15       * @return
16       */
17      public ArrayList<Integer> grayCode(int n) {
18          ArrayList<Integer> r = new ArrayList<Integer>();
19          r.add(0);
20          if(n == 0)
21              return r;
22          r.add(1);
23          if(n == 1)
24              return r;
25          for(int m = 1;m<n;m++){
26              int cur_size = r.size();
27              int base = (int) Math.pow(2, m);
28              for(int i = cur_size - 1;i>=0;i--){
29                  r.add(r.get(i)+base);
30              }
31          }
32          return r;
33      }