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 { if (vecc.size() && s[vecc.back()] == '(') { s[i] = '0'; s[vecc.back()] = '0'; vecc.pop_back(); } else { 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; }();
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] == '(') { if (i > 2) dp[i] = dp[i - 2] + 2; else dp[i] = 2; } else { int prev = dp[i - 1]; if (i - prev - 1 >= 0 && s[i - prev - 1] == '(') { 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/2
- 赋值少了 1/2, 他不对 ‘(‘ 的索引进行计算
emmm… 学到了很多
感觉”脚印”这个概念在很多算法里面都看到过, 一个个累加将复杂的计算分为了很多的小计算