LeetCode演算法題-1-bit and 2-bit Characters（Java實現）
這是悅樂書的第302 次更新，第321 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第170題（順位題號是717）。有兩個特殊字元，第一個字元可以用一個位元0表示，第二個字元可以用兩個位元（10或11）表示。現在給出一個由位元位組成的陣列，判斷其最後一個字元是否是一位字元。陣列的最後一位始終是位元0。例如：
輸入：bits = [1,0,0]
輸出：true
說明：解碼它的唯一方法是兩位字元和一位字元，所以最後一個字元是一位字元。
輸入：bits = [1,1,1,0]
輸出：false
說明：解碼它的唯一方法是兩位字元和兩位字元，所以最後一個字元不是一位字元。
注意：
-
陣列長度範圍為[1,1000]。
-
bits[i]始終為0或1。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
為了滿足最後一位是0，前面的n-1位必須完成匹配，即前面的n-1位能夠按照一位、兩位合理組成。所以，我們直接使用迴圈，計算前面n-1位完成組合的長度，判斷其是否等於n-1。因為有兩種情況，遇到0的時候，一位就行，遇到1的時候，只能是兩位。使用一個變數，從0開始往後累加，遇到0就加1，遇到1就加2，最後判斷其是否等於n-1。
public boolean isOneBitharacter(int[] bits) {
int len = bits.length, index = 0;
while (index < len-1) {
if (bits[index] == 0) {
index++;
} else {
index += 2;
}
}
return index == len-1;
}
03 第二種解法
對於第一種解法，我們還可以再優化下，在迴圈中去掉if判斷，直接加上當前元素，因為後面帶了加1，遇到0還是加1，遇到1，就變成加2了，和原來的思路一樣。
public boolean isOneBitharacter2(int[] bits) {
int len = bits.length, index = 0;
while (index < len-1) {
index += bits[index] + 1;
}
return index == len-1;
}
04 第三種解法
我們也可以從後往前推導。因為陣列最後一個數字始終是0，在遇到倒數第二個0時，這中間1的個數只能是偶數個或者0個。如果中間1的個數是0個，即陣列最後兩個元素都是0，不管其前面是1還是0，都滿足條件。其二，如果中間1的個數是奇數個，並且是連著的，就不滿足題目的設定了。
public boolean isOneBitharacter3(int[] bits) {
int len = bits.length;
int count = 0;
for (int i = len - 2; i >= 0; i--) {
if (bits[i] == 1) {
count++;
} else {
break;
}
}
return count%2 == 0;
}
05 小結
演算法專題目前已日更超過五個月 ，演算法題文章170 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！