作者:alg-flody
请点击上面公众号,免费订阅。
主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。
记录下,LeetCode Contest 56 题1,包括题目意思,和解题思路。
这个题目上来读了好几遍才理解它的意思,理解意思后,这个题目就比较简单了。
不过为了提升算法效率,进一步做了一些优化,优化后 beat 100% submission,重点看下优化思路吧。
01
原题解读
We have two special characters. The first character can be represented by one bit
. The second character can be represented by two bits (
- 0
or
- 10
).
- 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] 只可能为两种情况:
遍历情况分析,如果遍历时,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
请记住:每天一小步,日积月累一大步!
主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。
欢迎关注《算法channel》公众号
来源: https://mp.weixin.qq.com/s?__biz=MzI3NTkyMjA4NA==&mid=2247483873&idx=2&sn=1abe2b8661bf7b1ae4ab827c1c551297&chksm=eb7c2c2adc0ba53c75192e68ffb15daf5cf8d937eb940a900e73caa81c5b50bf50759092e318#rd