• This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together

  • The LeetCode is 89

    • Time: 2022-01-08
    • Strength button difficulty: Medium
    • Personal difficulty: Medium+
    • Data structure: binary, decision tree
    • Algorithms: dynamic programming, backtracking, bit operation

2022-01-08: LeetCode: 89. Gray code

1. Topic description

  • Title: Original title link

    • An N-bit Gray Code sequence is a sequence of 2N integers in which:
      • Each integer is in the range [0, 2n−12^ n-12n −1] (including 0 and 2n−12^ n-12n −1)
      • The first integer is 0
      • An integer does not occur more than once in a sequence
      • The binary representation of each pair of contiguous integers is exactly one bit different
      • The binary representations of the first and last integers differ by exactly one bit
    • Given an integer n, return any valid n-bit gray code sequence

  • Input output specification

    • Enter: bits of gray code n
    • Output: Array of gray code integer sequences

  • Input and output examples

    • Enter: n = 2
    • Output:,1,3,2 [0]
    • Enter n = 3
    • Output: [0,1,3,2,6,7,5,4], i.e000 - > 001 - > 011 - > 010 - > 110 - > 111 - > 101 - > 100

2. Method 1: Backtrack

  • Train of thought

    • In this case, n-bit gray codes are required to be solved, which can be obtained by observing the following examples:
      • When n = 2, the output sequence is [0,1,3,2], corresponding to [00, 01, 11, 10]
      • When n = 3, output sequence [0,1,3,2,6,7,5,4] corresponds to [000, 001, 011, 010, 110, 111, 101, 100]
    • The rule can be found: for the binary form of gray code, if the value of bits and bits (0 or 1), it will satisfy the symmetric relationship between 01 and 10
    • By abstracting the whole problem into the form of decision tree, we can see the symmetry rule of 01 and 10 of Gray code sequence more obviously
    • At this point, this problem is transformed into a common combination problem in backtracking, and the combination has a certain rule, that is, the traversal of each layer of the decision tree is to traverse 01 first, then 10, and so on

  • Backtracking + decision tree idea diagram

  • Complexity analysis: N is the number of bits in the input gray code

    • Time complexity: O(2n)O(2^n)O(2n), a total of 2N2 ^n2n digits are traversed to form gray code sequence
    • Space complexity: O(n)O(n)O(n) O(n)O(n)O(n)

  • Solution: StringBuilder stores binary numbers during tracebacks

    List<Integer> grayCodeList = new ArrayList<>();
StringBuilder binaryCode = new StringBuilder();
int[] left = new int[] {0.1};
int[] right = new int[] {1.0};

public List<Integer> grayCode(int n) {
    // int[] nums: this array represents the next binary number to fetch
    backTracing(n, binaryCode, left);
    return grayCodeList;
}

private void backTracing(int n, StringBuilder binaryCode, int[] nums) {
    // Find a matching result and add it to the result set
    if (binaryCode.length() == n) {
        Integer.valueof (binarycode.tostring (), 2);
        int grayCode = Integer.parseInt(binaryCode.toString(), 2);
        grayCodeList.add(grayCode);
        return;
    }

    // traceback the {0,1} array
    binaryCode.append(nums[0]);
    backTracing(n, binaryCode, left);
    binaryCode.deleteCharAt(binaryCode.length() - 1);

    // traceback the {1,0} array
    binaryCode.append(nums[1]);
    backTracing(n, binaryCode, right);
    binaryCode.deleteCharAt(binaryCode.length() - 1);
}
Copy the code

  • thinking

    • This example uses a stringStringBuilderType to store the binary number in the traceback process for useIntegerThe API of the class converts the binary number directly to the decimal number to be printed at the end
    • You can also use the backtracking commonListType to store binary numbers, at this time need to manually implement binary and decimal conversion
    • The following version of the solution is a bit more complicated

  • List stores the binary numbers in the traceback process

    List<List<Integer>> binaryCodeList = new ArrayList<>();
List<Integer> list = new ArrayList<>();
int[] left = new int[] {0.1};
int[] right = new int[] {1.0};

