原题链接:
https://leetcode.com/problems/gray-code/
[分析] 这题更像是找规律,n = 1时是 0, 1, n = 2时是00,01, 11, 10,后面两项可以看做是先对 0,1镜像得到1,0,然后分别加上10得到11,10, 因此可以从 i = 1时迭代求得 i = n的结果。Method2 是对 Method1的代码优化,空间使用率更高的同时时间效率也提升了(不需要每次都clone)。
public class Solution {
// Method 2
public List<Integer> grayCode(int n) {
if (n < 0)
return new ArrayList<Integer>();
List<Integer> seed = new ArrayList<Integer>(1 << n);
seed.add(0);
if (n == 0)
return seed;
seed.add(1);
int lastSize = 2;
for (int i = 1; i < n; i++) {
int largeHalfBase = 1 << i;
for (int j = lastSize - 1; j >= 0; j--)
seed.add(largeHalfBase + seed.get(j));
lastSize = seed.size();
}
return seed;
}
// Method 1
public List<Integer> grayCode1(int n) {
if (n < 0)
return new ArrayList<Integer>();
List<Integer> seed = new ArrayList<Integer>(1 << n);
seed.add(0);
if (n == 0)
return seed;
seed.add(1);
ArrayList<Integer> seed2 = new ArrayList<Integer>(1<<n);
for (int i = 1; i < n; i++) {
seed2.clear();
seed2.addAll(seed);
int largeHalfBase = 1 << i;
for (int j = seed.size() - 1; j >= 0; j--)
seed2.add(largeHalfBase + seed.get(j));
seed = (ArrayList<Integer>) seed2.clone();
}
return seed;
}
}
分享到:
相关推荐
标题中的"0089_gray_code"指的是leetCode平台上的一道特定题目,这道题目的名称为"Gray Code",在数学和计算机科学中,格雷码(Gray Code)是一种二进制数码系统,在这种系统中,两个连续数值的二进制表示仅有一位二...
- **2.1.19 Gray Code** - 生成格雷编码序列。 - 实现思路:基于位运算的规律。 - **2.1.20 Set Matrix Zeroes** - 给定一个m x n的矩阵,如果某个元素为0,则将其所在行和列的所有元素设为0。 - 实现思路:...
在编程和算法领域,生成Gray Code的一个常见问题是在LeetCode上的一个题目。编号为089的这个问题要求参与者编写一个算法来产生n位的格雷码序列。一个有效的格雷码序列需要满足每个数都是序列中一个数的格雷码,并且...
在这段代码中,`grayCode`方法接收一个整数n,表示生成的Gray Code序列的位数。方法内部使用了一个for循环,循环次数为`1 ,即2的n次方,这样可以保证生成所有可能的Gray Code。在循环体内部,我们利用了位运算技巧...
本文讲解的是在LeetCode上编号为89的问题——Gray Code(格雷码)的JavaScript解法。Gray Code问题是要求编写一个函数,该函数能够生成n位的格雷码。生成格雷码是一个涉及到位操作的算法问题,可以有多种解决方式,...
Gray code/ Circular To do 加入Google Test, 学习并掌握test driven development 的工作模式 Solution 使用visual studio code 写C++ 怎么样才能正确地引用其他文件的函数 答(ref:): 因为g++不会正确的编译其他的...
颜色分类leetcode 格雷码结构光重建 使用投影仪和相机重建 3D 场景 这个 repo 使用投影仪和相机来扫描场景并创建 3D 模型。 为了实现这一点,结构光图案被投射到场景上。 这是用相机捕获以确定密集对应关系。 该存储...
解法一:循环生成数组结果,倒序遍历已有的格雷码加上偏移量即可扩充格雷码位数vector<int> grayCode(int n) {执行结果:执行用时 : 4
gray code 二分查找 序列号 题目名称 题目难点 162 树的问题 序列号 题目名称 题目难点 297 leet code 序列号 题目名称 题目难点 33 搜索旋转排序数组 要求O(logN),同时数组是个旋转数组 34 在排序数组中查找元素的...
# [LeetCode](https://leetcode.com/problemset/algorithms/)  [![License]...
gas station leetcode leetcode 为了更好地检索以及归纳 *只是leetcode的会员题,没什么特殊含义。。 [] [BFS] [Two Pointer] [快慢] Prefix [89. Gray Code] [奇技淫巧]
#Gray code 12/29/2015 今天我将用两种解决方案来解决格雷码问题。 一个是preve bit '1',另一个是DFS。 力码 下面是我对 LeetCode 问题的解决方案的总结。 每个问题的主要思想通常可以在相应源文件的开头找到。 我...
233 Gray Code 565 234 Permutations 567 235 Permutations II 571 236 Permutation Sequence 573 237 Generate Parentheses 575 238 Combination Sum 577 239 Combination Sum II 579 240 Combination Sum III 581 ...
另一种方法是使用位操作,如上述 `Solution` 类中的 `grayCode` 函数所示。这个函数首先创建一个长度为 \(2^n\) 的数组 `ans` 并初始化为全 0,然后遍历从 1 到 \(2^n - 1\) 的所有整数。对于每个 i,将 i 右移一位...
格雷编码(Gray Code),又称格雷码或格雷二进制码,是一种特殊的二进制数字系统。在格雷编码中,两个连续的数值之间仅有一位数字不同,这使得它在数据传输、编码设计以及计算机科学的多个领域中有广泛应用。本篇...
格雷编码(Gray Code),又称格雷码或反射码,是一种二进制数字系统,它的特点是任意两个相邻的数值之间只有一个位元的差异。这种编码方式在数据传输、编码电路设计以及计算机科学的多个领域都有广泛的应用,因为它...
转换二进制到格雷码可以用公式`GrayCode = Binary ^ (Binary >> 1)`,而格雷码到二进制可以通过逐位比较并递归计算。例如,Q89题就涉及到了格雷编码的转换。 此外,数论还涉及到一些实用技巧,如在Q136题中,通过...