配列要素に「+」および「*」演算を適用することで取得できる最小の数値。

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃問題文＃＃＃

いくつかの正の整数を含む長さ「N」の配列が与えられます。さらに、「*」と「」の文字のみを含む長さ「N-1」の文字列が与えられます。「*」は乗算演算子、「」は加算演算子です。配列要素に対して算術演算を実行して、最小の正の整数値を取得するように求められます。 ＃＃＃例＃＃＃ ＃＃＃入力＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

イラスト

((1*2)3)の結果値です。

＃＃＃入力＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

イラスト

array[0]*array[1] (9 に等しく) を実行し、結果 1 を表します。その後、result1 を array[2] に追加し、12 に等しくして、result2 として表します。次に、15 に等しい result2 を配列 [3] に追加します。

＃＃＃入力＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

イラスト

((1*3*5)6)の結果値です。

方法 1

この方法ではビット マスキングを使用して問題を解決します。

選択肢が 2 つあるときはいつでも、ビット マスクを使用できます。ここでは、任意の順序で算術演算を適用するように求めていますが、指定された文字列に対して乗算と算術演算のどちらを選択する必要がありますか?

したがって、ビット マスクを使用すると、2 つの算術演算子を配置する可能なすべての方法を取得できます。その後、各ウェイで算術演算を実行し、結果が最小値であるかどうかを確認できます。

入力例を使用して上記のロジックを明確にしましょう。以下の例では、配列 = [1. 3, 5, 6]、文字列 = "*" です。

ここでは、文字列の長さは 3 です。したがって、合計 8 (2^3) 個のビット マスク、つまり 000、001、010、100、110、101、011、111 を使用できます。

ここで、「1」が「*」、「0」が「」演算子であると仮定すると、文字列内で指定された算術演算子のすべての順列を取得できます。

ただし、置換は、「1」の合計数が「*」演算子の数と等しく、「0」の数が「」演算子の数と等しい場合にのみ使用する必要があります。

＃＃＃アルゴリズム＃＃＃

ユーザーは、上記のメソッドを実装するには、次のアルゴリズムに従う必要があります。

ステップ 1

- 「totalMul」変数を定義し、ゼロに初期化して、文字列内の乗算算術演算子の合計数を格納します。

ステップ 2

- for ループを使用して、指定された文字列を反復処理します。現在の文字が「*」に等しい場合、「totalMul」変数の値は 1 増加します。

ステップ 3

- X が文字列の長さに等しい場合に、for ループを使用して、可能なすべてのビット マスクを取得します。ここで、「len」は配列の長さ、「len - 1」は文字列の長さです。

ステップ 4

- 「setBitCount」変数を定義して、現在のマスクに設定されているビット数を保存します。さらに、算術演算の現在の順序を保存するために「順序」リストが定義されます。

• ステップ 5

  - for ループ内で別の for ループを使用して、現在のマスクに設定されているビットの合計数 (「1」) を取得します。 j を左に 1 ビットシフトし、I で & 演算を実行し、j 番目のビットがセットされているかどうかを判断します。

• ステップ 6

  - 現在のビットが設定ビットの場合は、「setBitCount」変数の値を増やし、「*」をシーケンス ベクトルにプッシュします。それ以外の場合は、「」をシーケンス ベクトルにプッシュします。シーケンスベクトル中間。

• ステップ 7

  - setBitCount の値が totalMul の値と等しい場合、現在のマスクを使用して算術演算をスケジュールできることを意味します。そうでない場合は、次の反復に入ります。

• ステップ 8

  - if ステートメントで、「deque」データ構造を使用して配列要素を格納する「currentQueue」を定義します。

• ステップ 9

  - 「順序」リストを調べます。現在の文字が「*」の場合、キュー内の最後の要素をポップし、現在の配列インデックスの要素と乗算します。

• ステップ 10

  - 「orders」リストの現在の文字が「」の場合、現在の配列要素を「currentQueue」にプッシュします。

• ステップ 11

  - while ループを使用して、「currentQueue」からすべての要素をポップし、すべての要素を合計します。

• ステップ 12

  - min() 関数を使用して、「minimum」変数と「sum」変数から最小値を取得します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量
• - O(2N-1*N)、N は配列の長さです。すべてのビット マスクを反復処理すると、for ループを使用して現在のマスクに設定されているビットの合計数がカウントされ、O(2N-1*N) になります。

空間計算量
• − 算術演算子の順序を保存するためにリストを使用するため、O(N)。

以上が配列要素に「+」および「*」演算を適用することで取得できる最小の数値。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。