89. Gray Code

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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:

1
2
3
4
5
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].

Explanation:

  1. 由已经有的生成还没有的: xx | 1 << i. | is OR.
  2. 为什么内部的for循环需要倒过来? 因为这样保证chunk之间衔接的两个边界元素也是differ by one
  3. 然后右移一位1<<i得到下一部分.
Solution1

由已有的sequence生成后续的sequence;

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new LinkedList<>();
        res.add(0);
        for (int i = 0; i < n; ++i) {
            int size = res.size();
            for (int j = size -1; j >= 0; --j) {
                res.add(res.get(j) | 1<<i );
            }
        }
        return res;
    }
}

Solution2

Or: i ^ i/2, or i ^ i >> 1; ^ is XOR.

1
2
3
4
5
6
7
8
9
class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new LinkedList<>();
        for (int i = 0; i < 1 << n; ++i) {
            res.add(i ^ i >> 1);
        }
        return res;
    }
}

…
(此处应有👏)

骚不骚? G(i) = i ^ (i >> 1).

717. 1-bit and 2-bit Characters

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

Example 1:

1
2
3
4
5
Input: 
bits = [1, 0, 0]
Output: True
Explanation: 
The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.

Example 2:

1
2
3
4
5
Input: 
bits = [1, 1, 1, 0]
Output: False
Explanation: 
The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character.

Note:

  1. 1 <= len(bits) <= 1000.
  2. bits[i] is always 0 or 1.

Explanation

可以从前往后遍历, 如果是1那么这个part对应的肯定是2-bit, i+=2; 经过前面这样如果还能碰到0那么这个part肯定是1-bit, 那么++i; 遍历终止条件是到倒数第二位，那么如果是满足的那么跳出来是刚好在最后一位,否则不满足;

Solution 1
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int n = bits.length;
        int i = 0;
        while (i < n - 1) {
            if (bits[i] == 1) i += 2;
            else i += 1;
        }
        return i == n-1;
    }
}
Solution 2

而实际上可以优化: 并不需要遍历整个数组；可以只遍历最后面需要了解的地方

从倒数第二位开始后往前遍历看连续的1的数量; 如果是偶数个1那么所有的1都有配对，那么最后一个0就是单着的，可以；如果是奇数个连续的1那么最后一个0就跟前面一个1配对，就不行;

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int ones = 0;
        for (int i = bits.length - 2; i >= 0 && bits[i] == 1; --i) {
            ones++;
        }
        if (ones % 2 == 0) return true;
        return false;
    }
}