[LeetCode]89 Gray Code

1728 ワード

https://oj.leetcode.com/problems/gray-code/
public class Solution {
    public List<Integer> grayCode(int n) 
    {
        //  :
        // n = 0:
        // 0
        //
        // n = 1:
        // 0
        // 1
        //
        // n = 2:
        // 00
        // 01
        // 11
        // 10
        //
        // n = 3
        // 000
        // 001
        // 011
        // 010
        // 110
        // 111
        // 101
        // 100
        //
        //   n-1     s
        //     i,  0, 
        //     i,  1, 

        if (n < 0)
            return Collections.emptyList();
            
        if (n == 0)
            return Collections.singletonList(0);
        
        List<String> str = code(n);
        List<Integer> toReturn = new ArrayList<>();
        for (String s : str)
        {
            toReturn.add(Integer.parseInt(s, 2));
        }
        return toReturn;
    }
    
    private List<String> code(int n)
    {
        if (n == 1)
        {
            List<String> toReturn = new ArrayList<>();
            toReturn.add("0");
            toReturn.add("1");
            return toReturn;
        }
        
        List<String> last = code(n - 1);
        List<String> toReturn = new ArrayList<>();
        // for each e in last, append 0, to head. and into new result
        for (String s : last)
        {
            toReturn.add("0" + s);
        }
        // for each e in last (reverse), and append (1) in it.
        for (int i = last.size() - 1 ; i >= 0 ; i --)
        {
            toReturn.add("1" + last.get(i));
        }
        return toReturn;
    }
}