This problem is a simulation. I know that the solution must use bit operation, but it won't be. It's uncomfortable. Record my stupid thinking than simulation (java takes 41ms, really slow), and then calculate honestly.

Idea:

1. First of all, there is an interesting rule for gray codes, that is, the first n gray codes of n+1 bits are positive order n-bit gray codes plus prefix 0, and the last n are reverse order n-bit gray codes plus prefix 1. This rule is very cool to use when learning information theory.
2. According to this law, I can use the idea of dynamic programming, first record 1-bit gray code, get 2-bit gray code according to 1-bit gray code, and then get 3-bit gray code according to the obtained 2-bit gray code,... Traverse in turn until n-bit gray code is obtained.
3. Finally, convert the obtained n-bit gray code (binary string form) into decimal numbers, store it in the ans list and return it.

code:

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<>();
        List<StringBuilder> list = new ArrayList<>();
        list.add(new StringBuilder().append(0));
        list.add(new StringBuilder().append(1));
        for (int i = 2; i <= n ; i++) {
            int len = list.size();
            //before + 0
            for (int j = 0; j < len; j++) {
                StringBuilder b = new StringBuilder();
                b.append(0);
                b.append(list.get(j));
                list.add(b);
            }
            //after + 1
            for (int j = len-1; j >=0; j--) {
                StringBuilder b = new StringBuilder();
                b.append(1);
                b.append(list.get(j));
                list.add(b);
            }
            list = list.subList(len,list.size());
        }
        for (StringBuilder stringBuilder : list) {
            ans.add(Integer.parseInt(stringBuilder.toString(),2));
        }
        return ans;
    }
}

The following is the code of the official solution. I still don't understand how to operate it. I feel that the formula written has nothing to do with the actual operation. But the code is not long, back it!

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        for (int i = 0; i < 1 << n; i++) {
            ret.add((i >> 1) ^ i);
        }
        return ret;
    }
}

Author: LeetCode-Solution
 Link: https://leetcode-cn.com/problems/gray-code/solution/ge-lei-bian-ma-by-leetcode-solution-cqi7/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.

Or simulation, I suddenly found that my first reaction to the problem is to simulate first. As long as I can write it by simulation, the first way to jump out of my brain is simulation, emm. This is rigid thinking~

Idea:

1. Add stone to the list and sort the list first.
2. Loop through the list. If x is the penultimate element, that is, the next largest value, and Y is the penultimate element, that is, the maximum value. When x = y, remove both X and Y from the list; otherwise, remove y from the list and change the value at the corresponding position of X to y-x. And reorder the list.
3. When the length of the list is less than 2, exit the cycle. At this time, if the length of the list is 0, it means that all the stones are crushed and return to 0; If the length of the list is 1, it means that there is still a stone that has not been crushed. Return the weight of the stone.

code:

class Solution {
    public int lastStoneWeight(int[] stones) {
        List<Integer> list = new ArrayList<>();
        for (int i : stones){
            list.add(i);
        }
        Collections.sort(list);
        int len = list.size();
        while(len>=2){
            int x = list.get(len-2),y = list.get(len-1);
            list.remove(len-1);
            if (x == y){
                list.remove(len-2);
            }else {
                list.set(len-2,y-x);
            }
            Collections.sort(list);
            len = list.size();
        }
        return len == 1 ? list.get(0) : 0;
    }
}