小旭讲解 LeetCode 1238. 循环码排列

题目

LeetCode 1238. 循环码排列

思路

格雷码，特点是相邻两个数的二进制位只有一位不同。1940 年贝尔实验室的 Frank Gray提出，用于在 PCM（脉冲编码调变）方法传送信号时防止出错。因为其在临近数字转换时，变动的位数只有一位，使得误差降到最低。

生成格雷码 与 格雷码转换成二进制数的代码如下：

#include<bits/stdc++.h>
int n=10;
int b[1050];
void print_g() {
    for (int i=0;i<(1<<n);++i) {
        printf("%d ",i^(i>>1));
        b[i]=i^(i>>1);
    }
    printf("\n");
}
void print_b() {
    for (int i=0;i<(1<<n);++i) {
        int mask = b[i];
        int num = b[i];
        while (mask) {
            mask >>= 1;
            num ^= mask;
        }
        printf("%d ", num);
    }
    printf("\n");
}
int main() {
    print_g();
    print_b();
    return 0;
}

代码

class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        vector<int> ans{};
        int p=0;
        for(int i=0;i<(1<<n);++i) {
            ans.push_back(i^(i>>1));
            if((i^(i>>1))==start) p=i;
        }
        reverse(ans.begin(), ans.begin()+p);
        reverse(ans.begin()+p, ans.end());
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

参考

[1]. 格雷码 – 维基百科. https://zh.wikipedia.org/wiki/%E6%A0%BC%E9%9B%B7%E7%A0%81

欢迎分享，引用。若转载，请联系我，谢谢配合。
本文地址：https://qoogle.top/xiaoxu-tutorial-leetcode-1238-circular-permutation-in-binary-representation/