public List<Integer> grayCode(int n) {
 backTracing(n, list, left);
 // Convert binary to decimal
 List<Integer> grayCodeList = new ArrayList<>();
 for(List<Integer> binaryCode:binaryCodeList) {
     int grayCode = 0;
     for(int i = 0; i < binaryCode.size(); i++) {
         grayCode = grayCode*2 + binaryCode.get(i);
		}
     grayCodeList.add(grayCode);
 }
 return grayCodeList;
}

private void backTracing(int n, List<Integer> list, int[] nums) {
 // Find a matching result and add it to the result set
 if (list.size() == n) {
     binaryCodeList.add(new ArrayList<>(list));
     return;
 }

 // traceback the {0,1} array
 list.add(nums[0]);
 backTracing(n, list, left);
 list.remove(list.size() - 1);

 // traceback the {1,0} array
 list.add(nums[1]);
 backTracing(n, list, right);
 list.remove(list.size() - 1);
}
Copy the code

3. Method 2: bit operation + binary derivation

  • Train of thought

    • First, we need to understand the characteristics of gray code:Grey Code Encyclopedia
      • A gray code with a binary value of 0 is the zeroth term
      • The first term changes the rightmost bit
      • The second item changes the left bit of the first 1 bit from the right
      • The third and fourth terms are the same as the first and second terms, and so on, n bits of gray code can be arranged
    • Example: n = 3
      • 0, 0, 0 the zeroth term is initialized to 0
      • 0, 0, 1 The first term changes the rightmost bit of the previous term
      • 0, 1, 1 The second term changes the left bit of the first 1 bit from the right of the previous term
      • 0, 1, 0, the third term is the same as the first term, changing the right most bits of the previous term
      • 1, 1, 0, the fourth term and the second term, change the left of the first 1 bit from the right of the uppermost term
      • 1, 1, 1, the fifth term is the same as the first term, changing the right-most bits of the previous term
      • 1, 0, 1 the sixth term and the second term change the left of the first 1 bit from the right of the uppermost term
      • 1, 0, 0. The seventh term is the same as the first term, changing the right-most bits of the previous term

  • Complexity analysis: n is the length of the path string

    • Time complexity: O(n∗2n)O(n*2^n)O(n∗2n)
    • Space complexity: O(1)O(1)O(1)

  • Use integer.highestonebit ()

    public List<Integer> grayCode(int n) {
 List<Integer> res = new ArrayList<Integer>();
 res.add(0); / / zero
 for (int i = 1; i < (1 << n); i++) {
     int prev = res.get(i - 1);
     // 1. Change the rightmost bit
     if (i % 2= =1) {
         prev ^= 1;  // 0 ^ 1 = 1 and 1 ^ 1 = 0
         res.add(prev);
     } else { // 2. Change the left bit of the first 1 bit from the right
         int temp = prev;
         // Find the first 1 bit from the right
         for (int j = 0; j < n; j++) {
             if ((temp & 1) = =1) {
                 // Change the left position of the position
                 prev = prev ^ (1 << (j + 1));
                 res.add(prev);
                 break;
             }
             // Shift to the right
             temp = temp >> 1; }}}return res;
}
Copy the code

