1-bit and 2-bit Characters LT717

佚名 6年前 (2019-05-09) 随笔 1513人围观抢沙发百度已收录

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.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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.

Idea 1. dynamic programming, let dp[i] represents whether the encoded character could be ended here,

dp[i] = (A[i] == 0) || !dp[i-1]

Time complexity: O(n)

Space complexity: O(n)

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int N = bits.length;
        boolean[] dp = new boolean[N];
        dp[0] = true;
        for(int i = 1; i < N; ++i) {
            dp[i] = (bits[i-1] == 0 || !dp[i-1]);
        }
        
        return dp[N-1];        
    }
}

reduce it to 1-D dynamic programming

dp = (bits[i-1] == 0 || !dp)

Time complexity: O(n)

Space complexity: O(1)

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int N = bits.length;
        boolean dp = true;
     
        for(int i = 1; i < N; ++i) {
            dp = (bits[i-1] == 0 || !dp);
        }
        
        return dp;        
    }
}

Idea 2. Climbing stairs, if we can end in N-1 stairs, the Nth stair would be one character,

step += 1 if A[i] = 0

step += 2 ifA[i] = 1;

 1 class Solution {
 2     public boolean isOneBitCharacter(int[] bits) {
 3         int N = bits.length;
 4         int step = 0;
 5      
 6         for(int i = 0; i < N-1; ++i) {
 7             if(bits[i] == 0) {
 8                 step +=1;
 9             }
10             else {
11                 step += 2;
12                 i+=1;
13             }
14         }
15         
16         return step == N-1;        
17     }
18 }

better code

 1 class Solution {
 2     public boolean isOneBitCharacter(int[] bits) {
 3         int N = bits.length;
 4         int pos = 0;
 5      
 6         while (pos < N-1) {
 7             if(bits[pos] == 0) {
 8                 pos +=1;
 9             }
10             else {
11                 pos += 2;
12             }
13         }
14         
15         return pos == N-1;        
16     }
17 }

Idea 3. If you observe the pattern closely, only the last ones decide whether the last character must be 1-bit character or not, if odd number of ones, we need the last character to pair with the last one, if the number of ones is even, the last character can be 1-bit.

Time complexity: O(n)

Space complexity: O(1)

 1 class Solution {
 2     public boolean isOneBitCharacter(int[] bits) {
 3         int N = bits.length;
 4         int lastOnes = 0;
 5      
 6         for(int i = N-2; i >= 0 && bits[i] != 0; --i) {
 7             ++lastOnes;
 8         }
 9         
10         return ((lastOnes & 1) == 0);        
11     }
12 }