leetcode Different Ways to Add Parentheses 怎么做？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

leetcode Different Ways to Add Parentheses 怎么做？

leetcode Different Ways to Add Parentheses 怎么做？# JobHunting - 待字闺中

j*32015-08-02 07:08

1 楼

求代码，求思路,
果然年龄大了，智商捉急啊，还好最近不面

c*n2015-08-02 07:08

2 楼

你想想手做怎么弄，基本上左括号多于右括号就可再加右括号

【在 j**********3 的大作中提到】

: 求代码，求思路,
: 果然年龄大了，智商捉急啊，还好最近不面

l*s2015-08-02 07:08

3 楼

想象一下用手去挨个提溜中间的操作符，每次提溜出一个二叉树。

【在 j**********3 的大作中提到】

: 求代码，求思路,
: 果然年龄大了，智商捉急啊，还好最近不面

p*22015-08-02 07:08

4 楼

大牛还在刷呀。

【在 j**********3 的大作中提到】

: 求代码，求思路,
: 果然年龄大了，智商捉急啊，还好最近不面

j*32015-08-02 07:08

5 楼

我说的是那个新题，不是generate parenth的，我们说的是一个题吗？
如果是，就太好了。。。

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

: 你想想手做怎么弄，基本上左括号多于右括号就可再加右括号

j*32015-08-02 07:08

6 楼

校长给点思路吧

【在 p*****2 的大作中提到】

:
: 大牛还在刷呀。

j*32015-08-02 07:08

7 楼

大牛，能给段java code吗？

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

: 想象一下用手去挨个提溜中间的操作符，每次提溜出一个二叉树。

b*52015-08-02 07:08

8 楼

正解

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

: 想象一下用手去挨个提溜中间的操作符，每次提溜出一个二叉树。

j*32015-08-02 07:08

9 楼

能给段code么？

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

: 正解

s*l2015-08-02 07:08

10 楼

这个解释好很形象~
https://leetcode.com/discuss/48477/a-recursive-java-solution-284-ms

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

: 想象一下用手去挨个提溜中间的操作符，每次提溜出一个二叉树。

j*32015-08-02 07:08

11 楼

谢谢！

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

: 这个解释好很形象~
: https://leetcode.com/discuss/48477/a-recursive-java-solution-284-ms

j*32015-08-02 07:08

12 楼

这个题有点像那个 unique binary search tree, 是不？

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

: 这个解释好很形象~
: https://leetcode.com/discuss/48477/a-recursive-java-solution-284-ms

k*a2015-08-02 07:08

13 楼

加括号相当于进出栈的顺序，和二叉树树木是一样的，叫什么卡特兰数
https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0

【在 j**********3 的大作中提到】

: 这个题有点像那个 unique binary search tree, 是不？

l*a2015-08-02 07:08

14 楼

再给你几道follow up questions
输入很长时怎么提高性能呢？
如何去重呢？
如何不用递归呢？

【在 j**********3 的大作中提到】

: 这个题有点像那个 unique binary search tree, 是不？

p*22015-08-02 07:08

15 楼

boolean isOp(char c){
return c == '+' || c == '-' || c == '*';
}

int cal(char c, int x, int y){
switch(c) {
case '+':
return x+y;
case '-':
return x-y;
case '*':
return x*y;
default:
return -1;
}
}

List dfs(String input, int s, int e){
List al = new ArrayList<>();
for(int i=s; ichar c = input.charAt(i);
if(isOp(c)){
List left = dfs(input, s, i);
List right = dfs(input, i+1, e);
for(int x: left){
for(int y: right){
al.add(cal(c, x, y));
}
}
}
}
if(al.size()==0){
al.add(Integer.parseInt(input.substring(s,e)));
}
return al;
}

public List diffWaysToCompute(String input) {
return dfs(input, 0, input.length());
}

【在 j**********3 的大作中提到】

: 校长给点思路吧

l*a2015-08-02 07:08

16 楼

怎么解决输入太长，call stack overflow的问题呢？
请校长指点

【在 p*****2 的大作中提到】

:
: boolean isOp(char c){
: return c == '+' || c == '-' || c == '*';
: }
:
: int cal(char c, int x, int y){
: switch(c) {
: case '+':
: return x+y;
: case '-':

o*y2015-08-02 07:08

17 楼

dp?
[在 lolhaha (长期骑驴,一直找马) 的大作中提到：]
：怎么解决输入太长，call stack overflow的问题呢？
：请校长指点
：...........

r*n2015-08-02 07:08

18 楼

Scala code, not tested
object Parenthesis {
def main(args: Array[String]) {
val ret = constructTree("1+3*5")
println("start")
ret.foreach(println)
}
def wrap(c: Char): (Int, Int)=>Int = {
c match {
case '+' => (x, y) => x + y
case '-' => (x, y) => x - y
case '*' => (x, y) => x * y
}
}
def constructTree(input: String): Array[Int] = {
var split = false
var ret = (0 until input.length).flatMap{ idx =>
input(idx) match {
case '+' | '-' | '*' =>
split = true
val (left, right) = (constructTree(input.substring(0, idx)),
constructTree(input.substring(idx + 1, input.length)))
for{
l r } yield wrap(input(idx))(l, r)
case _ =>
Array.empty[Int]
}
}.toArray
if (!split){
ret = Array.fill(1)(input.toInt)
}
ret
}
}