LeetCode717. 1-bit and 2-bit Characters 解题

墨蓝 2022-06-05 02:47 150阅读 0赞

大家好，我又很不要脸的回来了，之前大创结题所以全部心思都放到大创里头了，今天刚交完结题材料，马上就来写LeetCode。之前说十一月中要把array的所有简单题刷完，现在看来真是啪啪啪地打脸，疼。  
废话不多说，先来看题目

# 看一下题目 #

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.

> 题目的大概意思是，给定一个数组，里面都是0或者1，它们按照某种方式编码成字符，它们的编码方式只有三种形式：0，10，11，而且这个数组最后一个元素是0，要求你判断这个数组的最后一个字符是0结尾或者是10，11结尾。
> 
> Example 1:  
> 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:  
> 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.

# 解题思路 #

看上去只要判断最后的两三位就可以了，但是既然给了一整个数组，肯定不会这么轻易就让你完成这道题的。我的方法是从头开始遍历这个数组，维护一个int bitA ,用来保存当前这个是不是1，如果是1，那它后面的一位就不用判断了，这两个肯定是组成一个字符的，跳过后一个继续，当前这个位是0，那它肯定是单独编码成字符的，直到最后一位字符，判断它是作为bitA，还是bitA后需要跳过的那个元素。  
这里采用的思想是确保前面的元素都已经被确定分成两个一组或者一个一组了，最后的那个才能分得清是否单独分成一组。

# 代码 #

using namespace std;  
class Solution \{  
public:  
bool isOneBitCharacter(vector& bits) \{  
int index = 0;  
int bitA = -1;

if (bits.size() == 1) {
            return true;
        }
        if (bits[bits.size() - 2] == 0) {//end with 00
            return true;
        }
        else {//end with 10
            if (bits.size() == 2)//bits are exactly 10
                return false;
            for (index = 0; index<bits.size(); index++) {
                bitA = bits[index];
                if (bitA == 1) {
                    index += 1;
                    if (index == bits.size()-1)
                        return false;
                    bitA = -1;
                    continue;
                }
                //bitA==0
                if (index == bits.size()-1)
                    return true;
                bitA = -1;
            }
        }
    }

\};

# 更好的算法 #

一时间还看不太懂，先贴上，我感觉这是经过统计发现一定的规律之后得出的算法。  
class Solution \{  
public:  
bool isOneBitCharacter(vector& bits) \{  
const int kL = bits.size()-1;  
int i = 0;  
while (i < kL) \{  
i += bits\[i\] + 1;  
\}  
return (i == kL) && (bits\[i\] == 0);  
\}  
\};