Leetcode 1-bit and 2-bit Characters 2017年12月2日
未分类
0 条评论

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 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，那么最后一个字符肯定是一位字符了。如果读到的位置超过了最后一个字符，那么最后一个字符肯定是二位字符。比如：

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

三、总结

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

Post Views: 60