一、题目描述
======
格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 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
两个数字。两个数字出现的次数没有限制,位置也没有限制 。然后是在给定的长度限制中对两个数字进行排列组合Gn0+Cn1+Cn2+⋯+Cn1G_{n}^{0}+C_{n}^{1}+C_{n}^{2}+\cdots+C_{n}^{1}Gn0+Cn1+Cn2+⋯+Cn1
2^n-1
规律巧解
动态规划
三、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
。 这样的编码就不符合要求。因为两个数字的每一位都不相同。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腾讯技术创作特训营第三期有奖征文,组队打卡瓜分大奖!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。