**

973. 1位跟2位字符

**
*

題目：

**
我們有兩個(gè)特殊的字符。第一個(gè)字符可以用一位 0 來表示。第二個(gè)字符可以用兩位(10 或者 11)表示。

現(xiàn)在給出一個(gè)字符串表示若干位。返回最后一個(gè)字符是否必定為一位字符。給出的字符串總是以 0 結(jié)尾。

樣例
樣例 1:
輸入:
bits = [1, 0, 0]
輸出: True
解釋:
解碼它的唯一方法是兩位字符和一位字符。所以最后一個(gè)字符是一位字符。

樣例 2:
輸入:
bits = [1, 1, 1, 0]
輸出: False
解釋:
解碼它的唯一方法是兩位字符和兩位字符。所以最后一個(gè)字符不是一位字符。
注意事項(xiàng)
1.1 <= len(bits) <= 1000.
2.bits[i] 總是 0 or 1.

思路：
1.首先看到這個(gè)題目的時(shí)候我想到的是哈夫曼編碼，但是仔細(xì)想想這只是需要我們驗(yàn)證一下而已，應(yīng)該不需要這么做；
**2.如果我最后一位給的是1，那么我們可以肯定的結(jié)果肯定是false;
3.接著最后一位是0的時(shí)候才需要進(jìn)一步考慮更多。如果所給的數(shù)組大小為length，那么除掉最后一位0，也就是還有l(wèi)ength-1位，如果這length-1位剛好按照這個(gè)規(guī)則編碼完，那么就輸出true，否則輸出false；
4.那怎么解讀這個(gè)規(guī)則呢？其實(shí)很簡單，從第一位開始，如果遇到0，直接下一位，如果是1，那就跳一位，到下下位。一直這么下去，那什么時(shí)候跳出這個(gè)循環(huán)呢？？？
條件應(yīng)該是前l(fā)ength-1為，也就是下標(biāo)到length-2；如果下標(biāo)比length-2大或者等于length-2的時(shí)候跳出循環(huán)；那么問題來了，跳出循環(huán)的時(shí)候，我們的下標(biāo)有兩種可能性。第一是剛好前面length-1個(gè)剛好編碼，下標(biāo)等于length-1。第二就是不能剛好編碼，按照我剛剛的循環(huán)規(guī)則，此時(shí)的下標(biāo)不等于length-1。
總的思路就是這樣子。下面附上我自己寫的代碼，雖然不是很好，但作為小白來說也不苛求速度了。在這里插入代碼片

bool isOneBitCharacter(vector<int> &bits) {int length=bits.size();int i=0;if(bits[length-1]==0){for(i=0;i<length-1;)if(bits[i]==0) i++;else {i++;i++;}if(i==length-1) return true;else return false;} }

總結(jié)

以上是生活随笔為你收集整理的Lintcode 973 解题思路及c++代码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。