Leetcode上stack相关的题目相比CC150题怎么那么少？Longest Valid Parentheses - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Leetcode上stack相关的题目相比CC150题怎么那么少？Longest Valid Parentheses

Leetcode上stack相关的题目相比CC150题怎么那么少？Longest Valid Parentheses# JobHunting - 待字闺中

a*e2014-08-21 07:08

1 楼

第一次看到的时候没想到要push数组的位置，而不是push‘（’，结果怎么都做不出来。
后来看了讨论的idea是把Indices存起来，按照那个想法写了，却发现last的初值要设
成-1，而不是0。最后通过的答案，看着觉得好郁闷，想了好久。。。。。。。
int longestValidParentheses(string s) {
vector left;
int n=s.size();
int last=-1,lmax=0;
for (int i=0; i{
if (s[i]=='(')
{
left.push_back(i);
}
else if (s[i]==')')
{
if (left.empty())
{
last=i;
}
else
{
left.pop_back();
if (left.empty())
{
lmax = max(lmax,i-last);
}
else
lmax = max(lmax,i-left.back());
}
}
}
return lmax;
}

h*e2014-08-21 07:08

2 楼

这道题最开始的想法是（也压栈，）也压栈，然后记录相应的index.不过后来发现似乎
）压栈没有必要只有最右边的）有用，就优化成最简那个形式了。

a*e2014-08-21 07:08

3 楼

我在看讨论之前一直没想过记录相应的index，所以一直搞不定。估计还是题做太少

s*t2014-08-21 07:08

4 楼

不用什么-1啊，压入index的想法在别的题里也有啊，比如histogram

m*a2014-08-21 07:08

5 楼

不喜欢这种不直观的很难看懂的写法
你在遇到)，准备pop的时候，看一下stack上对应位置是不是(
如果是，就pop，不是就push
最大值，就是当前i-pop后stack的index+1或i+1 when stack is empty.

来。

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

: 第一次看到的时候没想到要push数组的位置，而不是push‘（’，结果怎么都做不出来。
: 后来看了讨论的idea是把Indices存起来，按照那个想法写了，却发现last的初值要设
: 成-1，而不是0。最后通过的答案，看着觉得好郁闷，想了好久。。。。。。。
: int longestValidParentheses(string s) {
: vector left;
: int n=s.size();
: int last=-1,lmax=0;
: for (int i=0; i: {
: if (s[i]=='(')

a*e2014-08-21 07:08

6 楼

我不太明白你说的意思，你觉得易懂的写法是怎么样的？能贴出来参考一下么？
如果输入是（（（（））））（（（（（）

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

: 不喜欢这种不直观的很难看懂的写法
: 你在遇到)，准备pop的时候，看一下stack上对应位置是不是(
: 如果是，就pop，不是就push
: 最大值，就是当前i-pop后stack的index+1或i+1 when stack is empty.
:
: 来。

h*e2014-08-21 07:08

7 楼

楼主如果想做的话，做个四则运算的计算把。。做出来再做一个带括号的。我觉得这个
经常考，也不是特别经常但是作为难题倒是经常出现，而且twitter考过解方程的，前
一阵一个版友的twitter面经就是这个。

m*a2014-08-21 07:08

8 楼

int longestValidParentheses(string s) {
int max_length=0,length;
stack container;
for (int i=0;iif (s[i]=='('||container.empty()||s[container.top()]==')')
container.push(i);
else {
container.pop();
length=container.empty()?i+1:i-container.top();
if (length>max_length) max_length=length;
}
}
return max_length;
}

a*e2014-08-21 07:08

9 楼

可能每个人想得不同，我咋觉得这种方法更复杂呢。每个符号都要push进去。

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

: int longestValidParentheses(string s) {
: int max_length=0,length;
: stack container;
: for (int i=0;i: if (s[i]=='('||container.empty()||s[container.top()]==')')
: container.push(i);
: else {
: container.pop();
: length=container.empty()?i+1:i-container.top();
: if (length>max_length) max_length=length;

a*e2014-08-21 07:08

10 楼

请问你说的是
Evaluate Reverse Polish Notation么？或者是类似的
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another
expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
其实一点都不想做题。特别是碰到要花很长时间才能做出来的题，气大得很啊。。。。
。。。。。
估计要等明年才敢出去面试啦。。。。。。。。

【在 h*******e 的大作中提到】

: 楼主如果想做的话，做个四则运算的计算把。。做出来再做一个带括号的。我觉得这个
: 经常考，也不是特别经常但是作为难题倒是经常出现，而且twitter考过解方程的，前
: 一阵一个版友的twitter面经就是这个。

m*a2014-08-21 07:08

11 楼

其实反过来写就跟清楚了
如果stack不空的化，
if (s[i]=='(' and s[stack.top()]==')')
container.pop();
length=container.empty()?i+1:i-container.top();
if (length>max_length) max_length=length;
其他的所有情况push stack

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

: 可能每个人想得不同，我咋觉得这种方法更复杂呢。每个符号都要push进去。

y*n2014-08-21 07:08

12 楼

写反了，呵呵。。

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

: 其实反过来写就跟清楚了
: 如果stack不空的化，
: if (s[i]=='(' and s[stack.top()]==')')
: container.pop();
: length=container.empty()?i+1:i-container.top();
: if (length>max_length) max_length=length;
: 其他的所有情况push stack

h*e2014-08-21 07:08

13 楼

这个也算，还有正常的四则式子的运算，我经常感觉脑子不够用了，想到复杂的问题
多想一会儿就特累得休息然后再想~~~~

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

: 请问你说的是
: Evaluate Reverse Polish Notation么？或者是类似的
: Evaluate the value of an arithmetic expression in Reverse Polish Notation.
: Valid operators are +, -, *, /. Each operand may be an integer or another
: expression.
: Some examples:
: ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
: ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
: 其实一点都不想做题。特别是碰到要花很长时间才能做出来的题，气大得很啊。。。。
: 。。。。。

a*e2014-08-21 07:08

14 楼

‘正常的四则式子的运算’是不是用arithmetic expression tree更好做？或者先把它
转换为RPN，再做。Data structure and algorithm 那本书上有解释怎么转换。。。。
。。。。
关于Evaluate Reverse Polish Notation,知道RPN的特点或者说evaluate RPN的算法后
，更像一道细节实现题。
我在OJ上错了就是因为记不清怎么把string变成char，还有没注意isdigit只判断1个符
号，遇到（-4）就没把它当负数了。
int evalRPN(vector &tokens) {

int n = tokens.size();

stack numbers;

for (int i=0; i{
int len = tokens[i].length();
char * tmp = new char [len+1];
std::strcpy (tmp, tokens[i].c_str());
int j=0;
if (len==1&&(*tmp=='+'||*tmp=='-'||*tmp=='*'||*tmp=='/'))
{
int a = numbers.top();
numbers.pop();
int b = numbers.top();
numbers.pop();

if (*tmp=='+')
{
j=a+b;
}
else if (*tmp=='-')
{
j=b-a;
}
else if (*tmp=='*')
{
j=a*b;
}
else if(*tmp=='/')
{
j=b/a;
}

numbers.push(j);
}
else
{
j = atoi(tokens[i].c_str());
numbers.push(j);
}

}

return numbers.top();
}

【在 h*******e 的大作中提到】

: 这个也算，还有正常的四则式子的运算，我经常感觉脑子不够用了，想到复杂的问题
: 多想一会儿就特累得休息然后再想~~~~

h*e2014-08-21 07:08

15 楼

你写得挺好啊，我之前自己实现 atoi 了~~~ 还有自己写 intToStr了~~~ 看过你的发
现这些都不用啊，代码由50多行缩到了25行。正常四则运算的如果不带括号的就直接
一个stack就行, 如果带括号的需要2个stack 一个放符号，一个放数字。。带括号的
情况还挺复杂~~ 带括号的我还不会提笔就写~~ 没怎么练过，不带括号的倒是简单
一点。
我把我照你的改的也给贴上
class Solution {
public:
int evalRPN(vector &tokens) {
stack numStack;
for(int tokI = 0; tokI < tokens.size(); ++ tokI)
if(tokens[tokI] == "*" || tokens[tokI] == "+" || tokens[tokI] ==
"/" || tokens[tokI] == "-")
{
int val1 = numStack.top(); numStack.pop();
int val2 = numStack.top(), res; numStack.pop();
if(tokens[tokI] == "+")
res = val1 + val2;
else if(tokens[tokI] == "*")
res = val1 * val2;
else if(tokens[tokI] == "-")
res = val2 - val1;
else
res = val2 / val1;
numStack.push(res);
}
else
numStack.push(atoi(tokens[tokI].c_str()));
return numStack.top();
}
};

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

: ‘正常的四则式子的运算’是不是用arithmetic expression tree更好做？或者先把它
: 转换为RPN，再做。Data structure and algorithm 那本书上有解释怎么转换。。。。
: 。。。。
: 关于Evaluate Reverse Polish Notation,知道RPN的特点或者说evaluate RPN的算法后
: ，更像一道细节实现题。
: 我在OJ上错了就是因为记不清怎么把string变成char，还有没注意isdigit只判断1个符
: 号，遇到（-4）就没把它当负数了。
: int evalRPN(vector &tokens) {
:
: int n = tokens.size();

a*e2014-08-21 07:08

16 楼

多谢，学习了。