中国建设银行门户网站企业,长沙网站开发智能,做一个公司官网,重庆网页制作工作室89. 格雷编码题目数学公式动态规划回溯题目
传送门#xff1a;https://leetcode.cn/problems/gray-code/ 数学公式
int gray(int n) { // 计算第n位格雷码公式return n ^ (n 1);
}然后你写一个for循环#xff0c;计算从1到n的所有格雷码#xff0c;添加到答… 89. 格雷编码题目数学公式动态规划回溯 题目
传送门https://leetcode.cn/problems/gray-code/ 数学公式
int gray(int n) { // 计算第n位格雷码公式return n ^ (n 1);
}然后你写一个for循环计算从1到n的所有格雷码添加到答案数组。 动态规划
算例给了 n2 的解有了 n 2 的解推导怎么得到 n 3 的解。
n 2值范围是 0-3
n 3值范围是 0-7
差了一个 2²4
4 的二进制是 100
n 2 算例答案00 01 11 100-1-3-2
换成n3范围都加上 100
变成 100 101 111 1104-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
n4,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/
