#LeetCode 717. 1-битные и 2-битные символы

_{^{Ссылка на проблему: https://leetcode.com/problems/1-bit-and-2-bit-characters}}

Всем привет
С вами Кунал с новым блогом о DSA. Это первый блог в линейке блогов. Здесь я описал, как я решил проблему 717. 1-битные и 2-битные символы. Вопрос LeetCode.

Требование:

У нас есть два три специальных символа:

1. 1-бит: $0$

   0

2. 2-бит:
   $10$

   10 и

   $11$

   11

Из заданного массива битов мы должны определить, является ли последний символ частью 1-битного символа (т.е. только

0).

Тест + граничные случаи:

1. Входные данные: bits = [1, 0, 0], Output: true.
2. Вход: bits = [1, 1, 1, 0], Output: true
3. Вход: bits = [0, 0], Output: trueНе существует
   $00$

   00, поэтому нам нужно выбрать

   $0$

   0 два раза.

Решение:

Здесь мы хотим подтвердить, что последний бит в массиве битов может быть частью только 1-битного символа. Мы должны определить 2-битные и 1-битные символы в массиве. В соответствии с требованиями, если есть

1 присутствует в любом

индекс в массиве, тогда

индекс и

индекс+1 должен быть частью 2-битных символов. Итак, теперь у нас есть простые условия, которые мы можем проверить.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        i = 0
        while i < len(bits):
            # If 1 is present then the next bit should be part of the 2-bit character
            # So skip the next bit
            if bits[i] == 1:
                i += 1

            # If at end of the list, 0 is present and not skipped 
            # Last bit should be a 1-bit character 
            elif bits[i] == 0 and i == len(bits) - 1:
                return True

            i += 1

        return False

bits[i] == 0 здесь лишнее, так как оно должно быть охвачено как else часть bits[i] == 1. Кроме того, нет смысла проверять i == len(bits) - 1 в каждой итерации, в идеале мы должны проверять, указывает ли текущий (не пропущенный) индекс на последний индекс бита в конце, вне цикла.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        i = 0
        n = len(bits)
        last = len(bits) - 1
        while i < last:
            # If 1 is present then the next bit should be part of the 2-bit character
            # So skip the next bit
            if bits[i] == 1:
                i += 1
            i += 1

        # If the last index is not skipped then it should be a 1-bit character
        return i == last

Дальнейшая оптимизация:

Давайте сосредоточимся на последнем бите.

1. Предположим, что есть один символ / последний бит, тогда по определению он должен быть
   $0$

   0 и 1-бит.

2. Если последний бит и второй последний бит
   $00$

   00, то последний бит должен быть 1-битным, так как не существует

   $00$

   00 в 2-битном.

3. Если за последним битом следует единица, то конечный результат зависит от количества последующих единиц.
   1. Если присутствует нечетное количество, то последний бит не может быть 1-битным символом.
   2. Если присутствует четное количество, то последний бит должен быть 1-битным символом.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        n = len(bits)
        if n == 1:
            return True

        if bits[-2] == 0:
            return True

        ones = 0
        for i in range(n - 2, -1, -1):
            if bits[i] == 1:
                ones += 1
            else: break

        return ones % 2 == 0

Первое и второе условия в приведенном выше коде избыточны, так как в обоих случаях счетчик единицы равен 0, что является четным. Поэтому теперь мы должны просто проверить, является ли счетчик единиц четным или нечетным.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        evenOnes = True
        for bit in bits[-2::-1]:
            if bit == 1:
                evenOnes = not evenOnes
            else: break

        return evenOnes

Спасибо за прочтение.