LeetCode算法题-1-bit and 2-bit Char

这是悦乐书的第302次更新，第321篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第170题（顺位题号是717）。有两个特殊字符，第一个字符可以用一个比特0表示，第二个字符可以用两个比特（10或11）表示。现在给出一个由比特位组成的数组，判断其最后一个字符是否是一位字符。数组的最后一位始终是比特0。例如：

输入：bits = [1,0,0]

输出：true

说明：解码它的唯一方法是两位字符和一位字符，所以最后一个字符是一位字符。


输入：bits = [1,1,1,0]

输出：false

说明：解码它的唯一方法是两位字符和两位字符，所以最后一个字符不是一位字符。


注意：

• 数组长度范围为[1,1000]。

• bits[i]始终为0或1。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

为了满足最后一位是0，前面的n-1位必须完成匹配，即前面的n-1位能够按照一位、两位合理组成。所以，我们直接使用循环，计算前面n-1位完成组合的长度，判断其是否等于n-1。因为有两种情况，遇到0的时候，一位就行，遇到1的时候，只能是两位。使用一个变量，从0开始往后累加，遇到0就加1，遇到1就加2，最后判断其是否等于n-1。

public boolean isOneBitharacter(int[] bits) {
    int len = bits.length, index = 0;
    while (index < len-1) {
       if (bits[index] == 0) {
            index++;
        } else {
            index += 2;
        } 
    }
    return index == len-1;
}

03 第二种解法

对于第一种解法，我们还可以再优化下，在循环中去掉if判断，直接加上当前元素，因为后面带了加1，遇到0还是加1，遇到1，就变成加2了，和原来的思路一样。

public boolean isOneBitharacter2(int[] bits) {
    int len = bits.length, index = 0;
    while (index < len-1) {
        index += bits[index] + 1;
    }
    return index == len-1;
}

04 第三种解法

我们也可以从后往前推导。因为数组最后一个数字始终是0，在遇到倒数第二个0时，这中间1的个数只能是偶数个或者0个。如果中间1的个数是0个，即数组最后两个元素都是0，不管其前面是1还是0，都满足条件。其二，如果中间1的个数是奇数个，并且是连着的，就不满足题目的设定了。

public boolean isOneBitharacter3(int[] bits) {
    int len = bits.length;
    int count = 0;
    for (int i = len - 2; i >= 0; i--) {
        if (bits[i] == 1) {
            count++;
        } else {
            break;
        }
    }
    return count%2 == 0;
}

05 小结

算法专题目前已日更超过五个月，算法题文章170+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！