LeetCode-89-Gray Code(模拟/递归)-Medium

题意理解：

1. 列举出n位的所有格雷码；

2. 列举顺序必须按照示例中的顺序；

题目分析：

1. 找规律：

1）1位的格雷码为

0

1

2）n位的格雷码为n-1位格雷码的集合Set1，加上n-1位格雷码的集合最左侧添加一个1 Set2，其中，Set2中的元素为Set1中元素的从后向前的遍历结果，如

000

001

---------

011

010

------

110

111

101

100

解题代码：

public class Solution {
    public List<Integer> grayCode(int n) {
        ArrayList<Integer> ans=new ArrayList();
        if(n==0){
            ans.add(new Integer(0));
            return ans;
        }
        
        if(n==1){
            ans.add(new Integer(0));
            ans.add(new Integer(1));
            
            return ans;
        }else{
            List<Integer> tmp=grayCode(n-1);
            for(int i=0; i<tmp.size(); i++){
                Integer elem=tmp.get(i);
                ans.add(elem);
            }
             
             for(int i=tmp.size()-1; i>=0; i--){   
                Integer elem=tmp.get(i);
                int t=elem.intValue()+(int)Math.pow(2,n-1);
                ans.add(new Integer(t));
            }
            
            return ans;
        }
    }
}