C#版[击败98.85%的提交] - Leetcode717. 1比特与2比特字符 - 题解

版权声明: 本文为博主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. <nobr aria&#45;hidden="true"> [1⋯ 00] </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mrow> <mo> [ </mo> <mtable columnspacing="1em" rowspacing="4pt"> <mtr> <mtd> <mn> 1 </mn> </mtd> <mtd> <mo> ⋯ </mo> <mtext>   </mtext> </mtd> <mtd> <mn> 00 </mn> </mtd> </mtr> </mtable> <mo> ] </mo> </mrow> </math>
此情况下末尾为10+单个0，返回值为true

case 3. <nobr aria&#45;hidden="true"> [1⋯ 10] </nobr> <math xmlns="http&#58;&#47;&#47;www&#46;w3&#46;org&#47;1998&#47;Math&#47;MathML"> <mrow> <mo> [ </mo> <mtable columnspacing="1em" rowspacing="4pt"> <mtr> <mtd> <mn> 1 </mn> </mtd> <mtd> <mo> ⋯ </mo> <mtext>   </mtext> </mtd> <mtd> <mn> 10 </mn> </mtd> </mtr> </mtable> <mo> ] </mo> </mrow> </math>
此情况下，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;
    }
}