题目描述：

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:

Input: bits = [1, 0, 0]Output: TrueExplanation: The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.

 

Example 2:

Input: bits = [1, 1, 1, 0]Output: FalseExplanation: 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 <= len(bits) <= 1000.
• bits[i] is always 0 or 1.

 

要完成的函数：

bool isOneBitCharacter(vector<int>& bits) 

 

说明：

1、给定一个vector，每个元素或者为1或者为0，最后一个元素必定为0，要对这个vector做编码，元素0代表一种字符，10或者11代表另一种字符，要求判断编码之后最后一个字符是不是0代表的字符。

给个例子[1,0,0]，编码为，10代表的字符和0代表的字符。所以返回true，最后一个字符是0代表的字符。

再给个例子[1,1,1,0]，编码为，11代表的字符和10代表的字符。所以返回false，最后一个字符是10代表的字符。

2、理解了题意之后，由于最后一个元素必定为0，所以判断一下倒数第二个元素是不是0，如果是0，那么必定最后一个字符是0代表的字符，如果不是，我们再做判断。

笔者觉得从前面开始数起，可能还是比较容易做的方式，所以我们构造如下代码：

bool isOneBitCharacter(vector
     
      & bits)     {        int s1=bits.size();        if(bits[s1-2]==0)//判断倒数第二个元素是否为0            return true;        int i=0;        while(i
     

上述代码思路十分直接，实测7ms，beats 51.31% of cpp submissions。

 

3、改进：

上述做法中比较浪费时间的就是else语句里面的if语句，每次都要进行判断，十分浪费时间，而实际上我们只需要让 i 走到最后的时候停下来，然后再做一次判断是不是在s1-1这个位置就好了。

这样就不用每次都做条件判断了。

代码如下：

bool isOneBitCharacter(vector
     
      & bits)     {        int s1=bits.size();        if(bits[s1-2]==0)            return true;        int i=0;        while(i
     

分析一下为什么上述代码能够成立。

如果最后一个字符是0代表的字符，那么有三种情况，如下：

s1-3	s1-2	s1-1
	0	0
1	0	0
1	1	0

 

 

 

 

最后一个字符是0代表的字符，倒数第二个字符是0代表的字符或者11和10代表的字符。

那么上述改进的代码最后都会进行最后一次循环，然后i=s1-1，退出循环。

如果最后一个字符不是0代表的字符，最后两个元素是10，那么上述代码进行完最后一次循环，i=s1，退出循环。

所以我们最后再做一次判断就可以了，判断 i 的位置。

上述代码实测6ms，beats 98.74% of cpp submissions。