Given a string
Example 1:
Input: expression = "2-1-1" Output: [0,2] Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2
Example 2:
Input: expression = "2*3-4*5" Output: [-34,-14,-10,-10,10] Explanation: (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
Constraints:
1 <= expression.length <= 20 expression consists of digits and the operator'+' ,'-' , and'*' .- All the integer values in the input expression are in the range
[0, 99] .
Solution
這題也能看成是 95. Unique Binary Search Trees II 的衍生題
這題用 recursion 的方式來解會比較容易理解
能放入括號的,一定是運算符號的左右兩側,也就是 (...) + (...) or (...) - (...) or (...) * (...)
而括號裡面,也可以再用這種方式再去切分
所以可以想成是 binary tree 的資料結構
每當遇到運算符號,就去切分成左右兩段,找到計算的值後,再一個merge回來
kotlin(參考解答)
沒有留言:
張貼留言