Alibi

My Life is Getting Better

Leetcode[89] Gray Code

06 Nov 2015

###Task The gray code is a binary numeral system where two successive values differ in only one bit.

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.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0 01 - 1 11 - 3 10 - 2 Note: For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

###Python ####Iterative

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n == 0:
            return [0]
        ret = [0]
        for i in range(n):
            flip = 1 << i
            num = len(ret)
            for j in reversed(range(num)):
                ret.append(ret[j] | flip)
        return ret

####Recursive

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n == 0:
            return [0]
        ret = self.helper(n)
        return [int(code, 2) for code in ret]
    def helper(self, n):
        if n == 1:
            return ['0', '1']
        res = self.helper(n - 1)
        ret = []
        for num in res:
            ret.append('0' + num)
        for num in res[::-1]:
            ret.append('1' + num)
        return ret

####Generator

    def grayCodeGen(self, n, reverse=False):
        if n == 1:
            if reverse:
                yield "1"
                yield "0"
            else:
                yield "0"
                yield "1"
        else:
            if reverse:
                # all the "1"s start first
                gcprev = self.grayCodeGen(n-1, False)
                for code in gcprev:
                    yield "1" + code
                gcprev = self.grayCodeGen(n-1, True)
                for code in gcprev:
                    yield "0" + code
            else:
                # all the "0" start first
                gcprev = self.grayCodeGen(n-1, False)
                for code in gcprev:
                    yield "0" + code
                gcprev = self.grayCodeGen(n-1, True)
                for code in gcprev:
                    yield "1" + code

###Java

/*
    you must be kidding.
    Time ~ O(N^2), Space ~ O(1) 
    可以用以下规则实现：
    n = 1:     0  |   1
    n = 2:   00    01 | 11   10
    n = 3: 000  001 011 010 | 110 111 101 100
    ...
    红线左边的为上一行序列从左往右每个码前加 0，
    红线右边的为上一行序列从右往左每个码前加 1。
*/
public class Solution {

    public List<Integer> grayCode(int n) {
    	List<Integer> res = new ArrayList<Integer>();
        if (n < 0) {
        	return res;
        }

        res.add(0);
        for (int i = 0; i < n; i++) {
            int flipper = 1 << i; // flipper used to change the i-bit from 0 into 1
            int size = res.size();
            for (int j = size - 1; j >= 0; j--) {
                res.add(res.get(j) | flipper);
            }
        }
        //so basically, what we does is convert greycode(n - 1) to graycode(n)
        //namely, add 1 to all the previous result backward
        return res;
    }
}

###Points

Related Posts