返回

[Leetcode]89. Gray Code(C++)

题目描述

题目链接:89. Gray Code

An n-bit gray code sequence is a sequence of 2^n integers where:

  • Every integer is in the inclusive range [0, 2^n - 1],
  • The first integer is 0,
  • An integer appears no more than once in the sequence,
  • The binary representation of every pair of adjacent integers differs by exactly one bit, and
  • The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

例子

例子 1

Input:n = 2 Output:[0,1,3,2] Explanation: The binary representation of [0,1,3,2] is [00,01,11,10].

  • 00 and 01 differ by one bit
  • 01 and 11 differ by one bit
  • 11 and 10 differ by one bit
  • 10 and 00 differ by one bit [0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
  • 00 and 10 differ by one bit
  • 10 and 11 differ by one bit
  • 11 and 01 differ by one bit
  • 01 and 00 differ by one bit

例子 2

Input:n = 1 Output:[0,1]

Constraints

  • 1 <= n <= 16

解题思路

通过观察 n = 2 的两组可行答案和 n = 1 的答案,可以发现一个规律:

  • n = 2 的第二组的后两个元素和前两个元素(除了最高位)互为镜像,区别是后两个元素的最高位是 1,可以看成是 n = 1 的答案后面从后往前遍历,并最高位加个1形成一组答案;
  • n = 2 的第二组答案也是类似,区别是不是在最高位而是再低位加1

根据这个规律,代码如下:

#include <vector>

class Solution {
public:
    std::vector<int> grayCode(int n) {
        int num = (1 << n);
        std::vector<int> ans(num, 0);
        int current_bits = 0;
        for (int i = 1; i < num; ++i) {
            
            // mirror_line = (2 ^ current_bits) - 1, diff = (i - 2 ^ current_bits)
            int idx = (1 << current_bits) - 1 - (i - (1 << current_bits));
            ans[i] = ((1 << current_bits) | ans[idx]);
            if (i == ((1 << (current_bits + 1)) - 1)) {
                current_bits++;
            }
        }

        return ans;
    }
};
  • 时间复杂度: (2^n)
  • 空间复杂度: (2^n)

GitHub 代码同步地址: 89.GrayCode.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy