每周一算法2017.12.15

1-bit and 2-bit Characters

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.

描述:这里给出两种不同的字符,第一种字符可以被一个字节0 来替代。第二种字符可以被两个字节来替代10或者11。现在给出一个由若干个字节组成的字符串,需要你给出的判断是最后一个字符是否是第一种字符。给出的字符串永远以0结尾。

例子1: 输入字节 bits = [1,0,0] 输出True

例子2: 输入字节 bits = [1,1,1,0] 输出False

说明:解这道题的关键是找到第二种字符。

备注: 字符的长度限制为1 <= len(bits) <= 1000 字符中的每个元素为0或1

分析: 这道题主要是通过遍历字符中的元素,如果遍历到为1,那么就向后进两位,如果遍历为0,那么就向后进1位。遍历到最后一位以后,判断最后一位为0 还是10 如果是0 那么就是true,如果最后一个字符是10那么就返回false

可以给出这样一个例子: bits = [1,1,1,0,0,1,1,1,0,1,0,1,0,0]
假设一个值n = 0 遇到10 或者11 +2操作 遇到0 +1操作

第1次遍历结束后此时组合可为

[(1,1),1,0,0,1,1,1,0,1,0,1,0,0] n = 2

第2次遍历结束后此时组合可为

[(1,1),(1,0),0,1,1,1,0,1,0,1,0,0] n = 4

第3次遍历结束后此时组合可为

[(1,1),(1,0),(0),1,1,1,0,1,0,1,0,0] n = 5

第4次遍历结束后此时组合可为

[(1,1),(1,0),(0),(1,1),1,0,1,0,1,0,0] n = 7

第5次遍历结束后此时组合可为

[(1,1),(1,0),(0),(1,1),(1,0),1,0,1,0,0] n = 9

第6次遍历结束后此时组合可为

[(1,1),(1,0),(0),(1,1),(1,0),(1,0),1,0,0] n = 11

第7次遍历结束后此时组合可为

[(1,1),(1,0),(0),(1,1),(1,0),(1,0),(1,0),0] n = 13

此时n>=bits(lengh)-1跳出循环 此时bit为 [(1,1),(1,0),(0),(1,1),(1,0),(1,0),(1,0),(0)] 此时 13= bits(lengh)-1

进行判断:最后一位为0 属于第一种字符 返回为true

时间复杂度 0(n)

c++:

class Solution {  
public:  
    bool isOneBitCharacter(vector<int>& bits) {
        int num = 0;
        while(num < bits.size() - 1) {
        // 遍历如果为1,那么向后进2位,如果为0,向后进一位
            if(bits[num] == 1) {

                num = num + 2;
            } else {
                num++;
            }
        }
        // num从0开始累加以后不管是+1还是+2加到最后,如果等于最后一位那么就是true,此时面的能够组合为10 11 或者0 因为此时最后一位单独存在为0.
        if(num == bits.size() - 1) {
            return true;
        }
        return false;
    }
};

java:

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

swift:

func isOneBitCharacter(_ bits: inout [Int]) -> Bool {
    var num = 0
    while (num < bits.count-1){
        if (bits[num] == 1){
            num += 2
        }else {
            num += 1
        }
    }
    if num == bits.count - 1  {
        return true
    }
    return false
}

本题来自:leetCode

comments powered by Disqus