循环码排列

写在前面题目描述解题思考代码总结

写在前面

最近在学习STL源码，买了两本书：侯捷大大的《STL源码剖析》和他翻译的《深入探索C++对象模型》。并且实验室的工作挺忙，因此没时间刷题了。前天模拟了一场虚拟竞赛，碰到了这道题。当时觉得挺有意思的，没有写，只是想了个思路。昨天晚上我才做好这道题。

题目描述

---

给你两个整数 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 <= 16 0 <= start < 2^n

---

解题思考

我当时想出来的思路比较简单。对于这道题来说，其实题目要求的输出只是一个格雷码。例如输入n = 3的时候，格雷码为000, 001, 011, 010, 110, 111, 101, 100。格雷码的生成算法也非常直观：

$$\begin{gathered} \forall n-bitBinaryNumberB \\ B=B_1{B}_2{B}_3...B_n \\ \exists n-bitBinaryGrayCodeG \\ {G}_n=B_n\oplus B_{n+1} \\ G=G_1{G}_2{G}_3...G_n \end{gathered}$$

既然算法如此直观，那么其实下面的思路就非常简单了：

首先，根据输入n，我们生成一个从小到大的序列 a。对a中的每一个元素使用上面的算法求出格雷码，生成一个新的序列b。以a[start]为起点，循环输出整个序列b。

---

代码

#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; class Solution { public: vector<int> circularPermutation(int n, int start) { vector<int> result; for (int i = 0; i < pow(2, n); i++) { result.push_back(0); int temp = 1; for (int j = 0; j < n; j++) { int a = (i & temp) >> j; temp <<= 1; int b = (i & temp) >> (j + 1); int c = (a^b) << j; result.back() += c; } } int position = distance(result.begin(), find(result.begin(), result.end(), start)); vector<int> temp(result.begin(), result.begin() + position); result.insert(result.end(), temp.begin(), temp.end()); result.erase(result.begin(), result.begin() + position); return result; } }; int main(int argc, char const *argv[]) { int n; int start; Solution solu; cin >> n >> start; solu.circularPermutation(n, start); return 0; } /*0000 0001 0010 0011 0100 0101 0110 0111*/ /* 000 001 011 010 110 111 101 100*/

总结

没啥好总结的。我在leetcode的题解里看到有其他的解法，但是实际上也都差不多，多以就不放出来了。