This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

89. Gray code

Gray code is a binary number system in which two consecutive values differ by only one digit.

Given a non-negative integer n representing the total number of encoded digits, print its Gray encoding sequence. Even if there are multiple different answers, you only need to return one of them. Gray coded sequences must begin with 0. Example 1: Input: 2 Output: [0,1,3,2] Explanation: 00-0 01-1 11-3 10-2 For a given n, its gray encoding sequence is not unique. For example, [0,2,3,1] is also a valid gray encoding sequence. 00-0 10-2 11-3 01-1 Example 2: Input: 0 Output: [0] Explanation: We define that a Gray code sequence must start with 0. Given a Gray coding sequence with total number of bits n, its length is 2N. When n = 0, the length is 20 = 1. Therefore, when n = 0, its Gray coding sequence is [0].

Second, train of thought analysis

  • I’m going to focus in a moment on the overall approach to the problem. Some of the ideas in the middle don’t solve the problem. But to their own final solution is a catalyst.

Formula method

  • First of all, it can only appear in the code0,1Two numbers. There is no limit to how many times the two numbers can appear, and no limit to where they can be placed. Then permutations and combinations of two numbers within a given length limit
  • Right! What the author thinks of above all here is to solve by formula way.

  • First of all, the gray code number is n, and then there are n blocks inside that are used to store elements, zeros or ones. So in all of these possibilities we can think of 0 as occurring between 0 and n. And since there are only 0’s and 1’s, the number of 0’s is going to be 1’s

  • So we can list all the possibilities

G n 0 + C n 1 + C n 2 + … + C n 1 G_{n}^{0}+C_{n}^{1}+C_{n}^{2}+\cdots+C_{n}^{1}
  • And the above formula we all know it when we study mathematics2^n-1
  • It’s a simple formula, but all I’ve got here is the number of results. You can’t get the real result set. So it doesn’t work that way

Law of artful solution

  • The above formula doesn’t solve the problem completely, but at least we know what the length of our final result is. That’s at least a little helpful.
  • The number summarized above is exactly one permutation of the data in binary.

  • Binary data is arranged from smallest to largest. The difference between two adjacent data points is 1.

Dynamic programming

  • The above rule can be understood as the transfer equation of dynamic programming. And after the previous step we can also determine the initial value is 0. After the first step we can determine the scope of the transition.
  • So many conditions have been gathered. So what we’re left with is the last step in dynamic programming. You can do it from small to large

AC code

public List<Integer> grayCode(int n) {
    Double pow = Math.pow(2, n);
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < pow.intValue(); i++) {
        list.add(i);
    }
    return list;
}
Copy the code
  • Do not know whether the topic did not understand clearly, there is no verification

Back to the topic

  • In this system, two consecutive values differ by only one digit. It is because of this sentence that our analysis above is biased. There is only one difference between two consecutive values

  • Cases like the one above would fit the bill. The data we analyzed above is incremental. This is the number that comes up01 、10. This code does not meet the requirements. Because each digit is different.
  • We start with nothing, and when we expand to 1 bit we get 0 and 1. And just to see what’s going on here we’re going to go from 1 to 2 bits

  • Add 0 in front of the result set n=1. It doesn’t matter whether you fill the 0 first or you fill the 0 first. Because it’s symmetric

  • And when you fill in the zeros, you’re going to fill in the ones in front. And 0 and 1 are different. So it should be followed by 1 as shown here

  • And then we end up with something like this

  • This is the same as our previous snowballing article. The only thing that needs to be done in the extension is mirror inversion

  • One other thing we need to know is that when we add zeros and we convert them to decimal it doesn’t actually change the size of the data

  • So just like snowballing, we don’t need to do anything to the metadata except to do a complement of 1 to the data after the mirror.
public List<Integer> grayCode(int n) {
    List<Integer> list = new ArrayList<Integer>();
    list.add(0);
    for (int i = 0; i < n; i++) {
        for (int j = list.size()-1; j >=0; j--) {
            list.add((int)Math.pow(2,i) + list.get(j)); }}return list;
}
Copy the code

  • Later, there were more efficient codes on the website. But the logic is the same. The code on the official website appends data by shifting.

Four,

  • The body is the key. This is a mistake or blame themselves on the topic is not clear began to do the topic.
  • It’s the same snowballing as before but the expansion strategy is slightly different when it comes to scaling. Suggestions and snowball comparison oh

Like and follow