[G] 给定k个数字，求所有表达式结果为X - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

[G] 给定k个数字，求所有表达式结果为X

[G] 给定k个数字，求所有表达式结果为X# JobHunting - 待字闺中

y*u2014-01-14 08:01

1 楼

现在淘宝的全球购频道交易额最大的是什么类目?
记得是交易额不是交易量。
记得是全球购频道（也就是代购频道）不是整体淘宝
5选一
1：数码手机
2：笔记本电脑
3：包包
4：化妆品
5：母婴产品
答对的前3人每人10个包子伺候

a*s2014-01-14 08:01

2 楼

costco看到三种
focusfacor,据说补脑,但不甜 $39
lilcritters calcium 骨发育 $10+
lilcritters gummy vites 眼发育 $10+
哪种合适？thanks

n*s2014-01-14 08:01

3 楼

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.
暴力解法有太多的重复计算了，求此题目简洁解法。

s*x2014-01-14 08:01

4 楼

4：化妆品

m*n2014-01-14 08:01

5 楼

为什么要给孩子吃这种东西？

【在 a**s 的大作中提到】

: costco看到三种
: focusfacor,据说补脑,但不甜 $39
: lilcritters calcium 骨发育 $10+
: lilcritters gummy vites 眼发育 $10+
: 哪种合适？thanks

l*r2014-01-14 08:01

6 楼

递归啊。。这个题怎么是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])
: {

w*i2014-01-14 08:01

7 楼

4：化妆品

n*12014-01-14 08:01

8 楼

自己做吧，放心

n*s2014-01-14 08:01

9 楼

补充一下在最后的结果表达式中，数字的顺序随便(但必须k个都用到)，操作符的选择
和顺序随便，括号
的选择随便，但要合法。
楼上说的递归，没错，在这个题目里backtracking本质上就是permutation，不是么.
另外在无括号的情况下，backtracking求表达式很好写，但是有括号呢？

b*a2014-01-14 08:01

10 楼

d*72014-01-14 08:01

11 楼

小孩最好别吃这些东西，不健康。多吃水果吧，可以榨成果汁。

s*z2014-01-14 08:01

12 楼

题目中的运算符有优先级的吗? 还是顺序运算过去就行了?
没有的话,
X = A1/A2 + A3*A4
貌似不能从
X/A4来反推.
感觉可以记忆化起来, 但是这个地方怎么存Key有点费思量了.

y*u2014-01-14 08:01

13 楼

我刷牙吃饭回来...

a*s2014-01-14 08:01

14 楼

哦，看到好像不少家庭都买...

【在 d****7 的大作中提到】

: 小孩最好别吃这些东西，不健康。多吃水果吧，可以榨成果汁。

w*s2014-01-14 08:01

15 楼

每次从k中选两个数，枚举+,-,*,/四种操作，这样k个数就变成k-1个数了，递归枚举到
只剩下一个数即为结果。

【在 n*******s 的大作中提到】

: 补充一下在最后的结果表达式中，数字的顺序随便(但必须k个都用到)，操作符的选择
: 和顺序随便，括号
: 的选择随便，但要合法。
: 楼上说的递归，没错，在这个题目里backtracking本质上就是permutation，不是么.
: 另外在无括号的情况下，backtracking求表达式很好写，但是有括号呢？

g*i2014-01-14 08:01

16 楼

5

【在 y****u 的大作中提到】

: 现在淘宝的全球购频道交易额最大的是什么类目?
: 记得是交易额不是交易量。
: 记得是全球购频道（也就是代购频道）不是整体淘宝
: 5选一
: 1：数码手机
: 2：笔记本电脑
: 3：包包
: 4：化妆品
: 5：母婴产品
: 答对的前3人每人10个包子伺候

j*f2014-01-14 08:01

17 楼

我家买了COSTCO的3种GUMMY BEAR。呵呵。换着吃吧。：）
其实啊，大众店里的东西（比如SHAWS,TARGET,WALMART,KMART类），零食类
都差不多。
最近在TRADER JOES和WHOLE FOOD看到一些
新奇的东西。都可以拿来给孩子换着吃。

costco看到三种
focusfacor,据说补脑,但不甜 $39
lilcritters calcium 骨发育 $10+
lilcritters gummy vites 眼发育 $10+
哪种合适？thanks

【在 a**s 的大作中提到】

: costco看到三种
: focusfacor,据说补脑,但不甜 $39
: lilcritters calcium 骨发育 $10+
: lilcritters gummy vites 眼发育 $10+
: 哪种合适？thanks

b*92014-01-14 08:01

18 楼

括号是不是如果当前操作符是乘除就自动给后面出来的表达式加个括号？a * ( rest )

【在 n*******s 的大作中提到】

b*02014-01-14 08:01

19 楼

c*p2014-01-14 08:01

20 楼

这个我回一个。
我给他拿冰箱里面的 cheese糖糖。:)

n*s2014-01-14 08:01

21 楼

有括号呢

【在 w*******s 的大作中提到】

: 每次从k中选两个数，枚举+,-,*,/四种操作，这样k个数就变成k-1个数了，递归枚举到
: 只剩下一个数即为结果。

p*p2014-01-14 08:01

22 楼

以上都不是

【在 y****u 的大作中提到】

n*s2014-01-14 08:01

23 楼

不是的，这里考察所有可能合法的括号会生成的所有结果。

)

【在 b*****9 的大作中提到】

: 括号是不是如果当前操作符是乘除就自动给后面出来的表达式加个括号？a * ( rest )

k*u2014-01-14 08:01

24 楼

5

