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

preface

Today’s problem is simple, requiring only a simple simulation of traversal, and provides an alternative mathematical solution to traversal from the tail, which in certain cases does not require traversal of the entire array.

A daily topic

Today’s daily question 717. 1 bit and 2 bit characters, the difficulty is simple

  • 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:

Enter: bits = [1.0.0] output:trueExplanation: 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:

Enter: bits = [1.1.1.0] output:falseExplanation: The only encoding is two-bit character and two-bit character. So the last character is not a bit character.Copy the code

Tip:

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

Answer key

Simple simulation

The easiest way to solve this problem is to simply iterate through the array, because we encounter two situations:

  1. Start with 0, indicating a bit 0, change the answer to true and execute the next item

  2. Start with 1 to indicate two bits, change the answer to false and set a flag indicating that the next item needs to be skipped, and then the next item is executed

After we loop through the entire array, we get the value of the answer, which is the last bit.

/ * * *@param {number[]} bits
 * @return {boolean}* /
var isOneBitCharacter = function (bits) {
  let ans = 0,
    n = bits.length;
  let isTwo = 0;
  for (let i in bits) {
    if (isTwo == 1) {
      isTwo = 0;
      continue;
    }
    if (bits[i] == 0) {
      ans = 1;
      continue;
    }
    if (bits[i] == 1) {
      ans = 0;
      isTwo = 1;
      continue; }}return ans;
};
Copy the code

The reverse solution

There’s another way to think about it, but in certain cases you don’t necessarily need to loop through the entire array.

  1. So the last digit has to be 0

  2. And then we can go from the tail to the front until we find the second 0

  3. It then checks whether the length of the array after the second 0 is odd or even. If it is odd, the last bit must be a 0, which returns true, or two bits must be 10, which returns false. Take a look at the picture below to understand.

/ * * *@param {number[]} bits
 * @return {boolean}* /
var isOneBitCharacter = function (bits) {
  let n = bits.length;
  if (bits[n - 1] = =1) {
    return false;
  } else if (n == 1) {
    return true;
  } else {
    let long = 1;
    for (i = n - 2; i >= 0; i--) {
      if (bits[i] == 0) {
        if (long % 2= =1) {
          return true;
        } else {
          return false;
        }
      }
      long = long + 1;
    }
    return n % 2; }};Copy the code