89. Gray Code - LeetCode
2024-10-20 17:43:25
Question
Solution
思路:
n = 0 0
n = 1 0 1
n = 2 00 01 10 11
n = 3 000 001 010 011 100 101 110 111
Java实现:
public List<Integer> grayCode(int n) {
List<Integer> list = new ArrayList<>();
grayCode(n, 0, list);
return list;
}
void grayCode(int n, int cur, List<Integer> list) {
if (cur == 0) {
list.add(0);
} else if (cur == 1) {
list.add(1);
} else {
int tmpSize = list.size();
for (int i = tmpSize - 1; i >= 0; i--) {
// int tmp = 1 << (cur - 1);
// System.out.println(tmp + "\t" + list.get(i) + "\t" + (list.get(i) | tmp));
list.add(list.get(i) | (1 << (cur - 1)));
}
}
if (cur < n) grayCode(n, cur + 1, list);
}
Reference
格雷码是很经典的问题,规则其实很简单,在二进制形式下,任何响铃的两个值的二进制表示形式只有一位是不同的,我们可以找找规律。
一位就是简单的:0,1
两位是:00,01,11,10
三位是:000,001,011,010,110,111,101,100
发现什么规律没有?我们把一位的两个数,前面加上0,就是二位的头两个数,前面加上1再反序,就是二位的后两个数。把二位的前面加上0,就是三位的头四个数,把二位的前面加上1再反过来,就是三位的后四个数。
也就是说,对于每多一位的格雷码,前面一半的第一位都是0,后面一半的第一位都是1,其余的位,前后两半正好是中间对称的,前面一半就是少一位的格雷码序列,后面一半时把其反序。
知道这个规律就好做了,我们可以递归来做,每次取n-1位的格雷码来做上述操作,对于一位的格雷码,直接赋值是0,1就可以了。
不过题目要求返回的是十进制数,而不是字符串,所以我们最好直接操作十进制数,这里前面加0其实就不用做什么,前面加1的话可以将1左移n-1位然后与各个数字相加即可。
注意题目说的n是非负数,所以要考虑n=0的情况,测试用例的n=0时返回的是0。
最新文章
- PO VO BO DTO POJO DAO(转)
- App开发(Android与php接口)之:短信验证码
- PAT乙级 1007. 素数对猜想 (20)
- arm-linux-gcc 常用参数讲解 gcc编译器使用方法
- ie67 设置最小宽度最小高度
- PHP学习笔记十九【析构函数】
- JAVA GUI学习 - JMenuBar菜单条、JMenu菜单、JMenuItem菜单项组件学习
- Redis基础学习(四)&mdash;Redis的持久化
- 优化php性能的一点总结
- [转载] Java集合---HashMap源码剖析
- VSCode 插件推荐
- UNIX环境高级编程——时间和日期
- Number和toString中的坑
- js 提取字符串中所有的英文
- Docker初始
- Window下Neo4j安装教程
- Fast dev didn&#39;t succeed, trying another location
- java日期工具类DateUtil-续一
- 如何使用openstack OCL
- bzoj 3052 树上莫队 待修改
热门文章
- 使用Webpack+Gulp开发运行于Dcloud平台HTML5+引擎的混合APP项目经验分享
- ES6-11学习笔记--Map
- leetcode1753. 移除石子的最大得分
- c++对c的拓展_增强
- 学习Java必用的9个网站,最后一个最好用!
- Kubernetes架构-图解
- 阿里云-部署-服务-Docker
- Redis 未授权访问漏洞【原理扫描】修复方法
- /dev/dm-0 ....(/dev/mapper机制)
- Java学习day14