#LeetCode 717. 1비트 및 2비트 문자

문제 링크: https://leetcode.com/problems/1-bit-and-2-bit-characters

안녕하세요 여러분
새로운 DSA 블로그와 함께 여기 Kunal. 이것은 블로그 라인의 첫 번째 블로그입니다. 여기서 나는 717. 1-bit and 2-bit Characters을 어떻게 해결했는지 설명했습니다. 리트코드 질문입니다.

요구 사항:

2개의 3개의 특수 문자가 있습니다.

1비트:

000

2비트:

101010

그리고

111111

주어진 비트 배열에서 마지막 문자가 1비트 문자의 일부인지(즉,

000

).

테스트 + 엣지 케이스:

입력: bits = [1, 0, 0] , 출력: true

입력: bits = [1, 1, 1, 0] , 출력: true

입력: bits = [0, 0] , 출력: true없다

000000

문자 그래서 우리는 선택해야

000

두 번.

해결책:

여기서 비트 배열의 마지막 비트가 1비트 문자의 일부만 될 수 있는지 확인하려고 합니다. 배열에서 2비트 및 1비트 문자를 식별해야 합니다. 요구 사항에 따라

111

언제든지 참석

색인색인색인

배열에서

색인색인색인

그리고

인덱스+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는 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

추가 최적화:

마지막 부분에 집중합시다.

하나의 기호/마지막 비트가 있다고 가정하면 정의에 따라

000

그리고 1비트.

마지막 비트와 두 번째 마지막 비트가

000000

그런 다음 마지막 비트는 1비트여야 합니다.

000000

2비트 문자.

마지막 비트 뒤에 1이 있으면 최종 결과는 후속 비트의 수에 따라 달라집니다.

홀수 금액이 있는 경우 마지막 비트는 1비트 문자가 될 수 없습니다.

짝수 금액이 있는 경우 마지막 비트는 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

위 코드의 첫 번째와 두 번째 조건은 둘 다 짝수인 1의 개수가 0이므로 중복됩니다. 이제 1의 개수가 짝수인지 홀수인지 확인해야 합니다.

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

읽어 주셔서 감사합니다.