循环码排列Java
文章发布较早,内容可能过时,阅读注意甄别。
# 题目
给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p,并且满足:
- p[0] = start
- p[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
# 思路
List<List
# 解法
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<Integer> circularPermutation(int n, int start) {
int[] used = new int[1<<n];
used[start] = 1;
path.add(start);
backtrack(used, n, start);
return res.get(0);
}
public void backtrack(int[] used, int n, int start) {
if(!res.isEmpty()) return;
if(path.size() == used.length) {
res.add(new ArrayList<>(path));
return;
}
for(int i = 0; i < n; i++) {
int option = start ^ (1 << i);
if(used[option] == 0) {
used[option] = 1;
path.add(option);
backtrack(used, n, option);
used[option] = 0;
path.remove(path.size() - 1);
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 总结
- 分析出几种情况,然后分别对各个情况实现