“This is the 34th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

717. 1 bit and 2 bit characters

The title

There are two types of special characters:

  • The first character can be represented by a bit 0
  • The second type of character can be represented by two bits (10 or 11).

Given a binary array of bits ending in 0, return true if the last character must be a one-digit character.

Example 1

Input: bits = [1, 0, 0] Output: true Description: The only encoding is a two-bit character and a one-bit character. So the last character is a bit character.Copy the code

Example 2

Input: bits = [1, 1, 1, 0] Output: false Description: The only encoding is two-bit characters and two-bit characters. So the last character is not a bit character.Copy the code

prompt

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

Answer key

Positive sequence traversal

According to the requirements of the topic, simulation construction code. If the current character is 1, it can form 10,11, so if the current character is 1, the I +1 character can be either 1 or 1; If the current character is 0, the I +1 can’t be represented by two bits, either 0 or 1, so if the current character is 0, take one step forward, and if the current character is 1, take two steps forward. If the last step is right at len-1. The last step is represented by 1 bit

Edit the code as follows:

var isOneBitCharacter = function (bits) {
  const len = bits.length
  if (bits[len - 1= = =1) return false
  let idx = 0
  while (idx < len - 1) {
    if (bits[idx] === 0) {
      idx += 1
    } else {
      idx += 2}}return idx === len - 1
}
Copy the code

Reverse traversal

The first digit of the array must be 0, and the last digit must be 0. If the character before the last digit is 1; Need to discuss.

  • If the number of consecutive ones before the last digit is even, these ones can form a two-bit array,
  • If the character before the last bit is counted consecutively, the last bit of the string must be a two-bit character
  • The answer can be obtained by finding the number of consecutive 1’s before the last digit in the array

Edit the code as follows:


var isOneBitCharacter = function (bits) {
  const len = bits.length
  if (bits[len - 1= = =1) return false
  let l = 0
  for (let i = len - 2; i >= 0; i--) {
    if (bits[i] === 1) {
      l++
    } else {
      break}}return l % 2= = =0
}
Copy the code

conclusion

The author level is limited, if there is insufficient welcome to correct; Any comments and suggestions are welcome in the comments section