算法题1LVPS|我们学校终于放暑假了...

不知道打开这一页的小伙伴内心世界是怎样的...
如题，我们学校终于开始放暑假了

微信图片_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
给各位准入程序员职场的发干货，日常算法题，机器学习等资料敬请期待~