格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 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]。
原题url:https://leetcode-cn.com/problems/gray-code/
一开始拿到这题目,我想到的是从0开始,每次从右边第一位开始改变,放入结果集中(集合),如果添加成功,就以当前数为新的起点,继续变化和添加,否则就变化下一位。
这个想法看似美好,实际有两个需要解决的难点:
如何保证转化出的二进制,精确修改每一位呢?如果用 for 循环的话,效率很低。
每次这样改变的话,很可能效率会很低,时间复杂度会很高,如何优化?
基于以上两点,我稍微尝试了一下,感觉这个方法不靠谱,决定换一个思路。
那现在我就来尝试找找规律,自己写写0位、1位、2位、3位的格雷编码:
0位: 0 1位: 0 1 2位: 00 01 11 10 3位: 000 001 011 010 110 111 101 100
写完之后,应该能找到以下几个规律:
第 n 位格雷编码是第 n+1 位格雷编码的子集,意味着可以利用上一次的结果。
根据2进制来看,每多一位,其实就是在多的那一位置1即可。
基于第2点,需要做补充,格雷编码是需要考虑顺序的,并不能只是简单置1,应该是针对上一次的结果集倒序输出并在最高位置1。
上面3个规律,只有最后一个规律,可能比较难找,不过考虑到顺序这个特性,应该也能想出来。接下来我们看一下代码:
class Solution { public List<Integer> grayCode(int n) { // 动态规划,第n种情况是由:第n-1种正序各数字前加0 + 第n-1种倒序各数字前加1 // 先给出一开始的情况 LinkedList<Integer> list = new LinkedList<>(); list.add(0); if (n == 0) { return list; } LinkedList<Integer> result = new LinkedList<>(); result.add(0); // 最高位置1,可以理解为增加 int add = 1; for (int i = 1; i <= n; i++) { // 倒序 Collections.reverse(list); for (int item : list) { result.add(item + add); } list = new LinkedList<>(result); add = add << 1; } return result; } }
提交OK,执行用时: 3 ms
,内存消耗: 34.5 MB
,但是用时只战胜 9.59%
的 java 提交记录,看来还是有优化必要的。
我第一眼想到的优化是 倒序
,我并不需要真的将上一次的结果集真的倒置,而是只要倒序遍历即可。因为我存放的结果集是 LinkedList,可以利用它的 descendingIterator
,直接进行倒序遍历,其代码是:
class Solution { public List<Integer> grayCode(int n) { // 动态规划,第n种情况是由:第n-1种正序各数字前加0 + 第n-1种倒序各数字前加1 // 先给出一开始的情况 LinkedList<Integer> list = new LinkedList<>(); list.add(0); if (n == 0) { return list; } LinkedList<Integer> result = new LinkedList<>(); result.add(0); int add = 1; for (int i = 1; i <= n; i++) { // 倒序 Iterator<Integer> descIterator = list.descendingIterator(); while (descIterator.hasNext()) { result.add(descIterator.next() + add); } list = new LinkedList<>(result); add = add << 1; } return result; } } `
提交OK,执行用时: 2 ms
,内存消耗: 34.3 MB
,但是用时只战胜 21.07%
的 java 提交记录,看来还可以继续优化。
这次我盯上的是 list = new LinkedList<>(result);
,看起来是1行代码,实际内部利用了 addAll
方法,还是需要遍历这个结果集。而这里需要定义一个新的结果集是为了记录中间结果,是否真的有必要的呢?
如果还是利用 LinkedList 结构,还真就需要新建结果集。因为它想获取中间结果,用 get(int index)
这样的方法,依旧需要遍历。这时候我就想到,可以换一种数据结构 ArrayList
,这样无论是倒序遍历还是添加,都是只要记录上一次的总数量,就可以达到同样的效果了。接下来让我们看看代码:
class Solution { public List<Integer> grayCode(int n) { // 动态规划,第n种情况是由:第n-1种正序各数字前加0 + 第n-1种倒序各数字前加1 // 先给出一开始的情况 ArrayList<Integer> list = new ArrayList<>(1 << n); list.add(0); if (n == 0) { return list; } int add = 1; int tempCount; for (int i = 1; i <= n; i++) { tempCount = list.size(); // 倒序 for (int j = tempCount - 1; j >= 0; j--) { list.add(2 * tempCount - j - 1, list.get(j) + add); } add = add << 1; } return list; } }
提交OK,执行用时: 1 ms
,内存消耗: 34.2 MB
,用时战胜了 97.89%
的 java 提交记录,这下应该可以了。
以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题目的难点主要在于找规律以及之后的优化。
有兴趣的话可以访问我的博客或者关注我的公众号,说不定会有意外的惊喜。
https://death00.github.io/
公众号:健程之道
点击此处留言