镜像反转重新定义动态规划转移方程--格雷编码｜Java 刷题打卡

一、题目描述

======

89. 格雷编码

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。 格雷编码序列必须以 0 开头。 示例 1: 输入: 2 输出: [0,1,3,2] 解释: 00 - 0 01 - 1 11 - 3 10 - 2 对于给定的 n，其格雷编码序列并不唯一。 例如，[0,2,3,1] 也是一个有效的格雷编码序列。 00 - 0 10 - 2 11 - 3 01 - 1 示例 2: 输入: 0 输出: [0] 解释: 我们定义格雷编码序列必须以 0 开头。 给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。 因此，当 n = 0 时，其格雷编码序列为 [0]。

二、思路分析

======

• 我将已一下集中思路讲解自己解决问题的全部思路。中间有的思路并无法解决问题。但是对自己最终解决是一种促进作用。

公式法

• 首先编码中只能出现0、1 两个数字。两个数字出现的次数没有限制，位置也没有限制 。然后是在给定的长度限制中对两个数字进行排列组合
• 对！笔者这里首先想到的就是通过公式方式解决。
• 首先格雷编码位数是n ,内部就会有n块用来存放元素，0或者1。那么在所有的可能中我们可以理解成0出现的次数范围在0~n中。因为只有0和1所以0出现的次数相对的就是1
• 那么我们就可以将所有可能列举出来

Gn0+Cn1+Cn2+⋯+Cn1G_{n}^{0}+C_{n}^{1}+C_{n}^{2}+\cdots+C_{n}^{1}Gn0+Cn1+Cn2+⋯+Cn1

• 而上述的公式我们在学习数学的时候都知道他就是2^n-1
• 公式虽然简单，但是到这里我只能得到结果的数量。而无法获取到真实的结果集。所以这种方法无法进行到底

规律巧解

• 虽然上面的公式法无法彻底解决问题，但是至少我们知道我们最终结果长度是多少了。这至少也是有点帮助的。
• 上面总结出来的个数恰好就是二进制中数据的一次排列。
• 二进制数据从小到大排列。相邻两个数据差是1 。

动态规划

• 上面的规律我们可以理解成是动态规划的转移方程。且经过上一步我们也能够确定初始值是0.在经过第一步我们能够确定转移的范围。
• 已经收集到了那么多的条件了。那么剩下的我们就是动态规划中最后一步。从小到大执行就可以了

三、AC 代码

=======

public List<Integer> grayCode(int n) {
    Double pow = Math.pow(2, n);
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < pow.intValue(); i++) {
        list.add(i);
    }
    return list;
}

• 不知道是不是题目没有理解清楚，出现了验证不通过

重新审题

====

• 在该系统中，两个连续的数值仅有一个位数的差异 。 就是因为这句话导致我们上面的分析出现偏差。两个连续的数值中只有一位上存在差异
• 像上面哪种情况就是符合要求的。而我们上面分析的数据是递增的。就会出现这样的数字01 、10 。 这样的编码就不符合要求。因为两个数字的每一位都不相同。
• 我们刚开始的时候是空的，当扩展到1位的时候就会出现0、1两个结果 。为了方便看出效果我们下面演示从1到2位的情况
• 对n=1的结果集进行在前面补0 。 这里读者好好理解下，不管是先补0还是在前面补都没有影响。因为本身就是对称的
• 补完0之后，就会在前面进行补1 。而0 和1 本身就不同。所以紧接的后面应该是1 如图
• 最终我们补全之后是这样的
• 这个就和我们之前的一篇滚雪球的文章一样了。只不过在扩展的地方需要进行镜像反转的操作
• 还有一点我们需要知道在补零的时候翻译成十进制其实数据大小并没有发生变化
• 所以和滚雪球一样，我们对元数据不需要进行操作只需要对镜像之后的数据进行补1操作。

public List<Integer> grayCode(int n) {
    List<Integer> list = new ArrayList<Integer>();
    list.add(0);
    for (int i = 0; i < n; i++) {
        for (int j = list.size()-1; j >=0; j--) {
            list.add((int)Math.pow(2,i) + list.get(j));
        }
    }
    return list;
}

• 后来官网上有更加效率的代码。但是逻辑都是一样的。官网的代码是通过移位来完成数据的追加的。

四、总结

====

• 身体是最关键的。这次这个乌龙还是怪自己审题不清就开始做题了。
• 虽然和之前滚雪球一样但是在扩展的时候扩展策略稍微有所不同。建议和滚雪球对比一起看哦

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！