LeetCode刷题笔记-贪心法-格雷编码

时间:2022-03-06 08:20:05

题目描述:

格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n,打印其格雷编码序列。格雷编码序列必须以 0 开头。

来源:力扣(LeetCode)
链接: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;

LeetCode刷题笔记-贪心法-格雷编码

  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;
}