Bit1AndBit2Characters [source code]

public class Bit1AndBit2Characters {
static
/******************************************************************************/
class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = 0;
        while (i < bits.length - 1) {
            if (bits[i] == 1)
                i += 2;
            else {
                assert bits[i] == 0;
                i++;
            }
        }
        return i == bits.length - 1 && bits[i] == 0;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        Bit1AndBit2Characters.Solution tester = new Bit1AndBit2Characters.Solution();
        int[][] inputs = {
            {1,0,0}, {1},
            {1,1,1,0}, {0},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            System.out.println (Printer.separator ());
            int[] bits = inputs[2 * i];
            boolean ans = inputs[2 * i + 1][0] == 1;
            boolean output = tester.isOneBitCharacter (bits);
            System.out.printf ("%s -> %s, expected: %b\n",
                Printer.array (bits), Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

看完了大概理解这个题目的意思了, 其实就相当于给了你一个类似被entropy (Huffman) encoding之后得到的一个输出, 然后让你来得code就是了; 而且题目本身还是简化过的; 不过这个题目还是被大量的downvote, 原因也不难理解, 这个题目的描述给的就太模糊了, 这个是假设你熟悉entropy encoding的情况下, 就很好理解, 不然就很云里雾里;

总体来说是一个非常简单的题目, 最后基本是秒杀掉了, 速度是8ms (42%), 还算可以接受, 毕竟题目算是比较简单的;

这个是editorial1:

class Solution {  
    public boolean isOneBitCharacter(int[] bits) {  
        int i = 0;  
        while (i < bits.length - 1) {  
            i += bits[i] + 1;  
        }  
        return i == bits.length - 1;  
    }  
}

这个写法跟我的写法基本是差不多的, 不过他body里面写的比我更加简练一些; 这种小技巧可以适当了解一下; 不过我认为他最后这个返回值不够全面, 万一最后一个bit是1, 他这个算法我觉得可能是有问题;

editorial2, 同时也是submission最优解, 优势在于不需要做一个full scan:

class Solution {  
    public boolean isOneBitCharacter(int[] bits) {  
        int i = bits.length - 2;  
        while (i >= 0 && bits[i] > 0) i--;  
        return (bits.length - i) % 2 == 0;  
    }  
}

The second-last 0 must be the end of a character (or, the beginning of the array if it doesn't exist). Looking from that position forward, the array bits takes the form [1, 1, ..., 1, 0] where there are zero or more 1's present in total. It is easy to show that the answer is true if and only if there are an even number of ones present.
In our algorithm, we will find the second last zero by performing a linear scan from the right. We present two slightly different approaches below.

举个例子来说, 如果是10110, 那么我们最后得到的i是1, 理论上来说, 如果是判断这个pattern里面1的个数, 应该判断(5 - 1 - 1 - i) % 2 == 0, 两个-1相当于就抵消了(mod2), 或者可以这样理解, [length - 1]是0, [length]不存在, 反正不是1, 所以最后判断mod2的时候计算把这两位都包括进去也都无所谓;

discussion基本没有更好的解法了; 这个题目本身毕竟还是比较简单; 不过奇怪的是好像discussion里面不少人其实并不知道这个题目怎么做, 或者写出来的答案很复杂; 感觉还是个体思路的差别;

Problem 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:

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.

Note:

• 1 <= len(bits) <= 1000.
• bits[i] is always 0 or 1.

Difficulty:Easy
Total Accepted:10.7K
Total Submissions:21.4K
Contributor:fallcreek
Companies
quora
Related Topics
array
Similar Questions
Gray Code

Hide Hint 1

Keep track of where the next character starts. At the end, you want to know if you started on the last bit.