【在 y****u 的大作中提到】

g*g2014-01-14 08:01

25 楼

没错，基本上就是暴力组合各种表达式
在表达式最后求值。
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*u2014-01-14 08:01

26 楼

能不能每个都选一边

w*s2014-01-14 08:01

27 楼

已经处理了呀，没有括号只要排列加枚举算符

【在 n*******s 的大作中提到】

: 有括号呢

Y*i2014-01-14 08:01

28 楼

3

【在 y****u 的大作中提到】

x*g2014-01-14 08:01

29 楼

这个思路应该是正确方向。
取2个数，用+-*/操作，注意-/有2个方向，把结果放回剩下的k-2变成k-1子问题递归。
不过/如果不是整形操作，中间结果是浮点的话，精度损失又是个问题。
面试真是苦逼没用的事，遇上这种题，估计10有9挂，恶心啊。

【在 w*******s 的大作中提到】

: 每次从k中选两个数，枚举+,-,*,/四种操作，这样k个数就变成k-1个数了，递归枚举到
: 只剩下一个数即为结果。

l*u2014-01-14 08:01

30 楼

卫生巾

w*s2014-01-14 08:01

31 楼

用分数处理就可以了

【在 x****g 的大作中提到】

: 这个思路应该是正确方向。
: 取2个数，用+-*/操作，注意-/有2个方向，把结果放回剩下的k-2变成k-1子问题递归。
: 不过/如果不是整形操作，中间结果是浮点的话，精度损失又是个问题。
: 面试真是苦逼没用的事，遇上这种题，估计10有9挂，恶心啊。

m*n2014-01-14 08:01

32 楼

5

【在 y****u 的大作中提到】

x*g2014-01-14 08:01

33 楼

详解？

【在 w*******s 的大作中提到】

: 用分数处理就可以了

E*r2014-01-14 08:01

34 楼

2

【在 y****u 的大作中提到】

w*s2014-01-14 08:01

35 楼

自己写个分数类，或者用一些直接有标准库可以用，比如python的fractions

【在 x****g 的大作中提到】

: 详解？

b*t2014-01-14 08:01

36 楼

x*g2014-01-14 08:01

37 楼

哦，不熟悉这个，粗略看了下。
就是存分子/分母，完了简化可走最大公约数。+/-需要有最大公背数操作。
为了递归，把所有数都变成分数对象。
该类是不是还要考虑溢出.....?
另外：这个取2完了递归，算法本身如何去重？

【在 w*******s 的大作中提到】

: 自己写个分数类，或者用一些直接有标准库可以用，比如python的fractions

L*12014-01-14 08:01

38 楼

w*s2014-01-14 08:01

39 楼

实现高精度运算就可应付溢出，或者直接使用有标准库的，python/ruby/java都有
去重需要先表达式分析去冗余括号，然后排序

【在 x****g 的大作中提到】

: 哦，不熟悉这个，粗略看了下。
: 就是存分子/分母，完了简化可走最大公约数。+/-需要有最大公背数操作。
: 为了递归，把所有数都变成分数对象。
: 该类是不是还要考虑溢出.....?
: 另外：这个取2完了递归，算法本身如何去重？

y*u2014-01-14 08:01

40 楼

你下家给我的一个wifi版的卫生巾昨天送给关长了他老婆说很好用很有面子

【在 l*********u 的大作中提到】

: 卫生巾

b*92014-01-14 08:01

41 楼

那就不仅乘除加括号，加减也后面可以加上括号应该就行了吧？

【在 n*******s 的大作中提到】

: 不是的，这里考察所有可能合法的括号会生成的所有结果。
:
: )

l*t2014-01-14 08:01

42 楼

4

【在 y****u 的大作中提到】

g*e2014-01-14 08:01

43 楼

这样算不到(1*2)+(3*4)

【在 w*******s 的大作中提到】

: 每次从k中选两个数，枚举+,-,*,/四种操作，这样k个数就变成k-1个数了，递归枚举到
: 只剩下一个数即为结果。

y*o2014-01-14 08:01

44 楼

t*92014-01-14 08:01

45 楼

肯定是5，

b*82014-01-14 08:01

46 楼

包包

y*u2014-01-14 08:01

47 楼

答案揭晓
1 美容护肤/美体/精油
2 奶粉/辅食/营养品
3 手机
4 女装/女士精品
5 彩妆/香水/美发/工具
化妆品绝对的领先！
代购里最热门品牌是哪几个？欧美品牌里... （绝对不是apple,iphone,ipad）
到我俱乐部去看吧

y*u2014-01-14 08:01

48 楼

soimbox
wiiwii
best4380
各10个包子请查收...

E*r2014-01-14 08:01

49 楼

1 4 5

【在 y****u 的大作中提到】

: 答案揭晓
: 1 美容护肤/美体/精油
: 2 奶粉/辅食/营养品
: 3 手机
: 4 女装/女士精品
: 5 彩妆/香水/美发/工具
: 化妆品绝对的领先！
: 代购里最热门品牌是哪几个？欧美品牌里... （绝对不是apple,iphone,ipad）
: 到我俱乐部去看吧

b*02014-01-14 08:01

50 楼

哈哈哈，受到大孢子，谢了

o*t2014-01-14 08:01

51 楼

2

【在 y****u 的大作中提到】

w*i2014-01-14 08:01

52 楼

haha,thanks for the big baozi~~

s*x2014-01-14 08:01

53 楼

Oye! 谢谢！

【在 y****u 的大作中提到】

: soimbox
: wiiwii
: best4380
: 各10个包子请查收...