【LeetCode第 160 场周赛】5239. 循环码排列
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/shiliang97/article/details/102785299
给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：
p[0] = startp[i]和p[i+1]的二进制表示形式只有一位不同p[0]和p[2^n -1]的二进制表示形式也只有一位不同
指向知识点格雷码：我考试时候猜到了逆序加一
示例 1：
输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]示例 2：
输出：n = 3, start = 2
输出：[2,6,7,5,4,0,1,3]
解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)提示：
1 <= n <= 160 <= start < 2^n
排行榜上 别人的答案。。。也看不懂
int gray[70000];
class Solution {
public:
vector<int> circularPermutation(int n, int start) {
vector<int> ans;
for (int i = 0; i < (1 << n); ++i)
gray[i] = (i ^ (i >> 1));
int pos = 0;
for (int i = 0; i < (1 << n); ++i)
if (gray[i] == start) {
pos = i;
break;
}
for (int i = pos; i < (1 << n); ++i)
ans.push_back(gray[i]);
for (int i = 0; i < pos; ++i)
ans.push_back(gray[i]);
return ans;
}
};class Solution {
public:
int num[1<<16|5];
vector<int> circularPermutation(int n, int start) {
vector<int>ans;
for(int i=0;i<1<<n;i++)num[i]=0;
for(int i=1;i<=n;i++)for(int j=(1<<i)-1;j>=1<<i-1;j--)
num[j]=1<<i-1|num[(1<<i)-1-j];
int pos;
for(int i=0;i<1<<n;i++)if(num[i]==start){
pos=i;
break;
}
for(int i=pos;i<1<<n;i++)ans.push_back(num[i]);
for(int i=0;i<pos;i++)ans.push_back(num[i]);
return ans;
}
};姊妹题
Contest - 2018全校C语言程序设计作业6 http://oj.acm.zstu.edu.cn/JudgeOnline/contest.php?cid=4267 1.有16个球，其中白球5个，黑球4个，蓝球7个，如果从其中无返回任意取出10个球，请编写一个程序计算出3种颜色球都有的情况下有多少种颜色搭配,并输出每一种颜色搭配。 2.有n个阀门，编号为1到n，每一个阀门有一个按钮，每按下一次按钮，对应的阀门将会变化状态（如果阀门关闭则会开启，如果阀门开启则会关闭）。目前，这些阀门都是关闭的。这时，有第一个人按下全部的按钮,第二个人按下所有编号为2的倍数的按钮,第三个人按下所有编号为3的倍数的按钮....,一共有K个人，请问最后有哪些阀门是开着的?输入n和k，输出开着的阀门的编号。 示例输入输出： 7 3 1 5 6 7 3.输入一个正整数n，产生一个旋涡方阵。 示例输入输出： 4 10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4 4.某市筹划从一个矩形地区建造一个正方形广场。但是矩形地区内有许多钉子户，我们用“1”表示。能够建造广场的地方我们用“0”表示。整个地图由用户输入，设计一个算法计算出广场可以建设的最大面积。 示例输入输出： 请输入区域的长和宽： 5 6 请输入0-1矩阵: 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 最大的广场面积:9 5.设计一种0-1码，它有如下特征：使用二进制表示，每两个相邻的数之间只有一个位的值不同，同时最后一个数与第一个数之间也只有一个位的值不同。如三位：0 0 0，0 0 1，0 1 1，0 1 0，1 1 0，1 1 1，1 0 1，1 0 0 编写代码，展示n位的所有0-1码。 示例输入输出： 输入位数： 4 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0