问题描述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 always 0 or 1.参考地址http://www.cnblogs.com/grandyang/p/7790029.html这道题说有两种特殊的字符一种是两位字符只能是二进制的11和10另一种是单个位字符只能是二进制的0。现在给了我们一个只包含0和1的数组问我们能否将其正确的分割使得最后一个字符是个单个位字符。这道题可以使用贪婪算法来做因为两种字符互不干扰只要我们遍历到了数字1那么其必定是两位字符所以后面一位也得跟着而遍历到了数字0那么就必定是单个位字符。所以我们可以用一个变量i来记录当前遍历到的位置如果遇到了0那么i自增1如果遇到了1那么i自增2我们循环的条件是i n-1即留出最后一位所以当循环退出后当i正好停留在n-1上说明最后一位是单独分割开的因为题目中限定了最后一位一定是0所以没必要再判断了参见代码如下class Solution { public: bool isOneBitCharacter(vectorint bits) { int n bits.size(), i 0; while (i n - 1) { if (bits[i] 0) i; else i 2; } return i n - 1; } };这个算法还挺巧的简洁明了_ 
长河君 · 2026/10/23 1:02:42 · 阅读 1.2k 【leetcode】Leetcode:717. 1-bit and 2-bit Characters
问题描述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 always 0 or 1.参考地址http://www.cnblogs.com/grandyang/p/7790029.html这道题说有两种特殊的字符一种是两位字符只能是二进制的11和10另一种是单个位字符只能是二进制的0。现在给了我们一个只包含0和1的数组问我们能否将其正确的分割使得最后一个字符是个单个位字符。这道题可以使用贪婪算法来做因为两种字符互不干扰只要我们遍历到了数字1那么其必定是两位字符所以后面一位也得跟着而遍历到了数字0那么就必定是单个位字符。所以我们可以用一个变量i来记录当前遍历到的位置如果遇到了0那么i自增1如果遇到了1那么i自增2我们循环的条件是i n-1即留出最后一位所以当循环退出后当i正好停留在n-1上说明最后一位是单独分割开的因为题目中限定了最后一位一定是0所以没必要再判断了参见代码如下class Solution { public: bool isOneBitCharacter(vectorint bits) { int n bits.size(), i 0; while (i n - 1) { if (bits[i] 0) i; else i 2; } return i n - 1; } };这个算法还挺巧的简洁明了_