1-Bit And 2-Bit Characters Problem


Description

LeetCode Problem 717.

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).

Given a binary array bits that ends with 0, return true if the last character must be a one-bit character.

Example 1:

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

Constraints:

  • 1 <= bits.length <= 1000
  • bits[i] is either 0 or 1.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
    	// The numbers of 1 between the last 0 and the second last 0 determine the answer.
        // If the number is odd, the answer is false.
        // If the number is even, the answer is true.
        int count_1 = 0;
        for (int i = (int) bits.size() - 2; i >= 0 && bits[i] == 1; i--) 
            count_1 ++;
        return (count_1 % 2 == 0);
    }
};




Related Posts

Walking Robot Simulation Problem

LeetCode 874. A robot on an infinite XY-plane starts at...

Valid Mountain Array Problem

LeetCode 941. Given an array of integers arr, return true...

Sum Of Even Numbers After Queries Problem

LeetCode 985. You are given an integer array nums and...

Partition Array Into Disjoint Intervals Problem

LeetCode 915. Given an integer array nums, partition it into...

Monotonic Array Problem

LeetCode 896. An array is monotonic if it is either...

Maximize Distance To Closest Person Problem

LeetCode 849. You are given an array representing a row...