JAVA solution (symmetrical and iterative)


  • 0
    T
    public class Solution {
        //Generate the num sequence iterativelly. Specifically, if we generate the num sequence with 3 bits, we need to know the sequence for 2 bits.
        /*Hold this idea and see the 3 bits sequence: 00,01,11,10,110,111,101,100
        The sequence for the first 4 nums and the sequence for the last 4 nums are symmetrical.
        Thus, we could fill our sequence iterativelly and symmetrically.
        */
        public List<Integer> grayCode(int n) {
            ArrayList<Integer>[] nums = new ArrayList[n+1];
            //base case
            nums[0] = new ArrayList<Integer>();
            nums[0].add(0);
            for(int i = 1; i <= n; i++){
                ArrayList<Integer> temp = new ArrayList<Integer>();
                for(int j = i-1; j>=0; j--){
                    ArrayList<Integer> temp2 = nums[j];
                    int size = temp2.size();
                    for(int k = size-1; k >= 0; k--){
                        // System.out.println(k);
                        temp.add(temp2.get(k)+(int)Math.pow(2,i-1));
                    }
                }
                nums[i] = temp;
            }
            
            List<Integer> output = new ArrayList<Integer>();
            for(int i = 0; i <= n; i++){
                ArrayList<Integer> temp = nums[i];
                for(int num : temp){
                    output.add(num);
                }
            }
            return output;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.