d***8
发帖数: 1552 | 1 put operators in a list of numbers so that the result equals to a
number. Give you an array of integers, ask you to write program to put
operators (+ - * / %) between the integers (you may put in paratheis
wherever you want too), to have the equation equals to the result.
eg: 5 * (3 + 8) % 9 = 6
题目是:给你一串数字，让你写程序，把操作符（可以是任意多个 + - * / %）放进各
个数字之
间，同时还可以在任意位置放进括号，让这个算术表达式的值等于一个给定的数字。
比如：给你 5 3 8 9 = 6
你的程序应该输出 5 * (4 + 8) % 9 = 6 | B*****g
发帖数: 34098 | 2 俺只会穷举。
【在 d***8 的大作中提到】
: put operators in a list of numbers so that the result equals to a
: number. Give you an array of integers, ask you to write program to put
: operators (+ - * / %) between the integers (you may put in paratheis
: wherever you want too), to have the equation equals to the result.
: eg: 5 * (3 + 8) % 9 = 6
: 题目是:给你一串数字，让你写程序，把操作符（可以是任意多个 + - * / %）放进各
: 个数字之
: 间，同时还可以在任意位置放进括号，让这个算术表达式的值等于一个给定的数字。
: 比如：给你 5 3 8 9 = 6
: 你的程序应该输出 5 * (4 + 8) % 9 = 6
| g*********s
发帖数: 1782 | 3 the order of number is fixed?
looks like a brute force. first construct a tree with these numbers as
leaf node and unknown operators as internal node. then traverse it.
【在 d***8 的大作中提到】
: put operators in a list of numbers so that the result equals to a
: number. Give you an array of integers, ask you to write program to put
: operators (+ - * / %) between the integers (you may put in paratheis
: wherever you want too), to have the equation equals to the result.
: eg: 5 * (3 + 8) % 9 = 6
: 题目是:给你一串数字，让你写程序，把操作符（可以是任意多个 + - * / %）放进各
: 个数字之
: 间，同时还可以在任意位置放进括号，让这个算术表达式的值等于一个给定的数字。
: 比如：给你 5 3 8 9 = 6
: 你的程序应该输出 5 * (4 + 8) % 9 = 6
| d***8
发帖数: 1552 | 4 yes, the order of number is fixed.
具体怎么建tree呢？然后怎么穷举？
as
【在 g*********s 的大作中提到】
: the order of number is fixed?
: looks like a brute force. first construct a tree with these numbers as
: leaf node and unknown operators as internal node. then traverse it.
| d***8
发帖数: 1552 | 5 俺只会穷举各个操作符的排列顺序，
怎么穷举括号的位置呢？
【在 B*****g 的大作中提到】
: 俺只会穷举。
| d***8
发帖数: 1552 | | r******e
发帖数: 80 | 7 穷举法。 用postfix， 从第二个数字开始，进行5个符号的排列。 如果有n 个数字，
复杂度是 5^(n-1). 就是比较慢 | b*m
发帖数: 34 | 8 似乎用树的穷举并不完备。
比如 （a+b）*（d+e） 可以被穷举到
但是 （a+b）*d+e 用简单的leaf 和internal node tree 还是没法实现。
还是要考虑括号的实现。
，
【在 r******e 的大作中提到】
: 穷举法。 用postfix， 从第二个数字开始，进行5个符号的排列。 如果有n 个数字，
: 复杂度是 5^(n-1). 就是比较慢
| b*m
发帖数: 34 | 9 可以考虑 把 括号当作 leaf node 穷举得插入进去原有的leaf node 之间在读取树的
leaf node 的时候
【在 b*m 的大作中提到】
: 似乎用树的穷举并不完备。
: 比如 （a+b）*（d+e） 可以被穷举到
: 但是 （a+b）*d+e 用简单的leaf 和internal node tree 还是没法实现。
: 还是要考虑括号的实现。
:
: ，
| i**********e
发帖数: 1145 | 10 There are only 5 different kinds of expressions with different arrangement
of parenthesis for 4 numbers (using an example of 1,2,3,4), shown as below:
1) ((1 + 2) + (3 + 4))
2) (((1 + 2) + 3) + 4)
3) ((1 + (2 + 3)) + 4)
4) (1 + ((2 + 3) + 4))
5) (1 + (2 + (3 + 4)))
An easy way is to brute force using recursive method. Choose all possible
neighboring pairs and merge them using the operators (add, subtract...). For
example, choosing neighboring pairs of (1 and 2):
(1 + 2) + 3 + 4 --> 3 + 3 + 4
Similarly, choosing neighboring pairs of (2 and 3):
1 + (2 + 3) + 4 --> 1 + 5 + 4
Now the problem becomes generating all possible arrangement of parenthesis
of 3 numbers, and so on... until 1 number is left, which is the final answer.
The problem with this approach is possibility of duplicates being generated.
For example, this method would generate duplicates of the following
arrangement:
(1 + 2) + (3 + 4)
This is because it is possible for the algorithm to choose pair(1,2) as the
first pair to merge with pair(3,4) as the next pair to merge. The duplicate
would be generated by choosing pair(3,4) as the first pair to merge, and
pair(1,2) as the next pair to merge.
An easy way to resolve this is to use a set to store the answers in order to avoid
duplicates. But it wouldn't be efficient to go through all the unnecessary paths, right?
A better way would be to brute force the smart way by avoiding the duplicate
arrangements. This method is actually not too far away from the above
approach. Think and see if you can find a way to avoid the duplicates with
minor adjustment to the above algorithm.
The next challenge is how to print out the answers' expression. Initially, I
thought of using strings to store the expression but it is not very
efficient and troublesome to manipulate. I believe that storing the expression using stack-based postfix
method will be more efficient.
An interesting side note:
The total number of parenthesis arrangements is actually described by the
Catalan number:
http://en.wikipedia.org/wiki/Catalan_number
For example, the first five catalan numbers are:
1, 1, 2, 5, 14, ...
So, we can expect there would be 14 unique parenthesis arrangements for 5
numbers.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | i**********e
发帖数: 1145 | 11 刚想到很精简的 code，不需要用 post-fix stack-based expression，直接储存进一
个 string 数组即可。
效率应该是不错的了，有一些方面可以考虑提高效率，例如用 vector 需要删除元素可
能会慢些，但 vector 里的元素很少，应该影响不大。
还有一点就是每次传递归的时候，都需要把所有的数组重新 copy 一次。这是无可避免
的，因为每次进入下一层递归时必须传 copy，不能在原有数组中更改。
#include
#include
#include
#include
#include
using namespace std;
void generate(vector A, int target, int s, vector expression);
template
void eraseAt(vector &vec, int i) {
typename vector::iterator iter = vec.begin();
for (int j = 0; j < i; j++)
iter++;
vec.erase(iter);
}
void generateHelper(char oper, int result, vector A, int target, int i,
vector expression) {
// Replace both ith and (i+1)th elements with result
A[i] = result;
eraseAt(A, i+1); // erase the (i+1)th element
// Similar with expression, combine both ith and (ith)th expression
expression[i] = "(" + expression[i] + " " + oper + " " + expression[i+1] +
")";
eraseAt(expression, i+1);
generate(A, target, ((i <= 0) ? 0 : i-1), expression);
}
int total = 0;
void generate(vector A, int target, int s, vector expression) {
int n = A.size();
if (n == 1 && A[0] == target) {
assert(expression.size() == 1); // expressions combined to one
total++;
cout << expression[0] << " = " << target << endl;
return;
}
for (int i = s; i < n-1; i++) {
int x = A[i];
int y = A[i+1];
generateHelper('+', x+y, A, target, i, expression);
generateHelper('-', x-y, A, target, i, expression);
generateHelper('*', x*y, A, target, i, expression);
/*if (y != 0) {
generateHelper('%', x%y, A, target, i, expression);
//generateHelper('/', x/y, A, target, i, expression);
}*/
}
}
void printExpressionEqualTo(vector A, int target) {
int n = A.size();
assert(n > 0);
vector expression;
ostringstream outstr;
// convert integer to its string equivalent
for (int i = 0; i < n; i++) {
outstr.str("");
outstr << A[i];
expression.push_back(outstr.str());
}
generate(A, target, 0, expression);
}
int main() {
vector A;
int target = 720;
A.push_back(1);
A.push_back(2);
A.push_back(3);
A.push_back(4);
A.push_back(5);
A.push_back(6);
// A.push_back(7);
printExpressionEqualTo(A, target);
cout << endl << "Total arrangements: " << total << endl;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | i**********e
发帖数: 1145 | 12 顶.
不知道还有没有其他方法呢？（尤其可以避免每次递归制造额外的 copy）
还有一点就是，以上的方法会列出，但其实在加法没有括号的必要。
((1+2)+3)
(1+(2+3))
要怎么列出绝对 unique 的 arrangements 呢？
感觉会很复杂，很多情况要处理。
大家讨论讨论吧。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | P********l
发帖数: 452 | 13 me too.
【在 B*****g 的大作中提到】
: 俺只会穷举。
|
|
