原题链接:http://oj.leetcode.com/problems/gray-code/这道题要求求出n位的格雷码对应的二进制数,主要在于找到一种格雷码的递增方法(格雷码并不是唯一的,可以有多种)。我们来看看有了n-1位的格雷码如何得到n位的格雷码呢?其实方法比较简单,首先在n-1位的格雷码前面都添加0作为前2^(n-1)个格雷码,它们一定是合法的因为除了第一位(都是0)其余位都跟n-1的格雷码一致,所以两两之间只相差一位,满足要求。接下来看看如何接上剩下的2^(n-1)个,我们把n-1位的格雷码倒序排列,然后在每个前面添加1,然后接到上述的前2^(n-1)个就可以了。首先因为是倒序过来,所以中间两个元素除去第一位其他都是一样的(因为原来最后一个,现在倒序过来就是第一个),而他们第一位分别是0和1,满足格雷码的要求。而剩下的元素因为我们是n-1位的格雷码倒序排列,所以两两都是满足要求的,加上前面都一样的位1,仍然满足条件。最后看看这些数字是不是都不一样,前半部分和后半部分肯定不会一样,而因为前半部分都是0开头,后半部分都是1打头,所以互相之间也不会有重复,可以看出覆盖了所有数字,而且依次下来均满足条件。如此我们提出了格雷码的递推方法,我们只需要做一次位数的循环,每次根据上面结果构造当前位数的结果即可。算法复杂度是O(2+2^2+...+2^n-1)=O(2^n),所以是指数量级的,因为是结果数量无法避免。空间复杂度则是结果的大小,也是O(2^n)。代码如下:public ArrayList<Integer> grayCode(int n) {
ArrayList<Integer> res = new ArrayList<Integer>();
if(n<0)
return res;
if(n==0)
{
res.add(0);
return res;
}
res.add(0);
res.add(1);
for(int i=2;i<=n;i++)
{
int size = res.size();
for(int j=size-1;j>=0;j--)
{
res.add(res.get(j)+(1<<(i-1)));
}
}
return res;
}
可以看出上面代码并不需要处理前半部分,因为要求的是二进制数对应的整数,所以在前面加0等于原来的数字,所以前面数字只需要保持原来就行,后面进行倒序然后对最高位赋1即可。感觉更接近于一道寻找规律的题目,实现上用到一点位运算会比较简单,不过位运算是这道题的考察点之一,面试中还是有关于位运算的题目,需要熟悉一下哈。
分享到:
相关推荐
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
锈cauly-rust-leetcode-utils 这个项目为用 rust 语言编写 leetcode 提供了一些帮助。 如何使用 方法一: [Folk and] 克隆这个 repo。 在你的 leetcode cargo.toml 中,添加: [dependencies] cauly-rust-leetcode-...
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode题库所有数据库问题 Leetcode 所有数据库问题:Leetcode 问题 Active-Businesses-LeetCode.png 活跃用户-LeetCode.png 活动-参与者-LeetCode.png 至少合作过三次的演员和导演-LeetCode.png Ads-Performance-...
Swif-LeetCode-Utils:在LeetCode上快速创建和打印ListNode和TreeNode的方式
RandomPickWithWeight-LeetCode-528-源码.rar
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
Java-Leetcode-杨辉三角
vs code LeetCode 插件
前端大厂最新面试题-leetcode-interview-ts.docx
leetcode 答案 -leetcode- leetcode刷题指南 不只是答案 更多的是过程 更重要的是纠错的过程
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
Algorithm-LeetCode-NOTES.zip,利特码,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-js-tdd leetcode 勇士的简单样板 如何使用 克隆这个 repo 在你的 vscode 中安装 配置扩展以使用 repo 中的problems文件夹 使用1.two-sum.js案例导出解决方案 module . exports = { // ignore: true, fn : ...