给你两个整数 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
最大的广场面积:95.设计一种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
京公网安备 11010502036488号