範囲内の重複のない数値の合計数

この記事では、低値から高値までの特定の範囲で数値を繰り返さずに正の整数の数を数えるさまざまな方法について説明します。最初の方法は、範囲内のすべての数値を反復処理し、それらの数値に重複する数値が含まれているかどうかを確認する総当り的な方法です。 2 番目の方法では、プレフィックス配列を使用して必要な数を計算し、最後の方法では動的プログラミングのメモリ概念を使用して必要な結果を取得します。

問題文: 2 つの数値を下位から上位まで指定すると、その数値に重複する数字が含まれないように、下位と上位の間のすべての数値の数を見つけなければなりません。

方法1

これは強引な方法です。すべての数値を低い値から高い値まで繰り返して、重複する数値が含まれているかどうかを確認するだけです。これが私たちの問題に対する最も簡単な解決策です。

同じコードの解決策を以下に示します:

方法 2

このアプローチでは、プレフィックス配列を使用して、インデックス「イテレータ」まで重複する数値を含まない整数の数を保存します。

この方法に含まれる手順は次のとおりです:

数値に重複する桁があるかどうかを確認する関数を定義します。

• プレフィックス配列をゼロで初期化します。プレフィックス配列には、指定されたインデックス「イテレータ」までの有効桁数が格納されます。

• 各数値を下位から上位までたどり、重複する数値があるかどうかを確認します。重複する番号がない場合は、プレフィックス配列の対応するインデックスに 1 を追加します。

• プレフィックス配列のプレフィックスの合計を計算します。プレフィックスの合計により、範囲内の有効桁数の合計が得られます。

• プレフィックスの合計を返します。

• ＃＃＃例＃＃＃

  このメソッドのコードを以下に示します -

  リーリー ＃＃＃出力＃＃＃ リーリー
時間計算量 - O(nlogn)、n は (高 - 低) です。

空間の複雑さ - O(n)

方法 3 動的プログラミング方法

このアプローチでは、問題をサブ問題に分解し、サブ問題の結果をメモリ テーブルに保存します

プログラムは、指定された範囲内の有効桁数、つまり、桁が繰り返されていない数値の合計をカウントします。これは動的プログラミング手法を使用しており、関数 dp("iterator",used) は位置 "iterator" から開始して数値 "used" で形成できる有効桁数を返します。

memtable を使用して dp 関数の結果を保存し、数値の範囲を反復して数値ごとに dp 関数を呼び出します。開始するすべての「反復子」に対する dp 関数の結果の合計が、範囲内の有効桁数の合計になります。

- このコードでは、低い値から高い値までの範囲内の数値の合計数を重複せずにカウントする 3 つの方法について説明しました。

以上が範囲内の重複のない数値の合計数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。