leetcode1238.循环码排列

Posted on | In |
Words count in article: 380 | Reading time ≈ 1

给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：

  • p[0] = start
  • p[i] 和 p[i+1] 的二进制表示形式只有一位不同
  • p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同

示例：

1
2
3
4
输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
     所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]

分析：

1
2
3
4
5
格雷码：(0,1,2,,...,2^n-1) 排列为一圈，相邻两项之间只有一位不同
求格雷码：
	1.对称
	2.高位补1，低位补0
题目要求从start开始，因此最后需要和start异或

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        vector<int> a{0, 1};
        // 求格雷码
        for (int i = 1;i < n;i ++) {
            vector<int> b = a;
            // 对称
            for (int j = a.size() - 1;j >= 0;j --) 
                b.push_back(a[j] + (1 << i)); // 高位补1
            a = b;
        }
		// 保证从start开始
        for (int& x : a) x ^= start;

        return a;
    }
};

  • Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func circularPermutation(n int, start int) []int {
    a := []int{0, 1}
    for i := 1;i < n;i ++{
        var b = a
        for j := len(a) - 1;j >= 0;j -- {
            b = append(b, a[j] + (1 << i))
        }
        a = b
    }
    i := 0
    for _, x := range a {
        x ^= start
        a[i] = x
        i ++
    }
    
    return a
}

[原题链接](1238. 循环码排列 - 力扣（Leetcode）)

[相似题目](89. 格雷编码 - 力扣（Leetcode）)

0%