指定された文字を使用して、少なくとも 2 つの異なる文字を含む長さ 3 の文字列の数を数えます。

3 つの異なる文字「A」、「B」、「C」の出現頻度を表す 3 つの整数「a」、「b」、「c」を与えてください。これらの文字を使用して形成できる異なる文字列の数を見つける必要があり、形成された文字列には少なくとも 2 つの異なる文字が存在する必要があります。この問題を解決する 2 つの方法を見ていきます。1 つは単純な方法で、もう 1 つは数学的です。

＃＃＃例＃＃＃ リーリー リーリー

イラスト

「ABC」、「ABC」、「ACC」という 3 つの文字列を作成できます。これらの文字列では、「A」を 3 回、「B」を 2 回、「C」を 4 回使用していますが、これは指定された頻度と同じか、それより少ない頻度であり、すべての文字列には少なくとも 2 つの異なる文字が含まれています。

リーリー リーリー

イラスト p>

文字列「ACC」、「BCC」、「BCC」、「BCC」を作成できます。新しい文字列を作成する他の文字がないため、2 つの「C」を除くすべての指定された文字を使用しました。他の組み合わせを試していたら、最終的な文字列の数はさらに少なくなったでしょう。

単純な方法

最も簡単な方法は、指定された周波数の可能な組み合わせをすべて見つけることですが、問題は、これには非常に時間がかかり、非常に非効率であることです。

考えられるすべての部分文字列を生成する必要がありますが、その数が大きい場合、コンピューターでは処理できないほど多くの時間とスペースが必要になります。

数学的方法

＃＃＃アイデア＃＃＃

このアプローチの背後にある考え方は、文字列内に少なくとも 2 つの異なる文字が必要であるため、常に最も頻度の低い文字に焦点を当てようとするということです。

作成できる文字列の最大数は (a b c)/3 で、可能な数は少なくとも 2 つの文字列の出現頻度によってのみ決まります。

少なくとも 2 つの周波数が x と y で、その合計が (a b c)/3 以上である場合、この値を答えとして出力できます。それ以外の場合は、x と y の合計が答えになります。

＃＃＃実装＃＃＃

解決策を見つけるための例とアイデアを見てきました。次に、コードの実装を始めましょう -

まず、3 つの整数を受け入れ、整数を返す関数を作成します。

関数では、まずすべての整数をベクトルに格納し、次にベクトルをソートして最小頻度の整数を取得します。
指定されたすべての要素の合計を取得し、それを 3 で割って、作成できる文字列の最大数を取得します。
後で、最大の文字列の値と 2 つの周波数の最小合計の値を比較します。合計が小さい場合は、最大文字列が少なくとも 2 つの周波数要素の​​合計になるように更新されます。
最後に、可能な最大の文字列の値を返し、それを main 関数で出力します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
• 時間と空間の複雑さ

結果を取得するためにループや再帰呼び出しを使用していないため、上記のコードの時間計算量は O(1) または定数です。

ここでは余分なスペースを使用していないため、上記のコードのスペース複雑さは O(1) です。

＃＃＃結論は＃＃＃

このチュートリアルでは、少なくとも 2 つの異なる文字を含む指定された文字を使用して、カウント 3 で 3 つの長さの文字列を検索するプログラムを実装しました。私たちは単純な方法を議論し、一定の時間と空間の複雑さ、つまり O(1) を持つ数学的方法を実装しました。

以上が指定された文字を使用して、少なくとも 2 つの異なる文字を含む長さ 3 の文字列の数を数えます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。