Gray Code

1. Title

89. Gray Code

2. Http address

https://leetcode.com/problems/gray-code/?tab=Description

3. The question

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.

4 My code(AC)

public class Solution {
    public List<Integer> grayCode(int n) {
        

        List<Integer> reList = new ArrayList<Integer>();
        reList.add(0);
        if (n <= 0) {
            return reList;
        }

        int cur = 0;
        String curBinaryStr = Integer.toBinaryString(cur);
            n = 1 << n;
        curBinaryStr = "0" + curBinaryStr;
        for (int i = 1; i < n ; i++) {
            int len = curBinaryStr.length();
            for (int j = len -1; j >= 0; j--) {
                String newStr = curBinaryStr.substring(0, j);
                if (curBinaryStr.charAt(j) == '1') {
                    newStr += "0";
                } else {
                    newStr += "1";
                }
                newStr += curBinaryStr.substring(j + 1, len);

                int newInt = Integer.valueOf(newStr, 2);

                if (!reList.contains(newInt)) {
                    reList.add(newInt);
                    cur = newInt;
                    curBinaryStr = Integer.toBinaryString(cur);
                    curBinaryStr = "0" + curBinaryStr;
                    
                    break;
                }
            }
        }

        return reList;
    
    }
}

相关推荐