89. 格雷编码

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) + 倒序拼接

 

---

回溯

回溯思路，你看这链接的图。

• https://leetcode.cn/problems/gray-code/solution/hui-su-javadai-ma-zhu-shi-by-xiao-xiao-l-sz0r/