0

例如：如果一个字符串是")(((())))))("，答案应该是 8。我实现如下：（向他人学习）

int longestValidParentheses(string s) {
    int len = s.length();
    char* str = new char[len+1];
    strcpy(str,s.c_str());
    int maxlen=0;
    stack<char*> stk;
    char* cur = str;
    while(*cur)
    {
        if(*cur=='(')
            stk.push(cur);
        else
        {
            if(!stk.empty() && *stk.top()=='(')
            {
                stk.pop();
                maxlen = max(maxlen, cur-(stk.empty()?str-1:stk.top()));
            }
            else
                stk.push(cur);
        }
        cur++;
    }
    return maxlen;
}

但我不知道为什么这段代码，char* str = new char[len+1]但不是char* str = new char[len]。谁能告诉我为什么？如果我使用char* str = new char[len]，会发生错误。

4

4 回答 4

1

正如您从评论中可以看出的那样，您的问题在于您将一些真正C++（如string类型）的构造与更典型的 C 函数和数据类型（如char*、strcpy等）混合在一起。底线：字符串的长度是其中的字符数；但是所需的存储空间比这要大，因为一种char*字符串有一个终止'\0'字符来表示“字符串结尾”。如果您不为此分配空间，那么'\0'附加在字符串复制操作末尾的 将覆盖另一个内存位置，并可能造成灾难性后果。

于 2013-09-12T21:43:21.940 回答
1

您无需复制字符串即可对其进行迭代，因为它string附带了非常好的迭代器，其工作方式与以下内容完全相同char*：

前 10 行左右可以替换为：

int maxlen = 0;
auto cur = s.begin(), end = s.end();
std::stack<decltype(cur)> stk;
while (cur != end) {

如果您没有 C++11，请使用

std::string::iterator

代替auto和decltype(cur)。

也可以使用索引，甚至将 achar*变成字符串自己的内容：

cur = &s[0];

在任何情况下都不要复制字符串然后泄露它是一个好主意。

于 2013-09-12T21:49:18.630 回答
0

弗洛里斯已经给了你问题的答案。让我补充一件事：您不必复制该字符串。请注意，您正在分配一个缓冲区（新 [len+1]），并且您正在将一个从s.c_str().

检查什么是c_str！您要复制到缓冲区中的内容只是一个字符数组char*，您可以像新缓冲区一样完全适当地使用它。试试看：

int len = s.length();
char const* str = s.c_str();

它应该可以正常工作，而无需制作副本。（也许你需要在几个地方添加一些常量）

于 2013-09-12T21:43:40.337 回答
0 
int longestValidParentheses(string s){
    int pos = 0;
    int maxlen = 0;
    while(pos != -1){
           pos = substr(pos).find("(");
           if(str.substr(pos).find(")") == -1) pos = -1;
           maxlen += 2;
           pos++;
    }
    return maxlen;
}

如果您使用的是 C++，不妨使用您提供的工具。

于 2013-09-12T21:58:23.870 回答