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:
1 2 3 4 5 |
Input: bits = [1, 0, 0] Output: True Explanation: The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character. |
Example 2:
1 2 3 4 5 |
Input: bits = [1, 1, 1, 0] Output: False Explanation: The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character. |
Note:
1 <= len(bits) <= 1000
.bits[i]
is always0
or1
.
看着题目挺长的,难度全在读题上…解起来还是比较简单的…
二、解答
首先我们知道,这个问题要求:“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,那么最后一个字符肯定是一位字符了。如果读到的位置超过了最后一个字符,那么最后一个字符肯定是二位字符。比如:
1 |
{ 1, 0, 0 } // 1 -> 0 |
读到的位置一定是最后一位0,为true。
1 |
{ 1, 1, 1, 0 } // 1 -> 1 -> 飞出宇宙 |
读到的位置超过了最后一位0,为false。
根据以上思路,可以写成这样:
OnebitAndTwobitCharactersDay3.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
package com.xie.leetcode.array; public class OnebitAndTwobitCharactersDay3 { public static boolean isOneBitCharacter(int[] bits) { System.out.println("length = " + bits.length); int i = 1; if (bits[i - 1] == 1) { i += 2; } else { i++; } while (i < bits.length) { System.out.println(i); if (bits[i - 1] == 1) { i += 2; } else { i++; } } if (i == bits.length) { return true; } else { return false; } } public static void main(String[] args) { int[] bits1 = new int[] { 1, 0, 0 }; int[] bits2 = new int[] { 1, 1, 1, 0 }; System.out.println(isOneBitCharacter(bits1)); System.out.println(isOneBitCharacter(bits2)); } } |
运行结果为:
1 2 3 4 5 |
length = 3 true length = 4 3 false |
三、总结
本题的解题思路就是“找规律”,解释出来即可,算是比较简单。