当前位置:网站首页>2022.7.1-----leetcode. two hundred and forty-one
2022.7.1-----leetcode. two hundred and forty-one
2022-07-02 19:19:00 【Lu 727】
// Three operators
static final int ADDITION = -1;
static final int SUBTRACTION = -2;
static final int MULTIPLICATION = -3;
public List<Integer> diffWaysToCompute(String expression) {
List<Integer> ops = new ArrayList<Integer>();
// Split expressions into numbers and operators
for (int i = 0; i < expression.length();) {
if (!Character.isDigit(expression.charAt(i))) {
if (expression.charAt(i) == '+') {
ops.add(ADDITION);
} else if (expression.charAt(i) == '-') {
ops.add(SUBTRACTION);
} else {
ops.add(MULTIPLICATION);
}
i++;
} else {
int t = 0;
while (i < expression.length() &&Character.isDigit(expression.charAt(i)))
{
t = t * 10 + expression.charAt(i) - '0';
i++;
}
ops.add(t);
}
}
// Record [l,r] Result of expression
List<Integer>[][] dp = new List[ops.size()][ops.size()];
for (int i = 0; i < ops.size(); i++) {
for (int j = 0; j < ops.size(); j++) {
dp[i][j] = new ArrayList<Integer>();
}
}
return dfs(dp, 0, ops.size() - 1, ops);
}
public List<Integer> dfs(List<Integer>[][] dp, int l, int r, List<Integer> ops) {
// Non empty indicates that the expression has been solved
if (dp[l][r].isEmpty()) {
if (l == r) {
dp[l][r].add(ops.get(l));// There's only one number
} else {
// By the end of i+1 Bit operator is split , Solve in the left and right sub formulas respectively
for (int i = l; i < r; i += 2) {
List<Integer> left = dfs(dp, l, i, ops);
List<Integer> right = dfs(dp, i + 2, r, ops);
// This operator is the last step , The left and right subformulas should combine all possible results in pairs
for (int lv : left) {
for (int rv : right) {
if (ops.get(i + 1) == ADDITION) {
dp[l][r].add(lv + rv);
} else if (ops.get(i + 1) == SUBTRACTION) {
dp[l][r].add(lv - rv);
} else {
dp[l][r].add(lv * rv);
}
}
}
}
}
}
return dp[l][r];
}
边栏推荐
- R语言ggplot2可视化:可视化折线图、使用labs函数为折线图添加自定义的X轴标签信息
- mybatiesHelperPro工具必须的可以生成到对应项目文件夹下
- Emmet基础语法
- Imitation Jingdong magnifying glass effect (pink teacher version)
- Preprocessing and preprocessing macros
- Fastdfs installation
- 高频面试题
- How to delete the border of links in IE? [repeat] - how to remove borders around links in IE? [duplicate]
- QT中的QPropertyAnimation使用和toast案列
- Tutorial (5.0) 09 Restful API * fortiedr * Fortinet network security expert NSE 5
猜你喜欢
论文导读 | 关于将预训练语言模型作为知识库的分析与批评
PyTorch函数中的__call__和forward函数
codeforces每日5题(均1700)-第四天
How can retail enterprises open the second growth curve under the full link digital transformation
Why should we build an enterprise fixed asset management system and how can enterprises strengthen fixed asset management
Mysql高级篇学习总结7:Mysql数据结构-Hash索引、AVL树、B树、B+树的对比
【JVM调优实战100例】01——JVM的介绍与程序计数器
新手必看,點擊兩個按鈕切換至不同的內容
新手必看,点击两个按钮切换至不同的内容
潇洒郎:彻底解决Markdown图片问题——无需上传图片——无需网络——转发给他人图片无缺失
随机推荐
Learning summary of MySQL advanced 6: concept and understanding of index, detailed explanation of b+ tree generation process, comparison between MyISAM and InnoDB
How to play when you travel to Bangkok for the first time? Please keep this money saving strategy
Thread application instance
Golang并发编程——goroutine、channel、sync
Yunna | why use the fixed asset management system and how to enable it
What is 9D movie like? (+ common sense of dimension space)
守望先锋世界观架构 ——(一款好的游戏是怎么来的)
Imitation Jingdong magnifying glass effect (pink teacher version)
页面标题组件
Obligatoire pour les débutants, cliquez sur deux boutons pour passer à un contenu différent
[test development] software testing - concept
The R language dplyr package rowwise function and mutate function calculate the maximum value of multiple data columns in each row in the dataframe data, and generate the data column (row maximum) cor
PyTorch函数中的__call__和forward函数
ORA-01455: converting column overflows integer datatype
横向越权与纵向越权[通俗易懂]
"Patient's family, please come here" reading notes
Mysql高级篇学习总结7:Mysql数据结构-Hash索引、AVL树、B树、B+树的对比
[daily question] the next day
线程应用实例
2022 compilation principle final examination recall Edition