版权声明: 本文为博主Bravo Yeung(知乎UserName同名)的原创文章,欲转载请先私信获博主允许,转载时请附上网址
http://blog.csdn.net/lzuacm。
C#版 - Leetcode717. 1比特与2比特字符 - 题解
Leetcode 717. 1-bit and 2-bit Characters
在线提交: https://leetcode-cn.com/problems/1-bit-and-2-bit-characters/
题目描述
有两种特殊字符。第一种字符可以用一比特0
来表示。第二种字符可以用两比特(10
或 11
)来表示。
现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符,程序需返回bool值。给定的字符串总是由0结束。
示例 1:
输入:
bits = [1, 0, 0]
输出: True
解释:
唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。
示例 2:
输入:
bits = [1, 1, 1, 0]
输出: False
解释:
唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。
注意:
-
1 <= len(bits) <= 1000
. -
bits[i]
总是0
或1
.
分析:
观察规律可知,满足条件的数有如下规律:
- 连续的0只能出现在数的末尾
- 如果位数>1,首位必须是1
- 如果前方(从倒数第3位起)出现0,一定是和1交替出现的
满足条件的数的构成有如下几种情况:
case 1.[0]
此情况下末尾为单个0
,返回值为true
case 2.[1⋯ 00]" role="presentation">[1⋯ 00][1⋯ 00]
此情况下末尾为10
+单个0
,返回值为true
case 3.[1⋯ 10]" role="presentation">[1⋯ 10][1⋯ 10]
此情况下,1的个数是单数,就一定是false;1的个数是双数,就一定是true。
AC代码:
public class Solution
{
public bool IsOneBitCharacter(int[] bits)
{
bool IsTail0 = false;
int len = bits.Length;
if (len == 1)
return true;
if (bits.Last() == 0 && bits[len - 2] == 0)
return true;
int oneCounts = 0;
/*
for (int i = len - 2; i >= 0; i--)
{
if (bits[i] == 1)
oneCounts++;
}
*/
for (int i = len - 2; i >= 0 && bits[i] != 0; i--)
oneCounts++;
IsTail0 = (oneCounts %2 == 0) ? true : false;
return IsTail0;
}
}
Rank:
You are here!
Your runtime beats 98.85%
of csharp submissions.
疑问Q:
为何两种循环的结果不一样?需要debug一下了~
利用位运算&
进行改进:
public class Solution
{
public bool IsOneBitCharacter(int[] bits)
{
bool IsTail0 = false;
int len = bits.Length;
if (len == 1)
return true;
if (bits.Last() == 0 && bits[len - 2] == 0)
return true;
int oneCounts = 0;
for (int i = len - 2; i >= 0 && bits[i] != 0; i--)
oneCounts++;
IsTail0 = (oneCounts & 1) == 0; // Needs bracket () for & since the priority of == higher than &
return IsTail0;
}
}