### 题目描述 有两种特殊字符： - 第一种字符可以用一比特 0 表示 - 第二种字符可以用两比特（10 或 11）表示 给你一个以 0 结尾的二进制数组 bits ，如果最后一个字符必须是一个一比特字符，则返回 true 。 ### 输入输出 #### 示例1 ``` 输入: bits = [1, 0, 0] 输出: true 解释: 唯一的解码方式是将其解析为一个两比特字符和一个一比特字符。 所以最后一个字符是一比特字符。 ``` #### 示例2 ``` 输入：bits = [1,1,1,0] 输出：false 解释：唯一的解码方式是将其解析为两比特字符和两比特字符。 所以最后一个字符不是一比特字符。 ``` ### 题目解答 #### 思路 由题目可知，字符串的最后一个保证是0，不是1。 对数组从左到右遍历，如果bits[i]==0,那么遇到第一个字符，进行i++的操作。如果bits[i]==1,那么遇到第二种字符，i=i+2的操作。 通过遍历的方式也可知，字符串的解析方式是唯一的。 如果遇到i=n-1的时候，说明最后只剩1个字符，同时是0，那么返回true，否则返回false。 **算法复杂度** 时间复杂度：一次遍历O(N) 空间复杂度：无需开新的内存空间O(1) #### 代码实现 ```java class Solution{ public boolean isOneBitCharacter(int[] bits){ int i=0; while(i < bits.length-1){ i += bits[i] + 1; } return i ==bits.length-1; } } ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复