脚撕LeetCode(717)Easy
有两种特殊字符。 第一种字符可以用一比特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.
https://leetcode-cn.com/problems/1-bit-and-2-bit-characters/submissions/
题目的意思：如果一个数是1开头，则他是2比特数，如果单一个0就是1比特数，那么我们遍历的时候只需要判断当前数是否为1，如果为0则是1比特数，如果为1，则下一个数不判断，判断下下个数，到最后一位数看是否1比特数
一、爆破法
我们定义了一个countDouble，如果为0则是1比特数，1则是2比特数的第一位，2则是2比特数的第二位
执行结果如下：
93 / 93 个通过测试用例
状态：通过
执行用时: 0 ms
内存消耗: 37.6 MB
public static boolean isOneBitCharacterMe(int[] bits) {
int countDouble = 0;
for (int i = 0; i < bits.length; i++) {
// 如果当前是两位，且已经经历过一位了，就设置countDouble为2
if (1 == countDouble) {
countDouble = 2;
continue;
}
// 如果当前不是两字节的第二位则判断是否为1
if (1 == bits[i]) {
countDouble = 1;
} else {
countDouble = 0;
}
}
return countDouble == 0;
}执行结果很不稳定，时间经常是100%，但是空间有的时候只有60%，虽然最高峰是90%。
但是这种不稳定结果显然是我们不想要的（虽然我猜测是因为测试用例的问题）
看看官方答案（质量还是不错的，内存基本在97% 98%，时间是100%）
// 线性
public boolean isOneBitCharacter(int[] bits) {
int i = 0;
while (i < bits.length - 1) {
i += bits[i] + 1;
}
return i == bits.length - 1;
}
// 贪心
public boolean isOneBitCharacter(int[] bits) {
int i = bits.length - 2;
while (i >= 0 && bits[i] > 0) i--;
return (bits.length - i) % 2 == 0;
}执行结果如下：
线性：
93 / 93 个通过测试用例
状态：通过
执行用时: 0 ms
内存消耗: 37.5 MB
贪心：
93 / 93 个通过测试用例
状态：通过
执行用时: 0 ms
内存消耗: 37.4 MB
线性的做法是，如果bits[i] = 1 就跳过下一个，如果不为1则访问下一个，这个思维很好，跟我的很相似，但是人家这个明显更敏捷。最后一次循环i是length-2，如果倒数第二个数跟最后一个组成一个2bit数，那么i就会等于length，否则i就会等于length-1，这种思维还是比我的活很多
贪心的做法则是用的倒推，因为0无论是2bit还是1bit，都意味着结束所以找到除了最后一位以外的最后一个0，然后看这个0后面剩下的长度是否为双数，如果为双数那么最后一位数就是2bit，如果为单数则最后一位数是1bit。
可以看到贪心的做法十分的简洁，估计如果时间能细化到ms以下的位级的话，贪心应该会比线性好很多。
两个做法都非常不错，但是我想到的居然是最蠢的，最不稳定的办法，不愧是爆破法，算法之路还很长啊。
腾讯云开发者
