涨知识了，最近的每日一题都好难💥

资料

百度百科：「格雷码」

我们先看看普通的格雷编码

LeetCode89

格雷码规律解析

1
2
3
4
5
6
7
8
9
10
11
# n为1时 0 1 因为只有这两个数
n = 1  [0, 1]

# n为2时前两个数不变只是因为位数变了向前补0 [00, 01]
# n为2时后两个数可以总结出一个规律 
    # 最高位补1 低位数由n-1的数倒序排列 [11, 10]
n = 2  [00，01，11，10]

# n=3 时规律也是如此
n = 3  [000, 001, 011, 010, 110, 111, 101, 100]
...
  • 那么我们就可以根据这个思路实现代码

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var grayCode = function(n) {
    // 起始数字为0
    const ret = [0];
    // i 是需要在第i-1位补1
    // 刚开始需要在第0位补构成 [0, 1]
    for (let i = 1; i <= n; i++) {
        // 我们在这里获取length进行倒序遍历先后补充
        const m = ret.length;
        for (let j = m - 1; j >= 0; j--) {
            // (1 << (i - 1)) 代表最高位补1
            // ret[j] 与低位的 0 进行或运算还是 ret[j]
            // 而我们的j是倒序遍历 这样就可以做到格雷编码的规律了
            ret.push(ret[j] | (1 << (i - 1)));
        }
    }
    return ret;
};

本题格雷编码

LeetCode1238

异或 ^ 规律解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 我们需要用到三个推论
    # 异或两次得原值
    # 异或本身为0
    # 异或0为本身

# 也就是一个数异或同一个数两次，结果还是那个数
1 ^ 1 ^ 1 = 1
1 ^ 1 ^ 0 = 0
111 ^ 111 ^ 111 = 111

# 一个数异或它自己一定为零
1 ^ 1 = 0
111 ^ 111 = 000
101 ^ 101 = 000

# 一个数异或0一定为本身
010 ^ 000 = 010
111 ^ 000 = 111

# 也可以理解成我们先求出正常版的格雷编码
# 再将每个数都 ^ start 就求出来了
...
  • 那么我们岂不是可以先异或自己将起始值换为0
  • 再进行格雷编码规律的运算
  • 最后再异或变回去
  • 就可以解出本题呢？

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number} n
 * @param {number} start
 * @return {number[]}
 */
var circularPermutation = function(n, start) {
    // 起始数字为 start
    const ret = [start];
    // i 是需要在第i-1位补1
    for (let i = 1; i <= n; i++) {
        // m 是需要将多少数翻转
        const m = ret.length;
        // 将之前的数倒序翻转并向前补1
        for (let j = m - 1; j >= 0; j--) {
            // 此处翻转填补每个数
            // (1 << (i - 1)) 代表最高位补1
            // ret[j] 与低位的 0 进行或运算还是 ret[j]
            // 而我们的j是倒序遍历 就可以做到格雷编码的规律了
            // ^ start 可以让 起始位变为 000 再次 ^ 就会变回原来的数
            // 由于初始位置 ^ 了 start 为了后面的规律保持一致也要 ^ start
            ret.push(((ret[j] ^ start) | (1 << (i - 1))) ^ start);
        }
    }
    return ret;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
// 便于理解版
var circularPermutation = function(n, start) {
    // 先求常规格雷编码
    const ret = [0];
    for (let i = 1; i <= n; i++) {
        const m = ret.length;
        for (let j = m - 1; j >= 0; j--) {
            ret.push(ret[j] | (1 << (i - 1)));
        }
    }
    // 再将每个数异或start
    return ret.map(x=>x^start);
};