。添加括號的不同方法

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. Memoization：$memo陣列儲存每個表達式的計算結果，以避免冗餘計算。
2. 基本情況：當表達式為數字時，它會轉換為整數並加到結果中。
3. 遞歸拆分：對於表達式中的每個運算符，將其拆分為左右兩部分，遞歸計算兩部分的結果，然後根據運算符將它們組合起來。
4. 範例用法：使用範例表達式測試 diffWaysToCompute 函數以驗證解決方案。

這種方法可確保您透過利用記憶化來避免冗餘計算，從而有效地計算所有可能的結果。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。添加括號的不同方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！