★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10509872.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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).
Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.
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.
Note:
1 <= len(bits) <= 1000.bits[i]is always0or1.
有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。
现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。
示例 1:
输入: bits = [1, 0, 0] 输出: True 解释: 唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。
示例 2:
输入: bits = [1, 1, 1, 0] 输出: False 解释: 唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。
注意:
1 <= len(bits) <= 1000.bits[i]总是0或1.
20ms
1 class Solution 2 { 3 func isOneBitCharacter( _ bits: [ Int ] ) -> Bool 4 { 5 func findR1( _ startIndex: Int ) -> Bool 6 { 7 if startIndex == ( bits.count ) 8 { 9 return false 10 } 11 if startIndex == ( bits.count - 1 ) 12 { 13 return bits[ ( bits.count - 1 ) ] == 0 14 } 15 var result: Bool 16 if bits[ startIndex ] == 0 17 { 18 result = findR1( startIndex + 1 ) 19 } 20 else 21 { 22 result = findR1( startIndex + 2 ) 23 } 24 return result 25 } 26 return findR1( 0 ) 27 } 28 }
1 class Solution { 2 func isOneBitCharacter(_ bits: [Int]) -> Bool { 3 var n:Int = bits.count 4 var i:Int = 0 5 while (i < n - 1) 6 { 7 i += bits[i] + 1 8 } 9 return i == n - 1 10 } 11 }
24ms
1 class Solution { 2 func isOneBitCharacter(_ bits: [Int]) -> Bool { 3 var skipping = false, is1bit = false 4 5 for b in bits { 6 if skipping { 7 skipping = false 8 continue 9 } 10 if b == 1 { 11 skipping = true 12 is1bit = false 13 } else { 14 is1bit = true 15 } 16 } 17 return is1bit 18 } 19 }
28ms
1 class Solution { 2 func isOneBitCharacter(_ bits: [Int]) -> Bool { 3 var state = false 4 var i = 0 5 while i < bits.count { 6 if bits[i] == 1{ 7 state = false 8 i += 2 9 }else{ 10 state = true 11 i += 1 12 } 13 } 14 return state 15 } 16 }
52ms
1 class Solution { 2 func isOneBitCharacter(_ bits: [Int]) -> Bool { 3 let count = bits.count 4 guard count > 1 else { return true } 5 6 var cursor = count - 2 7 var oneCount = 0 8 while cursor >= 0 { 9 defer { cursor -= 1 } 10 if bits[cursor] == 1 { 11 oneCount += 1 12 } 13 else { 14 break 15 } 16 } 17 18 return oneCount & 1 == 0 19 } 20 }
60ms
1 class Solution { 2 func isOneBitCharacter(_ bits: [Int]) -> Bool { 3 var isTwoBit = false 4 5 bits.enumerated().forEach { index, bit in 6 if isTwoBit { 7 isTwoBit = (bits.count - 1 == index) 8 return 9 } 10 11 if bit == 1 { 12 isTwoBit = true 13 return 14 } 15 } 16 17 return !isTwoBit 18 } 19 }
请发表评论