题目
思路
格雷码,特点是相邻两个数的二进制位只有一位不同。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/
3replica
[…] 小旭讲解 LeetCode 1238. 循环码排列 […]