1 题目
An n-bit gray code sequence is a sequence of 2n integers where:
- Every integer is in the inclusive range
[0, 2n - 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.
Example 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
Example 2: Input: n = 1 Output: [0,1]
Constraints:
1 <= n <= 16
2 解答
咦，首先这个题做之前得先看看什么是格雷码：https://baike.baidu.com/item/%E6%A0%BC%E9%9B%B7%E7%A0%81/6510858
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。
public class Solution { /** * @param n: a number * @return: Gray code */ public List<Integer> grayCode(int n) { // write your code here // 定义返回结果 List<Integer> res = new ArrayList<>(); res.add(0); // 如果 n == 0,直接返回 if (n == 0) { return res; } res.add(1); for (int i = 1; i < n; i++){ // 逆序取，每个取出来然后跟1左移i位进行或运算 int len = res.size(); for (int j = len - 1; j >= 0; j--) { res.add(1 << i | res.get(j)); } } return res; } }
加油。