LeetCode实战：子问题分析

主要推送关于对算法的思考以及应用的消息。培养思维能力，注重过程，挖掘背后的原理，刨根问底。本着严谨和准确的态度，目标是撰写实用和启发性的文章，欢迎您的关注。

记录下，LeetCode Contest 56 题1，包括题目意思，和解题思路。 这个题目上来读了好几遍才理解它的意思，理解意思后，这个题目就比较简单了。 不过为了提升算法效率，进一步做了一些优化，优化后 beat 100% submission，重点看下优化思路吧。

01

原题解读

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:

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:

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.

题目的中文意思：

我们有两个特殊的字符，第一个字符可以用一位来表达：0；第二个字符用两位表达，要么为10，要么为11。

给出一个字符串，判断最后一位（位于最右侧的位）是不是一定为0。

LeetCode一般给出的例子不是瞎举的，而是非常有代表性的2个例子。

第一个例子 [1 0 0]，显然 第一个字符必须为1和0搭配为10（这是题目中第二个字符），所以第二个字符也就是最后一个字符必然为 0；

第一个例子 [1 1 1 0]，显然 第一个字符必须为1和1搭配为11，并且第二个字符必须为10，所以最后一个字符是10，而不是0 。

02

分析题目

设 bits为 n 位， 则如果判断最后一位是0的话，即bits[n-1]=0，那么

bits[n-2] 只可能为两种情况：

1. 如果bits.length=1，则只含有一个0字符，一定是；
2. bits[n-2] = 0，即 ...00，则这种结构表明一定是以0结尾；
3. bits[n-2]=1 且 bits[n-3]=0，即 ...010，这种结构一定不是最后一位为0；
4. bits[n-2]=1 且 bits[n-3]=1，即 ...110，这种情况不能确定最后一位一定是0 ，像题目中给出的例子 1110 便是其中一个最后一位不为0的代表，因此只有这种情况才需要遍历

遍历情况分析，如果遍历时，i 能等于 n-1，表示最后一位为0，并且 return；等遍历结束时，还没返回，表明已经越过最后一位，返回 false 。

经过上述分析后，代码如下所示：

public class Solution { public bool IsOneBitCharacter(int[] bits) { int i=0; if(bits.Length==1) //情况1 return true; if(bits[bits.Length-2]==0) //情况2 return true; if(bits.Length >2 && bits[bits.Length-2]==1 && bits[bits.Length-3]==0) //情况3 return false; //情况4 while(i<bits.Length){ if(bits[i]==1){ i+=2; } else i++; if(i==bits.Length-1) return true; } return false; } }

算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

Beat 100% submission

请记住：每天一小步，日积月累一大步！

主要推送关于对算法的思考以及应用的消息。培养思维能力，注重过程，挖掘背后的原理，刨根问底。本着严谨和准确的态度，目标是撰写实用和启发性的文章，欢迎您的关注。