☆打卡算法☆LeetCode 89、格雷编码 算法解析
☆打卡算法☆LeetCode 89、格雷编码 算法解析
恬静的小魔龙
发布于 2022-08-07 10:19:35
发布于 2022-08-07 10:19:35
一、题目
1、算法题目
“给定一个整数，返回任一有效的n位格雷码序列。”
题目链接：
来源：力扣（LeetCode）
链接：89. 格雷编码 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
- 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
- 第一个整数是 0
- 一个整数在序列中出现 不超过一次
- 每对 相邻 整数的二进制表示 恰好一位不同 ，且
- 第一个 和 最后一个 整数的二进制表示 恰好一位不同 给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
示例 1：
输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同示例 2：
输入： n = 1
输出： [0,1]二、解题
1、思路分析
首先说一下格雷码，格雷码是一种典型的二进制编码，最开始是为了通信，用于模拟数字转换和位置数字转换使用，后来应用于机械计数或电路状态输入等。
对于这道题来说，如果我们已经获取到了格雷码序列，只需要对它进行翻转，那么翻转前和翻转后的尾元素应该是相同。
2、代码实现
代码参考：
class Solution {
public List<Integer> grayCode(int n) {
List<Integer> ret = new ArrayList<Integer>();
ret.add(0);
for (int i = 1; i <= n; i++) {
int m = ret.size();
for (int j = m - 1; j >= 0; j--) {
ret.add(ret.get(j) | (1 << (i - 1)));
}
}
return ret;
}
}
image.png
3、时间复杂度
时间复杂度 ： O(2n)
其中n是格雷码序列的位数。
空间复杂度： O(1)
三、总结
将格雷码序列进行翻转，追加到原有序列的尾部，此时新序列的前后两部分均为合法的格雷码。
接下来就是考虑衔接点的合法性：
- 将翻转后的每个数进行尾部加1操作，确保连接点的两个数只有一位二进制位不同
- 追加1后，首尾两个数的二进制只有一位不同
这样就保证了整个序列的合法性。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-02-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录