[每日一题]1238.循环码排列
1238. 循环码排列 给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,…,2^n-1) 的排列 p，并且满足：
- p[0] = start
- p[i] 和 p[i+1] 的二进制表示形式只有一位不同
- p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同
输入：n = 2, start = 3 输出：[3,2,0,1] 解释：这个排列的二进制表示是 (11,10,00,01) 所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,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
Solution
class Solution {
LinkedList<Integer> ans = new LinkedList<>();
Set<Integer> set = new HashSet<>();
int n;
int start;
int num;
public List<Integer> circularPermutation(int n, int start) {
this.n = n;
this.start = start;
this.num = (int)Math.pow(2, n); // 结果列表所需要的长度;
backTracking(start);
return ans;
}
public boolean backTracking(int k) {
ans.add(k);
if (ans.size() == num) return true;
set.add(k);
for (int i = 0; i < n; ++i) {
// 每次取反k中的一位;
int a = k ^ (1 << i);
if (!set.contains(a)) {
if (backTracking(a)) return true;
}
}
ans.removeLast();
return false;
}
} //回溯