当前位置:网站首页>Force deduction solution summary 241- design priority for operation expression
Force deduction solution summary 241- design priority for operation expression
2022-07-22 19:32:00 【Lost summer】
Directory links :
Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog
GitHub Synchronous question brushing items :
https://github.com/September26/java-algorithms
Original link : Power button
describe :
Give you a string of numbers and operators expression , Combine numbers and operators according to different priorities , Calculate and return the results of all possible combinations . You can In any order Return to the answer .
The generated test case meets its corresponding output value in line with 32 Bit integer range , The number of different results does not exceed 104 .
Example 1:
Input :expression = "2-1-1"
Output :[0,2]
explain :
((2-1)-1) = 0
(2-(1-1)) = 2
Example 2:
Input :expression = "2*3-4*5"
Output :[-34,-14,-10,-10,10]
explain :
(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
Tips :
1 <= expression.length <= 20
expression By numbers and operators '+'、'-' and '*' form .
All integer values in the input expression are in the range [0, 99]
source : Power button (LeetCode)
link :https://leetcode.cn/problems/different-ways-to-add-parentheses
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Their thinking :
* Their thinking : * My thinking efficiency is still relatively low . * This problem has nothing to do with symbols , It's the process of pairing each other . * So my idea is to split values and symbols first , Divided into two sets , Then start recursive calculation . * Each time we traverse the set of values , Then select two adjacent ones for calculation , Then form a new set to enter the next cycle . In this way, each traversal is less than one value , When set length 1 when , Indicates the end of the traversal .
Code :
public class Solution241 {
Map<String, Integer> map = new HashMap<>();
public List<Integer> diffWaysToCompute(String expression) {
List<String> valueList = new ArrayList<>();
List<String> symbolList = new ArrayList<>();
char[] chars = expression.toCharArray();
StringBuilder builder = new StringBuilder();
for (int i = 0; i <= chars.length; i++) {
if (i == chars.length) {
valueList.add(builder.toString());
break;
}
char aChar = chars[i];
if (aChar == '+' || aChar == '-' || aChar == '*') {
valueList.add(builder.toString());
symbolList.add(String.valueOf(aChar));
builder.setLength(0);
} else {
builder.append(aChar);
}
}
List<Integer> sumList = new ArrayList<>();
for (String s : valueList) {
sumList.add(Integer.parseInt(s));
}
search(sumList, valueList, symbolList);
return new ArrayList<>(map.values());
}
private void search(List<Integer> sumList, List<String> valueList, List<String> symbolList) {
if (valueList.size() == 1) {
String s = valueList.get(0);
// The result of the calculation is
map.put(s, sumList.get(0));
return;
}
for (int i = 0; i < valueList.size() - 1; i++) {
ArrayList<String> newList = new ArrayList<>(valueList);
ArrayList<Integer> newNumList = new ArrayList<>(sumList);
String remove = newList.remove(i);
Integer leftValue = newNumList.remove(i);
String s = newList.get(i);
Integer rightValue = newNumList.get(i);
String symbol = symbolList.get(i);
newList.set(i, "(" + remove + symbol + s + ")");
if (symbol.equals("+")) {
newNumList.set(i, leftValue + rightValue);
} else if (symbol.equals("-")) {
newNumList.set(i, leftValue - rightValue);
} else {
newNumList.set(i, leftValue * rightValue);
}
symbolList.remove(i);
search(newNumList, newList, symbolList);
symbolList.add(i, symbol);
}
}
}
边栏推荐
- Don't let fear of marriage kill your happiness!
- Idea Quick Start Guide
- Leetcode daily question 2022/3/14-2022/3/20
- Help brand insight -- Analysis of consumers' emotional behavior
- LeetCode 每日一题 2022/3/14-2022/3/20
- LeetCode 每日一题 2021/11/29-2021/12/5
- Leetcode daily question 2022/1/10-2022/1/16
- Execute function now
- Rongyun x Xingzhi: exclusive Post-00 self social plot (including lottery)
- Mysql5.7 decompression configuration steps
猜你喜欢
Matlab plot子图的间距和边缘距离如何调整(已解决)
融云漫话:没有一个人躲得过“视频会议”
融云首席科学家任杰:历练出人才,职场「经历>经验」
MFC对话框程序只运行单个实例 的简单示例
Scenario practice | how to use rongyun super group to build a game community
DOM introduction and query
Batch check crawler
音频 3A 处理实践,让你的应用更「动听」
Several trends in the future development of software industry
融云 x 幸识: 专属 00 后的真我社交自留地(内含抽奖)
随机推荐
Leetcode daily question 2022/2/7-2022/2/13
JS advanced - understanding of functions
Force deduction solution summary 1108-ip address invalidation
4G工业路由器大气环境监测方案
Terminal data protection of Internet communication security
场景实践 | 如何使用融云超级群构建游戏社区
Oracle容器数据库的安装和使用
为什么重写equels方法一定要重写hashCode方法
Fluent adjusts the drawing shape by dragging
Methods of wrapping classes and strings
Industrial router oilfield wireless monitoring
Leetcode: 627. Change gender
DOM introduction and query
MySQL optimization enforces the use of indexes
LeetCode 每日一题 2022/2/14-2022/2/20
Constructor
A practical example of the go pipeline pattern -- calculating the MD5 value of a series of files
grafana面板-覆盖字段值
Leetcode daily question 2022/2/28-2022/3/6
Installation and use of Oracle container database