casyup.me@outlook.com

0%

leetcode/32ZLongestValidParentheses

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… 学到了很多

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