C#, A way using stack, easy to come up, without bit operations


  • 0

    The solution with most votes is excellent, but I am afraid seldom people can think it out in an interview if he has never met this problem.
    I try to give a solution which is easy to think out.
    Lets see when n = 1:
    0 1
    then n = 2:
    00 01 11 10 => 0 + each of {0,1} and 1 + each of {1, 0}
    then n = 3:
    000 001 011 010 110 111 101 100 => 0 + each of {00,01,11,10} and 1 + each of {10,11,01, 00}
    ....
    So we can see that what we need to do is when doing next round, we just need to output all the previous one, and reverse them, and add an 1 on top of them.
    adding an 1 means + 2^n, we can use a number to record it, every round we times 2. So we do not need to do bit operations in fact.
    To Reversing the results, we can use a stack.

    public class Solution {
        public IList<int> GrayCode(int n) {
            IList<int> Result = new List<int>();
            Result.Add(0);
            if (n == 0) return Result;
            Stack<int> stack = new Stack<int>();
            stack.Push(0);
            int Curr = 1;
            for (int i = 0; i < n; i++)
            {
                int m;
                while (stack.Count > 0)
                {
                m = stack.Pop();
                Result.Add(m + Curr);                
                }
                Curr = Curr * 2;
                foreach (int j in Result)
                {
                    stack.Push(j);
                }
            }
            return Result;
        }
    }
    

Log in to reply
 

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