casyup.me@outlook.com

0%

leetcode/32ZLongestValidParentheses

Posted on

Longest Valid Parentheses

一个只包含字符 ‘(‘ 和字符 ‘)’ 的字符串, 找到最长的有效括号层数

my solution

这个问题的核心是如何知道, 哪个 ‘)’ 和哪个 ‘(‘ 匹配

这种情况, 如果用栈来解决的话会简单很多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static int _ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    int longestValidParentheses(string s) {
        int size = s.size();

        vector<int> vecc;
        for (int i = 0; i < size; ++i) {
            if (s[i] == '(') {
                vecc.push_back(i);
            } else {    // asume is )
                if (vecc.size() && s[vecc.back()] == '(') {
                    s[i] = '0';
                    s[vecc.back()] = '0';
                    vecc.pop_back();
                }
                else {  // asume if (vecc.back() != '(') 
                    vecc.clear();
                }
            }
        }

        int ret = 0, now = 0;
        for (int i = 0; i < size; ++i) {
            if (s[i] == '0')
                ++now;
            else {
                ret = max(now, ret);
                now = 0;
            }
        }

        return max(now, ret);
    }
};

我并没有想到一次循环并找到最大长度的办法

采用的是一次循环将所有能够合并的括号全部替换, 再用一次循环来找到其中最长的序列

效果比想象中的要好, 可能是归功于快速IO

the best solution (4ms)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
const static int _= []()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();	// 在 hard 难度的题里面, 这个东西频繁出现

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLength = 0;
        vector<int> dp(s.size());
        for (int i = 1; i < s.size(); i++)
        {
            // 只处理当前值是 ')' 的情况
            if (s[i] == ')')
            {
                // 如果上一个值是 '('
                if (s[i - 1] == '(')
                {
                    // 如果当前下标超出了 2, 意味着可以加上之前的宽度
                    if (i > 2)
                        dp[i] = dp[i - 2] + 2;
                    else
                        // 否则宽度直接为 2 
                        dp[i] = 2;
                }
                // 如果上一个值是 ')'
                else // s[i-1] == ')'
                {
                    // 暂时保存上一个下标所记录的步数
                    int prev = dp[i - 1];
                    // 先判断下标是否有效, s[i - prev - 1] 的含义是
                    // 当前下标 减去 上一个下标记录的宽度, 那么就来到了这个宽度的起始位置
                    // 再减去 1, 就得到了这个宽度的上一个字符, 如果是 '(' 则代表宽度可以继续增加2
                    if (i - prev - 1 >= 0 && s[i - prev - 1] == '(')
                    {
                        // 宽度增加了 2
                        dp[i] = dp[i - 1] + 2;
                        // 再判断上一个区间的索引值是否合法
                        if (i - prev - 2 >= 0)
                            // 合法的话就再加上上一个区间的宽度
                            dp[i] += dp[i - prev - 2];
                    }
                }

            }
        }

        for (int n : dp)
            maxLength = max(maxLength, n);
        return maxLength;
    }
};

算法给人的第一感觉是”脚印”, 如果上一个”脚印”有效, 就加上他, 这样慢慢增加

他也是由两次循环组成, 第一个循环计算每次的步数, 第二次循环找到最大值

规律总结在代码注释, 假设字符串是 “()))()))()”, 那么他的 dp 可能是 0 2 0 0 0 2 0 0 0 2

“())(())()()()))” dp 可能是 0 2 0 0 0 2 4 0 6 0 8 0 [10] 0 0

(眼睛有点花… 不过应该没错)

大抵来说:

  1. 跳过了 ‘(‘ 的判断, 这会使需要处理的情况少 1/2
  2. 赋值少了 1/2, 他不对 ‘(‘ 的索引进行计算

emmm… 学到了很多

感觉”脚印”这个概念在很多算法里面都看到过, 一个个累加将复杂的计算分为了很多的小计算