。かっこを追加するさまざまな方法-PHPチュートリアル-php.cn

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

Barbara Streisand

リリース： 2024-09-20 06:56:07

オリジナル

499 人が閲覧しました

. Different Ways to Add Parentheses

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] の範囲内にあります。
入力式の整数値には、先頭に符号を示す「-」または「+」がありません。

解決策:

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

アプローチ：

再帰:
- 文字列内の演算子 (+、-、) ごとに、その演算子で式を分割します。
- 式の左部分と右部分を再帰的に計算します。
- 演算子を使用して両方の部分の結果を結合します。
メモ化:
- 同じ部分式を複数回再計算することを避けるために、部分式の結果を連想配列に保存します。
基本ケース:
- 式に数値のみが含まれる場合 (つまり、演算子が含まれない場合)、その数値を結果として返します。

チュートリアルの例:

入力「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]
?>

ログイン後にコピー