717. 1-bit and 2-bit Characters

题目描述和难度

  • 题目描述：

有两种特殊字符。第一种字符可以用一比特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.

思路分析

求解关键：

参考解答

参考解答1

public class Solution {

    // 有点贪心算法的意思

    public boolean isOneBitCharacter(int[] bits) {
        int len = bits.length;
        if (len == 0) {
            return false;
        }
        if (len == 1) {
            return true;
        }
        int i = 0;
        // 最多看到 len-2 ，len - 1 不用看了
        // 1 0 1 1 1 1 0
        // 1 0 1 1 1 0 0
        while (i < len - 1) {
            if (bits[i] == 0) {
                i++;
            } else {
                i += 2;
            }
        }
        return i == len - 1;
    }

    public static void main(String[] args) {
        int[] bits = {1, 1, 1, 0};
        Solution solution = new Solution();
        boolean oneBitCharacter = solution.isOneBitCharacter(bits);
        System.out.println(oneBitCharacter);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0717-1-bit-and-2-bit-characters ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。