LeetCode OJ ： Different Ways to Add Parentheses（在不同位置增加括号的方法）
2024-09-24 22:31:24
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]
这里的主要思想是讲左右的子串分别算出来之后，再做全排列就行了，可能有很所重复计算所以说效率比较低
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> result;
int length = input.length();
for(int i = ; i < length; ++i){
char c = input[i];
if(c == '+' || c == '-' || c == '*'){
string inputLeft = input.substr(, i);
string inputRight = input.substr(i+);
vector<int>leftResult = diffWaysToCompute(inputLeft);
vector<int>rightResult = diffWaysToCompute(inputRight);
for(int j = ; j < leftResult.size(); ++j){
for(int k = ; k < rightResult.size(); ++k){
if(c == '+')
result.push_back(leftResult[j] + rightResult[k]);
else if(c == '-')
result.push_back(leftResult[j] - rightResult[k]);
else if(c == '*')
result.push_back(leftResult[j] * rightResult[k]);
}
}
}
}
if(result.empty())//这一步主要的作用是讲分治得到的最后的字符转换成数字
result.push_back(stoi(input));
return result;
}
};
java版本如下所示：
public class Solution {
public List<Integer> diffWaysToCompute(String input) {
ArrayList<Integer> ret = new ArrayList<Integer>();
for(int i = 0; i < input.length(); ++i){
char c = input.charAt(i);
if(c == '+' || c == '-' || c == '*'){
List<Integer> leftRet = diffWaysToCompute(input.substring(0, i));
List<Integer> rightRet = diffWaysToCompute(input.substring(i+1, input.length()));
for(int left : leftRet){
for(int right : rightRet){
if(c == '+'){
ret.add(left + right);
}else if(c == '-'){
ret.add(left - right);
}else{
ret.add(left * right);
}
}
}
}
}
if(ret.isEmpty()){
ret.add(Integer.parseInt(input));
}
return ret;
}
}
最新文章
- 《Unix/Linux网络日志分析与流量监控》获2015年度最受读者喜爱的IT图书奖
- c语言冒泡排序
- android java substring说明
- centos 服务器内存管理
- JavaScript 全栈工程师培训教程(来自阮一峰)
- Leetcode 86. Unique Binary Search Trees
- ubuntu下安装TexLive和Texmaker
- Android GPS 临近触发
- HMMPfam的安装使用手记（转载）
- PagerSlidingTabStrip 高亮选中标题
- Web挖掘技术
- JavaScript 判断对象是否为空
- hdu 3309 Roll The Cube ( bfs )
- 对SVN的落地与实践总结
- base标签浏览器兼容问题
- 基于 Python 和 Pandas 的数据分析(6) --- Joining and Merging
- 【leetcode】121-Best Time to Buy and Sell Stock
- JOffice中的权限管理--功能粒度的权限管理配置
- 子域名枚举工具Sublist3r
- 设计模式之装饰模式（iOS开发，代码用Objective-C展示）