8/21 每日一題(由數組中必須由3種組合搭配(1,1)or(1,0) or (0), 且結尾必須是(0))

 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:

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:

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.

class Solution:

    def isOneBitCharacter(self, bits: List[int]) -> bool:

        if bits[-1]==1:

            return False

        i=0

        #只算到倒數第2個

        while i<len(bits)-1:

            if bits[i]==1:

                i+=2

                #下一個是1或是0都是成對的

            else:

                i+=1

        return i ==len(bits)-1

--------------------參考解答

class Solution:

    def isOneBitCharacter(self, bits: List[int]) -> bool:

        ret = True  # 初始化一個變量 ret 為 True，預設為最後一個字符由一個比特表示

        # 使用迴圈遍歷倒數第二個元素開始的部分

        for bit in bits[-2 ::-1]:

            if bit:  # 如果 bit 為 1，表示遇到了兩個比特字符（即 10 或 11）

                ret = not ret  # 將 ret 反轉，用來表示最後一個字符的類型

            else:  # 如果 bit 為 0，表示遇到了一個比特字符（即 0）

                break  # 如果遇到 0，則停止迴圈，因為後面的比特字符不會影響最後一個字符的判斷

        return ret  # 返回 ret，如果 ret 為 True，表示最後一個字符是由一個比特表示，否則為兩個比特表示