tag: 分治
对于一个形如 x op y(op 为运算符,x 和 y 为数) 的算式而言,它的结果组合取决于 x 和 y 的结果组合数,而 x 和 y 又可以写成形如 x op y 的算式。
因此,该问题的子问题就是 x op y
中的 x
和 y
:以运算符分隔的左右两侧算式解。
进行 分治算法三步走:
分解:按运算符分成左右两部分,分别求解
解决:实现一个递归函数,输入算式,返回算式解
合并:根据运算符合并左右两部分的解,得出最终解
ac代码(复杂度有点高……):
/**
* @param {string} input
* @return {number[]}
*/
var diffWaysToCompute = function(input) {
const isNumber = (input) => {
return /^\d+$/.test(input);
}
if(isNumber(input)) return [Number(input)];
let res = [], len=input.length;
const calc = (n1, n2, op) => {
switch(op){
case '+':
return n1+n2;
case '-':
return n1-n2;
case '*':
return n1*n2;
}
}
for(let i = 0; i < len; i++){
if(!isNumber(input[i])){
let left = diffWaysToCompute(input.substring(0, i));
let right = diffWaysToCompute(input.substring(i+1, len));
for(l of left){
for(r of right)
res = [...res, calc(l, r, input[i])];
}
}
}
return res;
};
第一次用js写题,记录几点:
-
用edge的console比较方便,单独的一个窗口
-
判断纯字符串是否是纯数字字符串:
(input) => {return /^\d+$/.test(input);
-
在字符串末尾添加元素的两种方式(肯定还有更多,但是这次就接触这两种:
[1,2,3].push(4) -> [1,2,3,4]
arr = [...arr, 4]
-
返回纯数字时记得要用[ ]包裹,不然就不iterable
-
注意一下js的写题的写法,挺有特色的