Leetcode282.|Leetcode282. Expression Add Operators
Analysis
Oveiously, in order to solve this question, we have to iterate through all of the possible cases at least once. DFS can be used to solve the iteration process.
The optimization we could made it to prune the unnecessary branches, e.g. there is not need to try 0 sequences longer than 1, because this is not a natural number.
And also, like always, we have to take into consideration the overflow problem for a integer-related calculation.
In addition, we have to also deal the the multiplication case differently since multiplicaiton operation has a higher priority than plus and minus. Thus if a multiplication shows up latter, we have to change the calculation sequence in our result. E.g. when we get "2+3" in the previous search and we want to check "2+35" in the next step, we have to first subtract 3 from "2+3" and then add "35" to the result.
Time complexity:
Considering for every digit 0-9 in the number, we have 4 possible operator that can be assigned between them -- +, -, '*andjoin, which means the previous digit and current digit will combined to become 1 number, e.g.2 join 3will be23`.
【Leetcode282.|Leetcode282. Expression Add Operators】Based on the fact that there are n digits in total, there are O(4^n) possible cases that we need to check. Hence the time complexity of the program is O(4^n).
Implementation in Java:
class Solution {
public List addOperators(String num, int target) {
List res = new ArrayList<>();
if (num == null || num.length() == 0) {
return res;
}addOperators(res, "", num, target, 0, 0, 0);
return res;
}private void addOperators(List res, String path, String num, int target, int start, long eval, long nextMulted) {
if (start == num.length()) {
if (eval == target) {
res.add(path);
return;
}
}
for (int i = start;
i < num.length();
i++) {
if (i != start && num.charAt(start) == '0') {
break;
}
long curr = Long.parseLong(num.substring(start, i + 1));
if (start == 0) {
addOperators(res, path + curr, num, target, i + 1, curr, curr);
} else {
addOperators(res, path + "+" + curr, num, target, i + 1, eval + curr, curr);
addOperators(res, path + "-" + curr, num, target, i + 1, eval - curr, -curr);
addOperators(res, path + "*" + curr, num, target, i + 1, eval - nextMulted + nextMulted * curr, nextMulted * curr);
}
}
}
}
推荐阅读
- paddle|动手从头实现LSTM
- Swift|Swift ----viewController 中addChildViewController
- paddlepaddle|paddlepaddle操作(一)
- 嵌入式电脑|Paddle Inference——基于python API在Jetson上部署PaddleSeg模型
- 龙马UI|龙马UI lm-ui-elementl lm-address地址组件
- Unable|Unable to add window -- token null is not valid; is your activity running?
- linux如何查看ip地址
- JAVA并发编程——原子操作类以及LongAdder源码分析
- 原生js事件简化
- bash|bash 源码 分析