。かっこを追加するさまざまな方法

241.括弧を追加するさまざまな方法

難易度: 中

トピック: 数学、文字列、動的プログラミング、再帰、メモ化

数値と演算子の文字列式を指定すると、数値と演算子をグループ化するために考えられるすべての方法を計算して得られるすべての結果を返します。回答は任意の順序で返すことができます。

テスト ケースは、出力値が 32 ビット整数に収まり、異なる結果の数が 10⁴ を超えないように生成されます。

例 1:

• 入力: 式 = "2-1-1"
• 出力: [0,2]
• 説明:

  ((2-1)-1) = 0
  (2-(1-1)) = 2

例 2:

• 入力: 式 = "2*3-4*5"
• 出力: [-34,-14,-10,-10,10]
• 説明:

  (2*(3-(4*5))) = -34
  ((2*3)-(4*5)) = -14
  ((2*(3-4))*5) = -10
  (2*((3-4)*5)) = -10
  (((2*3)-4)*5) = 10

制約:

• 1
• 式は数字と演算子「+」、「-」、「*」で構成されます。
• 入力式内のすべての整数値は [0, 99] の範囲内にあります。
• 入力式の整数値には、先頭に符号を示す「-」または「+」がありません。

解決策:

再帰をメモ化と組み合わせて使用​​すると、部分式の以前に計算された結果を保存できます。これにより、冗長な計算が回避され、ソリューションが最適化されます。

アプローチ：

1. 再帰:

   • 文字列内の演算子 (+、-、​​) ごとに、その演算子で式を分割します。
   • 式の左部分と右部分を再帰的に計算します。
   • 演算子を使用して両方の部分の結果を結合します。

2. メモ化:

   • 同じ部分式を複数回再計算することを避けるために、部分式の結果を連想配列に保存します。

3. 基本ケース:

   • 式に数値のみが含まれる場合 (つまり、演算子が含まれない場合)、その数値を結果として返します。

チュートリアルの例:

入力「2*3-4*5」の場合:

• * -> で分割2、3～4※5
  • 3-4*5 と 2 を再帰的に計算し、結合します。
• - - で分割> 2*3 および 4*5
  • それぞれを再帰的に計算して結合します。
• 他の分割についても同様です。

このソリューションを PHP で実装してみましょう: 241。かっこを追加するさまざまな方法

<?php
class Solution {

    /**
     * @var array
     */
    private $memo = [];

    /**
     * @param String $expression
     * @return Integer[]
     */
    public function diffWaysToCompute($expression) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * @param $expression
     * @return array|mixed
     */
    private function compute($expression) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage
$solution = new Solution();
$expression1 = "2-1-1";
$expression2 = "2*3-4*5";
print_r($solution->diffWaysToCompute($expression1)); // Output: [0, 2]
print_r($solution->diffWaysToCompute($expression2)); // Output: [-34, -14, -10, -10, 10]
?>

説明：

1. メモ化: $memo 配列には、冗長な計算を避けるために各式の計算結果が保存されます。
2. 基本ケース: 式が数値の場合、整数に変換され、結果に追加されます。
3. 再帰的分割: 式内の演算子ごとに、それを左と右の部分に分割し、両方の部分の結果を再帰的に計算し、演算子に基づいてそれらを結合します。
4. 使用例: diffWaysToCompute 関数は、ソリューションを検証するためにサンプル式を使用してテストされます。

このアプローチでは、メモ化を活用して冗長な計算を回避し、考えられるすべての結果を効率的に計算できます。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。かっこを追加するさまざまな方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。