4. Method three: dynamic planning

  • Idea: Dynamic planning

    • In this case, n-bit gray codes are required to be solved, which can be obtained by observing the following examples:
      • When n = 1, the output sequence is [0,1]
      • When n = 2, the output sequence is [0,1,3,2]
      • When n = 3, output sequence [0,1,3,2,6,7,5,4]
    • That is, the rule of prefix symmetry can be obtained
      • A 1-bit gray code has two digits
      • When n increases, the new sequence is related to the old sequence, and the new sequence is appended to the old sequence
      • The first 2n2^n2n digits in an N + 1-bit gray code are equal to an n-bit gray code sequence, written sequentially, prefixed with 0
      • The last 2n2^n2n code words in the N +1 bit gray code are equal to the n-bit gray code sequence, written in reverse order, prefixed by 1
      • The last bit of the Gray code is 2n−12^{n-1}2n−1 because it differs only one bit from the first (0)
    • Therefore, the sequence of n+1 bit gray codes is equal toN – bit gray code sequence prefixed by 0 + N – bit gray code sequence with prefix 1 in reverse order
      • The binary prefix +0 indicates that the number has not changed
      • The binary prefix +1 represents the decimal addition of 2n2^n2n to the original n-bit binary number
    • According to this kind of new sequence depends on the old sequence, and the boundary (beginning and end gray code) is determined, the idea of dynamic programming can be considered to solve the problem

  • Illustration: symmetry rule of prefixes

  • Dynamic planning of the three musketeers

    • DP array definition:dp[i]Represents the i-th digit in the gray code sequence, starting at 0
    • Boundary conditions: DP [0] = 0 DP [n] = 2n−12^{n-1}2n−1
    • State transition equation: Note that when solving the n-bit Gray code sequence, the reference is the n-1 bit gray code sequence
      • I < 2 n – 1 I < 2 ^ {n – 1} I < 2 n – 1: dp [I] = dp dp [I] [I] = dp dp [I] [I] = dp [I]
      • 2 n – 1 < = I < 2 n2 ^ {}, n – 1 < = I < 2 ^ n2n – 1 < = I < 2 n: dp [I] = dp (2 n – 1 – I] + 2 n – 1 dp [I] = dp (2 ^ n – 1 – I] + 2 ^ {}, n – 1 dp [I] = dp (2 n – 1 – I] + 2 n – 1
    • Pay attention to
      • In this case, instead of using the ordinary array DP, use the List for DP
      • Since it is necessary to know the situation of n-1 bit when solving the n-bit gray code sequence, the outer loop of 0-N bit gray code sequence is needed
      • Since the first half of the sequence does not change, you can add directly from the second half of the sequenceadd

  • Complexity analysis: n is the length of the path string

    • Time complexity: O (2 n) O (2 ^ n) O (2 n), and the outer loop O (n) O (n) O (n), inner loop every time for O (2 I) O (2 ^ I) O (2 I), the last time for O (2 n) O (2 ^ n) O (2 n), overall for O (2 n) O (2 ^ n) O (2 n) level
    • Space complexity: O(1)O(1)O(1)

  • Answer key

    // Method 2: dynamic programming
public List<Integer> grayCode(int n) {
    List<Integer> dp = new ArrayList<>();
    dp.add(0);
    for (int i = 0; i < n; i++) {
        int prefix = 1 << i; // The prefix is 1
        for (int j = dp.size() - 1; j >= 0; j--) { dp.add(dp.get(j) + prefix); }}return dp;
}
Copy the code

5. Method 4: Gray code formula

  • Train of thought

    • An N-bit binary code can be directly converted into an N-bit gray code, and the corresponding formula is:
      • For n-bit binary codes, numbered 0 to n-1 from right to left, that is, Bn−1… B1B0B_{n-1}… B_1B_0Bn – 1… B1B0
      • For n-bit gray codes, numbered from 0 to n-1 from right to left, that is, Gn−1… G1G0G_{n-1}… G_1G_0Gn – 1… G1G0
      • If the i-th bit of the binary code is the same as the I-th bit of the I +1 bit, the i-th bit of the corresponding gray code is 0, otherwise it is 1
      • When I +1 = n, the NTH bit of the binary code is considered to be 0, i.e., the n-1st bit remains unchanged
    • Therefore, the whole gray code sequence can be calculated directly according to the formula

  • Diagram: Formula

  • Complexity analysis: n is the length of the path string

    • Time complexity: O(2n)O(2^n)O(2n)
    • Space complexity: O(1)O(1)O(1)

  • Answer key

    public List<Integer> grayCode(int n) {
 List<Integer> res = new ArrayList<>();
 for(int binary = 0; binary <1 << n; binary++){
     res.add(binary ^ binary >> 1);
 }
 return res;
}
Copy the code

The last

LeetCoder, a new developer, has published some problem solving solutions based on other developers’ ideas (links to resources are at the bottom). Please follow me if this article helps. I hope you can give me three even “like” & “favorites” & “attention” ~ ~ ~ also hope you have time to visit my “personal blog”.

The resources

  • Graycode Wiki: zh.wikipedia.org/wiki/%E6%A0…