不知道打开这一页的小伙伴内心世界是怎样的...
如题，我们学校终于开始放暑假了
微信图片_20180730170034.jpg
To 学生：嗷。。什么？你们早就放暑假了？？？那又怎样？我们爱学习，我们宁愿在图（qin）书（shi）馆（da）学（wang）习（zhe），对我们就是中国最晚放假的大学
To 已经毕业的coder：你点进来是何居心？工作中的bug调好了吗？业务逻辑理清楚了吗？blablabla
微信图片_20180730170109.png
等等，这和算法题有什么关系？
答案是
哦，没什么关系，就是日常闲得 dan teng 做做算法题，且看一道 LeetCode Hard 赛题
寻找最长合法括号子串
给定包含 '(' 和 ')'的一个字符串, 找到一个最长的合法的括号子串。
Example 1:
Input: "(()"
Output: 2
解释: 最长有效括号子串是 "()"
Example 2:
Input: ")()())"
Output: 4
解释: 最长有效括号子串是 "()()"
这道题是考括号匹配算法，首先第一个想到的肯定是：暴力循环求解咯~
这里补充一下括号匹配算法：一般用 stack 解决，简单来说就是遇到 '(' 就push ‘)’就pop，如果pop失败或者最后stack非空就 return false.否则 return true.
显然匹配判断一下就是 O(N) 复杂度了
在做之前且慢，让我掐指一算 emmm 复杂度 O(N^3) 肯定不合算
当然这题我是想用动态规划来做的
while (想出方法){咬手指;}
然后我放弃了，因为手指真的好痛...于是我决定换一个姿势
while(想出方法){趴着打草稿;}
过了N久，对不起，恕小编无能，比不过各位大佬，这次我想不出睡着了...醒来翻翻solution 终于明白了
题解
首先，先上最简单的 Brute Force 算法
最简单暴力求解
// 匹配算法
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push('(');
} else if (!stack.empty() && stack.peek() == '(') {
stack.pop();
} else {
return false;
}
}
return stack.empty();
}
// 最长匹配求解
int main(){
int M=0;
for (int i=0;i<s.size();i++)
for (int j=i+1;j<s.size();j++)
if (isValid(s,i,j))
M=max(M,j-i+1);
return 0;
}
时间复杂度 O(N^3)
其次，上了最高效的动态规划算法，看完答案都想自尽，因为太巧妙了...对不起，小编功底不到家...可是转念一想，不就是因为功底不到家才刷算法题提升自己能力的嘛...ヾ(≧▽≦*)o 于是我兴奋地坚持往下看了...
动态规划
dp[i] 表示以 i 下标结尾的匹配括号串的最长长度
那么当且仅当 s[i]=')' 有 dp[i]\geq 0，这个时候才可能是合法的呀(●'◡'●)
-
如果 ".....() "则 dp[i]=dp[i-2]+2，这个式子很显然了
-
如果" .....)) "且 dp[i-dp[i-1]-1]='('则 dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2 表示分裂成两个相连的匹配括号串。
解释一下 i-dp[i-1]-1 这个索引其实是以 dp[i-1] 为结尾的合法串的串头还要再往前一个的索引，因为 dp[i-1] 是以 s[i-1]=')' 为末尾的合法串长。那么如果 dp[i-dp[i-1]-1]='('，那么算 dp[i] 除了计算从 i-dp[i-1]-1='(' 为开头到 s[i-1]=')' 为末尾的串长，即 dp[i-1]，我们还别忘了计算以 i-dp[i-1]-2 为末尾的合法串呀，虽然可能是 0。
找到 DP 方程编程什么的都是小 caaseee (●ˇ∀ˇ●)
public int longestValidParentheses(String s) {
int maxans = 0;
int dp[] = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxans = Math.max(maxans, dp[i]);
}
}
return maxans;
}
时间复杂度 O(N)
再来一种贼巧妙的，至少我觉得是，给大家来拓宽一下思路~
别走，小心下一次面试说不定就碰到啦！
栈算法
使得当前最大长度 MaxLength 记录的始终是最长的合法的串
初始 stack.push(-1)
(1) 如果 s[i]='(' ，则 stack.push(i)
(2) 如果 s[i]=')'， 则stack.pop()
若 stack.empty()
stack.push(i)
保证从 '(' 的前一个开始计
若 !stack.empty()
MaxLength=max\{MaxLength,i-stack.top()\}
保证 i-stack.top() 是合法串的长度
没有 code 感觉就像说废话一样，所以大家有空可以敲一敲
public int longestValidParentheses(String s) {
int maxans = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}
这是第一篇 leetcode专题的文章，以后会出更多的~主要还是想一边自己学习的同时 和大家一起分享，一起进步，大家可能坐地铁或者什么的也不方便拿出电脑啊啥的，你只要打开文章以及纸笔就算是分析了一道题，也算是节约了时间了~
我当然比不过很多大牛，不过还是希望我包括大家都走在成为大牛的路上...
感谢大家敬请期待ヾ(≧▽≦*)o
个人微信公众号：准程序员coder
ID: wx_precoder
给各位准入程序员职场的发干货，日常算法题，机器学习等资料敬请期待~
网友评论