X

LEETCODE 717. 1-bit and 2-bit Characters 解题思路分析

题目大意:

1比特与2比特字符

有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。

现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

示例 1:

输入: 
bits = [1, 0, 0]
输出: True
解释: 
唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。

示例 2:

输入: 
bits = [1, 1, 1, 0]
输出: False
解释: 
唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。

注意:

  • 1 <= len(bits) <= 1000.
  • bits[i] 总是01.

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=717

解题思路分析:

一开始我将这道题想复杂了,以为是动态规划问题,仔细分析后发现,其实对于任意给定的数组,它只存在唯一的一种分组方式,当遇见1时,它代表的一定是2比特字符(10或者11),而遇到0时,它只能是1比特字符0,因此,我们从第0位开始向后分组,如果第0位是1,该组长度为2,下标向后移动2格,如果是0,该组长度为1,下标向后移动1格,直到最后一组,查看他的长度,如果是1,返回true,否则返回false。

本体使用循环或者递归都可以实现上述逻辑。

实现代码:

public boolean isOneBitCharacter(int[] bits) {
    // 递归求解
    return help(bits, 0);
}

boolean help(int[] bits, int index){
    // 如果当前是倒数第二位
    if(index==bits.length-2){
        // 如果当前位是0,返回true。最后两组一定是0和0
        // 如果当前位是1,返回false。最后一组一定是10
        return bits[index]==0;
    }
    // 如果当前是最后一位,返回true。
    if(index==bits.length-1){
        return true;
    }
    if(bits[index]==0){
        // 如果当前位是0,当前位自己是一组,向后移动一格
        return help(bits, index+1);
    }else{
        // 如果当前位是1,当前位与后一位是一组,向后移动2格
        return help(bits, index+2);
    }
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for 1-bit and 2-bit Characters.

Memory Usage: 38.6 MB, less than 11.11% of Java online submissions for 1-bit and 2-bit Characters.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-717-1-bit-and-2-bit-characters-解题思路分析/
Categories: leetcode
kwantong: