刷题之旅从数组类型的题目开始。第三十三道题目是1比特与2比特字符，对应leetcode的题号为717。

image

题目描述

有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。

现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

示例 1:

1
2
3
4
5
输入: 
bits = [1, 0, 0]
输出: True
解释: 
唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。

示例 2:

1
2
3
4
5
输入: 
bits = [1, 1, 1, 0]
输出: False
解释: 
唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。

注意:

  • 1 <= len(bits) <= 1000.
  • bits[i] 总是0 或 1.

解题思路

分析一下题目，0可以用一比特来表示，10或11可以用两比特来表示。某个数组元素总为1或0，以[1,0,0]为例，1不能单独作为一个比特，必须跟0或1结合才行，那么10才符合条件，那么还剩一个0，这个0用一比特表示，那么这个数组就符合条件，因为题目要求最后一个字符为一比特字符。

比如[1,1,1,0]，这个就不符合，为什么呢？因为同理，第一个1必须结合0或1才行，此时11为两比特，那么前两个1已经被占用，这个时候用第三个1，同理，10才行，那么此时11和10全部用完，说明最后一个0不能作为一比特来用了。

所以这道题目理解的关键就是，数组从前往后，遇到1就要占两位，遇到0就占一位。按照上面的规则一直判断，如果最后还能胜一个0说明符合条件，如果最后不剩了，那么就不符合条件。那么就是判断咯，1则加2，0则加1，理解了这个思想后，就可以写代码了，注意判断count的结束条件，不是判断到最后一位，而是倒数第二位。时间复杂度为O(N)，空间复杂度为O(1)。

提交代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int count = 0;
        // 判断到最后一个元素之前即可，注意边界，不能判断到最后一个，最后一个元素没有意义，还会导致程序判断有误
        while(count < bits.length-1){
            // 如果开头是0.那么这一位必定是用一比特来表示
            if(bits[count] == 0){
                count += 1;
            // 如果开头是1，那么这一位必定是两比特
            }else if(bits[count] == 1){
                count += 2;
            }
        }
        // 计数结束
        // 此时如果索引等于最后一个元素，说明还剩最后一位，结合题意最后一位必为0，那么此时必定符合条件
        // 比如1，0，0，那么此时count=3-1=2，符合条件
        // 如果直接已经到数组的最后一位的后面，说明倒数第二位为1，此时最后两个数字结合成了两比特，不符合条件
        // 比如1，1，1，0.此时count=4-1!=4，不符合条件
        return count == bits.length-1 ? true : false;
    }
}