脚本宝典收集整理的这篇文章主要介绍了LeetCode 89: GrayCode (Java),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
GrayCode:给定位数n,按规律生成一组二进制代码,直接上例子。
1位的格雷码就是0,1。
2位的格雷码是在1位的格雷码前面加0或1。
由上图可以发现,2位的格雷码后一位是镜像对称;3位的格雷码后2位是镜像对称;4位的格雷码后3位是镜像对称。
规律就是n为格雷码是在n-1位格雷码的基础上,先将n-1位镜像对称然后前一半首位添0,后一般首位添1而得到。
如果要输出n位的格雷码就得先生成n-1位格雷码,这样自然会想到回溯的方法来编程。
具体实现要先考虑基本的case,也就是n=1的情况,应该先在list中添加0,1两个数,之后n=2的时候倒着读加上1。
public List<Integer> grayCode(int n) { if(n == 0){ List<Integer> res = new ArrayList<>(); res.add(0); return res; } List<Integer> res = grayCode(n-1); int originSize = res.size(); int addN = 1 << (n-1); for(int i = originSize-1;i>=0;i--) res.add(addN+res.get(i)); return res; }
Ref: 百度百科:格雷码
以上是脚本宝典为你收集整理的LeetCode 89: GrayCode (Java)全部内容,希望文章能够帮你解决LeetCode 89: GrayCode (Java)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。