美文网首页
LeetCode 1-bit and 2-bit Charact

LeetCode 1-bit and 2-bit Charact

作者: codingcyx | 来源:发表于2018-04-19 21:25 被阅读0次

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

    解法一(普通):

        bool isOneBitCharacter(vector<int>& bits) {
            int n = bits.size();
            if(n == 1) return true;
            if(bits[n-2] == 0) return true;
            if(n == 2 || (n>=3 && bits[n-3] == 0))
                return false;
            //how many '1' continuous
            int i = n-2;
            while(i>=0 && bits[i] == 1) 
                i--;
            if((n-2-i) % 2 == 0) return true;
            else return false;
        }
    

    解法二(高端):

        bool isOneBitCharacter(vector<int>& bits) {
            int i = 0, n = bits.size();
            while(i < n-1){
                if(bits[i] == 0) i++;
                else i += 2;
            }
            return i == n-1;
        }
    

    看到0后移一个,看到1后移两个。

    相关文章

      网友评论

          本文标题:LeetCode 1-bit and 2-bit Charact

          本文链接:https://www.haomeiwen.com/subject/rjugkftx.html