89. 格雷编码
- 题目
- 数学公式
- 动态规划
- 回溯
题目
传送门：https://leetcode.cn/problems/gray-code/
数学公式
int gray(int n) { // 计算第n位格雷码公式
return n ^ (n >> 1);
}然后你写一个for循环，计算从1到n的所有格雷码，添加到答案数组。
动态规划
算例给了 n=2 的解，有了 n = 2 的解，推导怎么得到 n = 3 的解。
n = 2，值范围是 0-3
n = 3，值范围是 0-7
差了一个 2²（4）
4 的二进制是 100
n = 2 算例答案：00 01 11 10（0-1-3-2）
换成n=3范围，都加上 100
变成 100 101 111 110（4-5-7-6）
000 001 011 010
（0-1-3-2）
100 101 111 110
（4-5-7-6）
每个序列都保证了相邻数的二进制一位不同
我们现在把俩个序列拼接，就是 n = 3 的格雷码
序列是符合要求的，唯一不同就是拼接地方不同，序列1最后010和序列2开头100有俩位不同
只变化1位就是倒序拼接，因为2和6不同就是加了4，二进制上也就是多了一个1（第1位加1）
n=4,5,6 原问题 = n-1的子问题 + 2^(n-1) + 倒序拼接
回溯
回溯思路，你看这链接的图。