2

これはインタビューの質問です：

Imagine an alphabet of words. Example:
a ==> 1
b ==> 2
c ==> 3
.
z ==> 26
ab ==> 27
ac ==> 28
.
az ==> 51
bc ==> 52
and so on.

文字のシーケンスは昇順のみである必要があります (ab は有効ですが、ba は無効です)。与えられた単語は、有効な場合はそのインデックスを出力し、そうでない場合は 0 を出力します。

Input Output
ab 27
ba 0
aez 441

注: ブルートフォースは許可されていません。質問へのリンクは次のとおりです。 http://www.careercup.com/question?id=21117662

その解決策は次のように理解できます。

  • 単語の合計は 2^26 -1 です。
  • 与えられた単語について、サイズの小さい単語が最初に出現します。
  • 単語の長さを n とすると、
    • n より小さいサイズの単語の総数は C(26, 1) + C(26, 2) + ...+ C(26, n -1)
  • 次に、指定された単語の前に同じサイズの単語がいくつあるかを計算します
  • 2 つの数値に 1 を加えた合計が結果です

参照: sites.google.com/site/spaceofjameschen/annnocements/printtheindexofawordwithlettersinascendingorder--microsoft

サンプル ソリューションでは、作成者が word.size() より小さいサイズの単語数を計算する方法を理解しました。しかし、コードでは、「word」の前に出現する word.size() と同じサイズの単語の数を見つける方法についてはあまりよくわかりません。

正確には、このビット：

char desirableStart;  
i = 0;
while( i < str.size()){     
    desirableStart = (i == 0) ? 'a' : str[i - 1] + 1;   

    for(int j = desirableStart; j < str[i]; ++j){
        index += NChooseK('z' - j, str.size() - i - 1);     // Choose str.size() - i - 1 in the available charset
    }

    i ++;
}

誰かがこのビットを理解するのを手伝ってくれますか? ありがとう。

4

2 に答える 2

0

同じサイズの単語数の計算と短い単語の対応する単語数の計算に違いはありません。

0 から始まる c の配列のインデックス付けに惑わされる可能性があります。したがって、i < str.size()そうでないことを示唆しているかもしれませんが、このループの最後の反復では、インデックスが計算される単語と同じサイズの単語が実際にカウントされます。

于 2013-08-14T10:11:10.520 に答える