【Leetcode】89. Gray Code（规律）（二进制相邻位变换）

布满荆棘的人生 2022-02-22 10:23 142阅读 0赞

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer *n* representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

**Example 1:**

Input: 2
    Output: [0,1,3,2]
    Explanation:
    00 - 0
    01 - 1
    11 - 3
    10 - 2
    
    For a given n, a gray code sequence may not be uniquely defined.
    For example, [0,2,3,1] is also a valid gray code sequence.
    
    00 - 0
    10 - 2
    11 - 3
    01 - 1

**Example 2:**

Input: 0
    Output: [0]
    Explanation: We define the gray code sequence to begin with 0.
                 A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
                 Therefore, for n = 0 the gray code sequence is [0].

题目大意：

二进制编码每次只能变换一个位置，从零开始，将变换之后的序列按照十进制输出。n代表有多少位。

解题思路：

![20190409102636215.png][]以两位数为例，实际上第二部分就是对第一部分从后往前多加了一个2的1次方。所以我们就可以将问题视作对vector中已存在的数加上2的n次方。

class Solution {
    public:
        vector<int> grayCode(int n) {
            vector<int > ans;
            ans.push_back(0);
            int b = 1;
            for(int i = 0;i<n;i++){
                for(int j = ans.size()-1;j>=0;j--){
                    ans.push_back(ans[j]+b);
                }
                b <<= 1;
            }
            return ans;
        }
    };

[20190409102636215.png]: /images/20220222/bfaa4c900040459f9ffa6e97cb3fa9cc.png

发表评论取消回复

表情：

评论列表（有 0 条评论，142人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode89/60 Gray Code/Permutation Sequence--迭代

一：Leetcode 89 [Gray Code][] 题目：The gray code is a binary numeral system where two succe

悠悠/ 2022年08月07日 16:40/ 0 赞/ 113 阅读

相关 Leetcode: Gray Code

题目： The gray code is a binary numeral system where two successive values differ in onl

古城微笑少年丶/ 2022年08月07日 12:56/ 0 赞/ 32 阅读

相关 LeetCode-Gray Code

The gray code is a binary numeral system where two successive values differ in only one

悠悠/ 2022年08月04日 09:19/ 0 赞/ 62 阅读

相关 leetcode 89. Gray Code

The gray code is a binary numeral system where two successive values differ in only one

淩亂°似流年/ 2022年07月30日 13:15/ 0 赞/ 170 阅读

相关【LeetCode】89. Gray Code解法及注释

89. Gray Code Total Accepted: 58433 Total Submissions: 161645 Difficulty: Medium Th

蔚落/ 2022年07月27日 11:50/ 0 赞/ 169 阅读

相关 [leetcode]89. Gray Code

The gray code is a binary numeral system where two successive values differ in only one

电玩女神/ 2022年07月24日 07:28/ 0 赞/ 127 阅读

相关 [leetcode]89. Gray Code -- JavaScript 代码

/ @param {number} n @return {number[]} / var grayCode = function(n) {

以你之姓@/ 2022年07月18日 06:14/ 0 赞/ 18 阅读

相关 LeetCode 89.Gray Code （格雷编码）

题目描述：格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0

ゞ浴缸里的玫瑰/ 2022年05月10日 10:16/ 0 赞/ 191 阅读

相关【Leetcode】89. Gray Code（规律）（二进制相邻位变换）

The gray code is a binary numeral system where two successive values differ in only one

布满荆棘的人生/ 2022年02月22日 10:23/ 0 赞/ 143 阅读

相关 [转载]LeetCode: Gray Code

The gray code is a binary numeral system where two successive values differ in only one

亦凉/ 2021年09月17日 16:48/ 0 赞/ 164 阅读