题目描述:
格雷编码是一个二进制数字系统, 在该系统中, 两个连续的数值仅有一个位数的差异.
给定一个代表编码总位数的非负整数 n, 打印其格雷编码序列. 格雷编码序列必须以 0 开头.
链接: https://leetcode-cn.com/problems/gray-code
解题思路:
当 n=1 时: 0,1
当 n=2 时, 仅需对 n=1 的所有结果最高位添加 1&&& 并且逆序添加
0,1
10,11-> 逆序 11,10
最终结果 0,1,11,10;
- public List<Integer> grayCode(int n) {
- List<Integer> result= new ArrayList<>();
- result.add(0);
- // 格雷码生成和前已经添加到集合中的元素有关, 故 DP
- for(int i=0;i<n;i++){ // 从 1 位数开始算起, 二位数仅仅和 1 位数有关, 三位数和 1&2 位数都有关
- for (int j=result.size()-1;j>=0;j--){
- // 关于 1 的位运算, 相当于 2 的幂运算
- result.add((1<<i)+result.get(j)); //1<<5(1 左移 5 位) 即: 2^5
- }
- }
- return result;
- }
来源: http://www.bubuko.com/infodetail-3100623.html