格雷码
看到题目就想到了格雷码 然后就疯狂搜索格雷码 手动构造了一波格雷码 看了题解 emmm 有点亏
理论基础
- n 位格雷码序列 是一个由
2n个整数组成的序列，其中： - 每个整数都在范围
[0, 2n - 1]内（含0和2n - 1） - 第一个整数是
0 - 一个整数在序列中出现 不超过一次
- 每对 相邻 整数的二进制表示 恰好一位不同 ，且
- 第一个 和 最后一个 整数的二进制表示 恰好一位不同
- 三位二进制数的格雷码序列为
000,001,011,010,110,111,101,100
从全0 格雷码开始，按照下面策略：
1.翻转最低位得到下一个格雷码;
2.把最右边的1的左边的位翻转得到下一个格雷码；
交替按照上述策略生成2 k − 1 次，可得到k kk位的格雷码序列
相关题目
格雷编码【LC89】
n 位格雷码序列 是一个由
2n个整数组成的序列，其中：
- 每个整数都在范围
[0, 2n - 1]内（含0和2n - 1）- 第一个整数是
0
- 一个整数在序列中出现 不超过一次
- 每对 相邻 整数的二进制表示 恰好一位不同 ，且
- 第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数
n，返回任一有效的 n 位格雷码序列 。
手动构造
- 思路：交替手动构造
从全0 格雷码开始，按照下面策略：
翻转最低位得到下一个格雷码;
把最右边的1 的左边的位翻转得到下一个格雷码；
交替按照上述策略生成2 k − 1次，可得到k kk位的格雷码序列
实现
class Solution { public List<Integer> grayCode(int n) { List<Integer> res = new ArrayList<>(); int len = 1 << n; res.add(0); for (int i = 1; i < len; i++){ // 交替构造 if ((i & 1) == 1){ // 反转最低位 res.add(reverseIth(res.get(i - 1), 0)); }else{ int j = 0, pre = res.get(i - 1); while (((pre >> j) & 1) == 0){ j++; } // 反转最右边的1的左边的那位 res.add(reverseIth(res.get(i - 1), j + 1)); } } return res; } // 反转右边数第i位 public int reverseIth(int num, int i){ if (((num >> i) & 1) == 0){ return num | (1 << i );// 设为1 }else{ return num & (~(1 << i));// 设为0 } } }
复杂度分析
- 时间复杂度：O ( 2 n )
空间复杂度：O ( 1 )
镜像构造
- 思路：
class Solution { public List<Integer> grayCode(int n) { List<Integer> res = new ArrayList<>(); res.add(0); for (int i = 0; i < n; i++){ int m = res.size(); for (int j = m - 1; j >= 0; j--){ res.add(res.get(j) | (1 << i)); } } return res; } }
class Solution { public List<Integer> grayCode(int n) { List<Integer> res = new ArrayList<>(); for (int i = 0; i < 1 << n; i++){ res.add(i ^ (i / 2)); } return res; } }
复杂度分析
时间复杂度：
空间复杂度：
循环码排列【LC1238】
给你两个整数
n和start。你的任务是返回任意(0,1,2,,...,2^n-1)的排列p，并且满足：
p[0] = start
p[i]和p[i+1]的二进制表示形式只有一位不同p[0]和p[2^n -1]的二进制表示形式也只有一位不同
先构造再添加
- 思路：
根据题意相邻二进制只有一位不相同，那么可以想到格雷码。可以将start看作某个格雷码的二进制形式，然后可以先按照题格雷编码【LC89】先从0开始构造出n 位的格雷码，在构造过程中记录与start相等的格雷码下标i n d e x。最后再从i n d e x 遍历一次格雷码数组，将结果添加到结果集中。
- 实现
class Solution { public List<Integer> circularPermutation(int n, int start) { int len = 1 << n; int[] gray = new int[len]; List<Integer> res = new ArrayList<>(); int index = start; for (int i = 0; i < len; i++){ gray[i] = i ^ (i >> 1); if (gray[i] == start) index = i; } for (int i = index;i < index + len; i++){ res.add(gray[i % len ]); } return res; } }
异或start
思路：题格雷编码【LC89】从0开始构造出n 位的格雷码，那么我们可以在构造的每个结果上异或start，那么起始数值变为了start，又保证相邻数的二进制形式只有一位不同
class Solution { public List<Integer> circularPermutation(int n, int start) { int len = 1 << n; List<Integer> res = new ArrayList<>(); for (int i = 0; i < len; i++){ res.add(i ^ (i >> 1) ^ start); } return res; } }
