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.
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 }
1-bit and 2-bit Characters LT717
原文：https://www.cnblogs.com/taste-it-own-it-love-it/p/10836377.html