Leetcode 1-bit and 2-bit Characters

继续刷题。

参考:https://leetcode.com/problems/1-bit-and-2-bit-characters/description/

一、题目

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:

Example 2:

Note:

  • 1 <= len(bits) <= 1000.
  • bits[i] is always 0 or 1.

看着题目挺长的,难度全在读题上…解起来还是比较简单的…

二、解答

首先我们知道,这个问题要求:“Return whether the last character must be a one-bit character or not.”,即“返回最后一个字符是否必须是一位字符”(而且必须是0)。

然后,根据题目的条件,一位字符只有0,二位字符有10/11。也就是说,我们从头去遍历每个字符,如果读到的i位置的字符是0,那么需要去读的下一个字符位置为i+1。如果读到一个字符是1,因为存在10/11两种组合,所以直接去读i+2位置的字符即可。

此时,如果读到的位置就是最后一位0,那么最后一个字符肯定是一位字符了。如果读到的位置超过了最后一个字符,那么最后一个字符肯定是二位字符。比如:

读到的位置一定是最后一位0,为true。

读到的位置超过了最后一位0,为false。

根据以上思路,可以写成这样:

OnebitAndTwobitCharactersDay3.java

运行结果为:

三、总结

本题的解题思路就是“找规律”,解释出来即可,算是比较简单。

发表评论

电子邮件地址不会被公开。 必填项已用*标注