問題

2つの特殊文字があります。最初の文字は1ビット0で表すことができます。 2番目の文字は2ビット(10または11)で表すことができます。

いくつかのビットで表される文字列が与えられました。最後の文字が1ビット文字でなければならないかどうかを返します。与えられた文字列は常にゼロで終わります。

例1: 入力: ビット= [1、0、0] 出力:true

入力: ビット= [1、1、1、0] 出力:false

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

    }return count%2==0;
}
}
 

このコードはいくつかのテストケースでは機能しません 私の2番目の例のテストケースは動作していません

  ベストアンサー

長いビットストリームの場合、最後からビットストリームを調査する方がはるかに速いでしょう...しかし、ケースを検出するのはもう少し難しいです。終了ビットを見ると:

 .....00 // 1 bit
.....01 // error
.....10 // 1/2 bit
.....11 // 2 bit
 

.....10のケースが存在しない限り、すぐに答えを決定することができます。その場合、もう少し調査する必要があります。

 ....110 // 1/2 bit
....010 // 2 bit
 

そして再び:

 ....1110 // 1/2 bit
....0110 // 1 bit
 

そして再び:

 ...11110 // 1/2 bit
...01110 // 2 bit
 

あなたが見ることができるように、結果の1つのカウントは、最後の単語が1または2ビット(交互に)であるかどうかを判断します。

だから単にそれがどのケースであるかを検出し、すぐにansweを投げるか、最後のゼロの前に結果のものを数え、その答えを決定します。

このようにして、ゼロが発生するまでストリーム全体を処理する必要はありません。

そう:

 .....11 // 2 bit or error
.....01 // error
.....00 // 1 bit
....010 // 2 bit
...0110 // 1 bit
..01110 // 2 bit
.011110 // 1 bit
0111110 // 2 bit
 

ストリームの開始(開始時にゼロはありません)にヒットした場合にのみ、配列全体を処理する必要がありますが、それは不可能です...ストリームが次のようになる単一のケースとして:

 111.....111X
 

したがって、最後にゼロがなくても、最後のビットの前のものの数は、終わりが1ビットか2ビットの長さであるかどうかを伝えます。

 last_word_bit_length= 1 + (consequent_ones_count&1)
 

私はJAVAでコーディングしないので、代わりにC ++の例を示します(それを移植するのは難しくありません)。

 int last_word_bits(int *bits,int n)
    {
    int i=0;
    if (n<1) return 0;                      // empty
    if (n>=1) i|=bits[n-1];
    if (n>=2) i|=bits[n-2]<<1;
    if (i==1) return 0;                     // ...00 or ...0 -> error
    if (i==0) return 1;                     // ...01 -> 1
    if (i==3) return 2;                     // ...11 -> 2 or error
    // count consequent ones
    for (i=0,n-=2;n>=0;n--,i++)
     if (bits[n]==0) break;
    return 1+(i&1);
    }
 

答えを与える:

 {1,0,0} -> 1
{1,1,1,0} -> 2
 

私はビットストリームにエラーが含まれていないことを期待しています。そうでなければ、特別なケースi==3もそれを数える必要があります...それがエラーかどうかを判断するために

  同じタグがついた質問を見る

javaalgorithmdata-structures