原题链接:
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;
}
}
分享到:
相关推荐
javascript js_leetcode题解之89-gray-code.js
python python_leetcode题解之089_Gray_Code
- **2.1.19 Gray Code** - 生成格雷编码序列。 - 实现思路:基于位运算的规律。 - **2.1.20 Set Matrix Zeroes** - 给定一个m x n的矩阵,如果某个元素为0,则将其所在行和列的所有元素设为0。 - 实现思路:...
c语言基础 c语言_leetcode题解之0089_gray_code.zip
Gray code/ Circular To do 加入Google Test, 学习并掌握test driven development 的工作模式 Solution 使用visual studio code 写C++ 怎么样才能正确地引用其他文件的函数 答(ref:): 因为g++不会正确的编译其他的...
java java_leetcode题解之Gray Code.java
颜色分类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/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![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题中,通过...