n*******s
发帖数: 482 | 1 Given four number a0, a1, a2, a3,..., ak
Find all possible expression to using + - * / with any '(',')' to generate a
result equals to target X.
上来就想了
1. 数字permutation （k！种）
2. 然后在数字之间插operator ： +-*/ （k-1 spaces， total possibility 4^(k-1
))
3. 加括号，就是生成所有叶子数为k的树，简单起见就是用binary tree了
List GenTree(oprand[s..e])
{
List allTress = new List();
if(s==e)
allTrees.add(new Node(s));
return allTrees.
for i=s to e-1:
Node root = GenRoot(s, e, i)
List leftSubTrees = GenTree(oprand[s, i])
List rightSubTrees = GenTree(oprand[i+1, e])
allTress.addAll(GenFullTree(root, leftSubTrees,rightSubTrees)
return allTrees.
}
求结果就是post order traversal.
暴力解法有太多的重复计算了，求此题目简洁解法。 | l********r
发帖数: 29 | 2 递归啊。。这个题怎么是permutation。。
X +，-，×，/ ak，
然后用A1.。。。 Ak-1凑不同的结果
（）就是用来提高优先级用的，可以无视
a
-1
【在 n*******s 的大作中提到】
: Given four number a0, a1, a2, a3,..., ak
: Find all possible expression to using + - * / with any '(',')' to generate a
: result equals to target X.
: 上来就想了
: 1. 数字permutation （k！种）
: 2. 然后在数字之间插operator ： +-*/ （k-1 spaces， total possibility 4^(k-1
: ))
: 3. 加括号，就是生成所有叶子数为k的树，简单起见就是用binary tree了
: List GenTree(oprand[s..e])
: {
| n*******s
发帖数: 482 | 3 补充一下 在最后的结果表达式中，数字的顺序随便(但必须k个都用到)，操作符的选择
和顺序随便，括号
的选择随便，但要合法。
楼上说的递归，没错，在这个题目里backtracking本质上就是permutation，不是么.
另外 在无括号的情况下，backtracking求表达式很好写，但是有括号呢？ | s*******z
发帖数: 83 | 4 题目中的运算符有优先级的吗? 还是顺序运算过去就行了?
没有的话,
X = A1/A2 + A3*A4
貌似不能从
X/A4来反推.
感觉可以记忆化起来, 但是这个地方怎么存Key有点费思量了. | w*******s
发帖数: 138 | 5 每次从k中选两个数，枚举+,-,*,/四种操作，这样k个数就变成k-1个数了，递归枚举到
只剩下一个数即为结果。
【在 n*******s 的大作中提到】
: 补充一下 在最后的结果表达式中，数字的顺序随便(但必须k个都用到)，操作符的选择
: 和顺序随便，括号
: 的选择随便，但要合法。
: 楼上说的递归，没错，在这个题目里backtracking本质上就是permutation，不是么.
: 另外 在无括号的情况下，backtracking求表达式很好写，但是有括号呢？
| b*****9
发帖数: 89 | 6 括号是不是如果当前操作符是乘除就自动给后面出来的表达式加个括号？a * ( rest )
【在 n*******s 的大作中提到】
: 补充一下 在最后的结果表达式中，数字的顺序随便(但必须k个都用到)，操作符的选择
: 和顺序随便，括号
: 的选择随便，但要合法。
: 楼上说的递归，没错，在这个题目里backtracking本质上就是permutation，不是么.
: 另外 在无括号的情况下，backtracking求表达式很好写，但是有括号呢？
| n*******s
发帖数: 482 | 7 有括号呢
【在 w*******s 的大作中提到】
: 每次从k中选两个数，枚举+,-,*,/四种操作，这样k个数就变成k-1个数了，递归枚举到
: 只剩下一个数即为结果。
| n*******s
发帖数: 482 | 8 不是的，这里考察所有可能合法的括号 会生成的所有结果。
)
【在 b*****9 的大作中提到】
: 括号是不是如果当前操作符是乘除就自动给后面出来的表达式加个括号？a * ( rest )
| g*****g
发帖数: 212 | 9 没错，基本上就是暴力组合各种表达式
在表达式最后求值。
void allexpressions(vector &num, vector &exps, vector &
ret, int target)
{
int n =num.size();
for(int i=0; i
{
swap(num, 0,i);
exps.push_back(""+i);
allexpressions(num, 1, n, exps, ret, target);
exps.pop_back();
swap(num, 0,i);
}
}
void caculateExpressions(vector &exps, vector &ret, int
target)
{
}
void allexpressions(vector &num, int s ,int n, vector &exps
, vector &ret, int target)
{
static string ops[4] = {"+", "-", "*", "/"};
if (s == n)
{
caculateExpressions(exps, ret, target);
}
for(int i=s; i
{
swap(num, i, s);
vector nexps;
for(int j=0; j
{
for(int k=0; k<4; k++)
{
string vstr = combine(ops[k], num[i]);
nexps.push_back(exps[j]+vstr);
nexps.push_back("("+exps[j]+vstr+")");
int cnt = 0;
for(int l =exps[j].length()-1; l>=0; l--)
{
// not number
if (exps[j][l] >'9' || exps[j][l] < '0')
{
if (exps[j][l] == ')')
{
cnt++;
}
else if (exps[j][l] == '(')
{
cnt--;
}
else // ops
{
if (cnt == 0) // start pos of '('
{
nexps.push_back(exps[j].substr(0, l) +
exps[j][l] +"(" +vstr+")");
}
}
}
}
}
}
allexpressions(num, i+1, n, nexps, ret, target);
swap(num, i, s);
}
}
【在 n*******s 的大作中提到】
: 补充一下 在最后的结果表达式中，数字的顺序随便(但必须k个都用到)，操作符的选择
: 和顺序随便，括号
: 的选择随便，但要合法。
: 楼上说的递归，没错，在这个题目里backtracking本质上就是permutation，不是么.
: 另外 在无括号的情况下，backtracking求表达式很好写，但是有括号呢？
| w*******s
发帖数: 138 | 10 已经处理了呀，没有括号只要排列加枚举算符
【在 n*******s 的大作中提到】
: 有括号呢
| | | x****g
发帖数: 1512 | 11 这个思路应该是正确方向。
取2个数，用+-*/操作，注意-/有2个方向，把结果放回剩下的k-2变成k-1子问题递归。
不过/如果不是整形操作，中间结果是浮点的话，精度损失又是个问题。
面试真是苦逼没用的事，遇上这种题，估计10有9挂，恶心啊。
【在 w*******s 的大作中提到】
: 每次从k中选两个数，枚举+,-,*,/四种操作，这样k个数就变成k-1个数了，递归枚举到
: 只剩下一个数即为结果。
| w*******s
发帖数: 138 | 12 用分数处理就可以了
【在 x****g 的大作中提到】
: 这个思路应该是正确方向。
: 取2个数，用+-*/操作，注意-/有2个方向，把结果放回剩下的k-2变成k-1子问题递归。
: 不过/如果不是整形操作，中间结果是浮点的话，精度损失又是个问题。
: 面试真是苦逼没用的事，遇上这种题，估计10有9挂，恶心啊。
| x****g
发帖数: 1512 | 13 详解？
【在 w*******s 的大作中提到】
: 用分数处理就可以了
| w*******s
发帖数: 138 | 14 自己写个分数类，或者用一些直接有标准库可以用，比如python的fractions
【在 x****g 的大作中提到】
: 详解？
| x****g
发帖数: 1512 | 15 哦，不熟悉这个，粗略看了下。
就是存分子/分母，完了简化可走最大公约数。+/-需要有最大公背数操作。
为了递归，把所有数都变成分数对象。
该类是不是还要考虑溢出.....?
另外：这个取2完了递归，算法本身如何去重？
【在 w*******s 的大作中提到】
: 自己写个分数类，或者用一些直接有标准库可以用，比如python的fractions
| w*******s
发帖数: 138 | 16 实现高精度运算就可应付溢出，或者直接使用有标准库的，python/ruby/java都有
去重需要先表达式分析去冗余括号，然后排序
【在 x****g 的大作中提到】
: 哦，不熟悉这个，粗略看了下。
: 就是存分子/分母，完了简化可走最大公约数。+/-需要有最大公背数操作。
: 为了递归，把所有数都变成分数对象。
: 该类是不是还要考虑溢出.....?
: 另外：这个取2完了递归，算法本身如何去重？
| b*****9
发帖数: 89 | 17 那就不仅乘除加括号，加减也后面可以加上括号应该就行了吧？
【在 n*******s 的大作中提到】
: 不是的，这里考察所有可能合法的括号 会生成的所有结果。
:
: )
| g*********e
发帖数: 14401 | 18 这样算不到(1*2)+(3*4)
【在 w*******s 的大作中提到】
: 每次从k中选两个数，枚举+,-,*,/四种操作，这样k个数就变成k-1个数了，递归枚举到
: 只剩下一个数即为结果。
|
|
