【LeetCode】241. Different Ways to Add Parentheses
2024-10-10 17:17:03
Different Ways to Add Parentheses
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are+
, -
and *
.
Example 1
Input: "2-1-1"
.
((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]
Example 2
Input: "2*3-4*5"
(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
Output: [-34, -14, -10, -10, 10]
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
与Unique Binary Search Trees II思路类似,可以对照看。
本题参考Gcdofree的做法
左右子串分别计算所有可能,然后全排列。
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> ret;
for(int i = ; i < input.size(); i ++)
{
if(input[i] == '+' || input[i] == '-' || input[i] == '*')
{
vector<int> left = diffWaysToCompute(input.substr(, i));
vector<int> right = diffWaysToCompute(input.substr(i+));
for(int j = ; j < left.size(); j ++)
{
for(int k = ; k < right.size(); k ++)
{
if(input[i] == '+')
ret.push_back(left[j] + right[k]);
else if(input[i] == '-')
ret.push_back(left[j] - right[k]);
else
ret.push_back(left[j] * right[k]);
}
}
}
}
if(ret.empty())
ret.push_back(atoi(input.c_str()));
return ret;
}
};
最新文章
- js document.createElement()的用法 (转)
- HDU 1106 排序 题解
- php dirname(__FILE__) 获取当前文件的绝对路径 (转)
- lazyload.js详解
- .NET设计模式(12):外观模式(Fa&#231;ade Pattern)(转)
- React Native学习-调取摄像头第三方组件:react-native-image-picker
- cocos2d_随手篇1_关于ccTouchBegan的调用
- CALayer -- 备忘
- Android应用开发学习之图片切换器
- 打开SQL Server 配置管理器时出现了问题
- javascript深入理解js闭包(看了挺多的,感觉这篇比较透彻)
- angular.js之作用域scope&#39;@&#39;,&#39;=&#39;,&#39;&;&#39;
- CentOS7+CDH5.14.0安装全流程记录,图文详解全程实测-5安装JDK及安装mysql数据库
- Eclipse的设置
- vi中换行、翻页和查找功能
- cmd 查看端口
- [Oracle]PDB Clone 方法
- eclipse引入系统类库
- lambda,reduce,filter用法
- XAML实时显示更新插件LiveXAML