其中包含:广搜、深搜、动态规划
递归很要命💀
判断括号的合法性 对括号的合法性判断是一个很常见且实用的问题,比如说我们写的代码,编辑器和编译器都会检查括号是否正确闭合。而且我们的代码可能会包含三种括号[](){}
,判断起来有一点难度。
本文就来聊一道关于括号合法性判断的算法题,相信能加深你对栈 这种数据结构的理解。
解决这个问题之前,我们先降低难度,思考一下,如果只有一种括号() ,应该如何判断字符串组成的括号是否合法呢?
处理一种括号 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 public static boolean isValid (String s) { if (s == null || s.length() < 1 ) return true ; int n = s.length(); Stack<Character> stack = new Stack<>(); for (int i = 0 ; i < n; i++){ char c = s.charAt(i); if (c == '(' ){ stack .push(c); }else { if (stack .isEmpty()) return false ; else stack .pop(); } } if (stack .isEmpty()) return true ; return false ; }
优化:
1 2 3 4 5 6 7 8 9 10 11 12 bool isValid (string str) { int left = 0 ; for (char c : str) { if (c == '(' ) left++; else left--; if (left < 0 ) return false ; } return left == 0 ; }
如果只有圆括号,这样就能正确判断合法性。对于三种括号的情况,我一开始想模仿这个思路,定义三个变量left1
,left2
,left3
分别处理每种括号,虽然要多写不少 if else 分支,但是似乎 可以解决问题。
但实际上直接照搬这种思路是不行的 ,比如说只有一个括号的情况下(())
是合法的,但是多种括号的情况下,[(])
显然是不合法 的。
仅仅记录每种左括号出现的次数已经不能做出正确判断了,我们要加大存储的信息量,可以利用栈 来模仿类似的思路。
处理多种括号 栈是一种先进后出的数据结构,处理括号问题的时候尤其有用。
我们这道题就用一个名为left
的栈代替之前思路中的left
变量,遇到左括号就入栈,遇到右括号就去栈中寻找最近的左括号,看是否匹配 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 bool isValid (string str) { stack<char > left; for (char c : str) { if (c == '(' || c == '[' || c == '{' ) left.push(c); else if (!left.empty() && leftOf(c) == left.top()) left.pop(); return false ; } return left.empty(); } char leftOf (char c) { if (c == '(' ) return ')' ; else if (c == '[' ) return ']' ; return '}' ; }
以上就是判断括号合法性的算法思路,核心就是利用了栈先进后出的特点,栈顶元素就是最近的左括号,遇到右括号就在栈顶判断就行了。遇到括号相关的问题,可以优先考虑一下是否能借助栈来解决。
最长有效括号 其实这道题就是 leetcode 的原题,第 32 题,难度为 hard。
1 2 3 4 5 6 7 8 9 示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2: 输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"
1、暴力法
暴力法其实很简单,就是最开始把第一个字符当做最长有效括号的首字符 来遍历字符串,接着把第二个字符当做最长有效括号的首字符来遍历字符串,接着把第三个字符……
例如对于 s = “( ) ) ( ( ) )”。
把第一个字符作为首字符,则 max = 2 (遇到第三个字符 ‘)’ 就匹配不了了) 把第二个字符作为首字符,则 max = 0 (一开始就是 ‘)’,显然啥也匹配不了) 把第三个字符作为首字符,则 max = 0 把第四个字符作为首字符,则 max = 4 ….. 这种做法的时间复杂度为 O(n^2),空间复杂度为 O(1)
基本上面那道题一样,只是做了 n 次遍历。
这道题的优化版本我们仍然是用栈来做,不过入栈的时候,不是让 “(“ 入栈,而是让 “(“ 的下标入栈。步骤如下:
1、先把 -1 放入栈内。(至于为什么?看到后面你就知道了) 2、、对于遇到的每个 ‘(‘ ,我们将它的下标 放入栈中。 3、对于遇到的每个 ‘)’ ,我们弹出栈顶的元素并将当前元素的下标 与弹出元素下标作差 ,得出当前有效括号字符串的长度 。
通过这种方法,我们继续计算有效子字符串的长度,并最终返回最长有效子字符串的长度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public int longestValidParentheses(String s) { int max = 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 { max = Math.max (max , i - stack .peek()); } } } return maxans; }
实际上,这道题仍然可以像上面那样,用变量来代替栈来优化,不过这个时候我们需要两个变量,我们假设变量为 left 和 right。
我们在从从左到右遍历字符串的过程中,用 left 记录 ‘(‘ 的数量,用 right 记录 ‘)’ 的数量。并且在遍历的过程中:
1、如果 left >= right,显然这个时候 right 个 ‘)’ 都将一定能够得到匹配。所以当前的有效括号长度为 2 * right。然后更新 max。
2、如果 left < right,显然这个时候部分 ‘)’ 一定得不到匹配,此时我们把 left 和 right 都置为 0。
当遍历完字符串,我们是否就得到最大长度的有效括号了呢? 大家可以想一下
答是不可以的,我们还需要从右到左 遍历计算一下。
为什么呢?
因为实际上 ‘(‘ 和 ‘)’ 其实是等价的,为什么就不可以倒过来遍历计算呢?所以,千万别忽略了哈。
最后的代码如下:
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 public int longestValidParentheses(String s) { int left = 0 , right = 0 , max = 0 ; for (int i = 0 ; i < s.length(); i++) { if (s.charAt(i) == '(') { left ++; } else { right ++; } if (left == right ) { max = Math .max (max , 2 * right ); } else if ( right > left ) { left = right = 0 ; } } left = right = 0 ; for (int i = s.length() - 1 ; i >= 0 ; i--) { if (s.charAt(i) == '(') { left ++; } else { right ++; } if (left == right ) { max = Math .max (max , 2 * left ); } else if (left > right ) { left = right = 0 ; } } return max ; }
高频算法题:括号生成 题目描述 给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的 括号组合。
例如,给出 n = 3 ,生成结果为:
1 2 3 4 5 6 7 [ "((()))" , "(()())" , "(())()" , "()(())" , "()()()" ]
回溯算法(深度优先遍历) 之后会写一篇关于深搜跟广搜的文章
如果完成一件事情有很多种方法,并且每一种方法分成若干步骤,那多半就可以使用“回溯”算法完成。
“回溯”算法的基本思想是“尝试搜索”,一条路如果走不通(不能得到想要的结果),就回到上一个“路口”,尝试走另一条路。
因此,“回溯”算法的时间复杂度一般不低。如果能提前分析出,走这一条路并不能得到想要的结果,可以跳过这个分支,这一步操作叫“剪枝”。
做“回溯”算法问题的基本套路是:
1、使用题目中给出的示例,画树形结构图,以便分析出递归结构;
一般来说,树形图不用画完,就能够分析出递归结构和解题思路。
2、分析一个结点可以产生枝叶的条件、递归到哪里终止、是否可以剪枝、符合题意的结果在什么地方出现(可能在叶子结点,也可能在中间的结点);
3、完成以上两步以后,就要编写代码实现上述分析的过程,使用代码在画出的树形结构上搜索符合题意的结果。
在树形结构上搜索结果集,使用的方法是执行一次“深度优先遍历”。在遍历的过程中,可能需要使用“状态变量”。
我们以 n = 2
为例,画树形结构图。
参考代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public class Solution { public List<String> generateParenthesis (int n) { List<String> res = new ArrayList<>(); if (n == 0 ) return res; dfs('' ,n,n,res); return res; } private void dfs (String curstr,int left,int right, List<String> res) { if (left == 0 && right == 0 ) { res.add(curstr); return ; } if (left > 0 ) { dfs(curstr+'(' , left-1 , right, res); } if (right > 0 && right > left) { dfs(curstr+ ')' , left, right-1 , res); } } }
Parentheses: 圆括号
带注释版:
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 public class Solution { public List<String> generateParenthesis (int n) { List<String> res = new ArrayList<>(); if (n == 0 ) { return res; } dfs("" , n, n, res); return res; } private void dfs (String curStr, int left, int right, List<String> res) { if (left == 0 && right == 0 ) { res.add(curStr); return ; } if (left > 0 ) { dfs(curStr + "(" , left - 1 , right, res); } if (right > 0 && left < right) { dfs(curStr + ")" , left, right - 1 , res); } } }
因为每一次尝试,都使用新的字符串变量,所以没有显式的回溯过程
在递归终止的时候,直接把它添加到结果集即可,与leetcode第 46 题、第 39 题区分
如果我们不用减法,使用加法,即 left
表示“左括号还有几个没有用掉”,right
表示“右括号还有几个没有用掉”,可以画出另一棵递归树。
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 public class Solution { public List<String> generateParenthesis (int n) { List<String> res = new ArrayList<>(); if (n == 0 ) { return res; } dfs("" , 0 , 0 , n, res); return res; } private void dfs (String curStr, int left, int right, int n, List<String> res) { if (left == n && right == n) { res.add(curStr); return ; } if (left < n) { dfs(curStr + "(" , left + 1 , right, n, res); } if (right < n && left > right) { dfs(curStr + ")" , left, right + 1 , n, res); } }
广度优先遍历 使用广度优先遍历,结果集都在最后一层,即叶子结点处得到所有的结果集,编写代码如下。
还是这棵树,只是我们这次使用广搜
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 55 56 57 58 59 60 public class Solution { class Node { private String res; private int left; private int right; public Node (String res, int left, int right) { this .res = res; this .left = left; this .right = right; } @Override public String toString () { return "Node{" + "res='" + res + '\'' + ", left=" + left + ", right=" + right + '}' ; } } public List<String> generateParenthesis (int n) { List<String> res = new ArrayList<>(); if (n == 0 ) { return res; } Queue<Node> queue = new LinkedList<>(); queue.offer(new Node("" , n, n)); n = 2 * n; while (n > 0 ) { int size = queue.size(); for (int i = 0 ; i < size; i++) { Node curNode = queue.poll(); if (curNode.left > 0 ) { queue.offer(new Node(curNode.res + "(" , curNode.left - 1 , curNode.right)); } if (curNode.right > 0 && curNode.left < curNode.right) { queue.offer(new Node(curNode.res + ")" , curNode.left, curNode.right - 1 )); } } n--; } while (!queue.isEmpty()) { res.add(queue.poll().res); } return res; } }
动态规划 第 1 步:定义状态 dp[i]
使用 i 对括号能够生成的组合。
注意 :每一个状态都是列表的形式。
第 2 步:状态转移方程 :
i
对括号的一个组合,在 i - 1
对括号的基础上得到;
i
对括号的一个组合,一定以左括号 “(“ 开始(不一定以 “)” 结尾),为此,我们可以枚举右括号 “)” 的位置,得到所有的组合;
枚举的方式就是枚举左括号 “(“ 和右括号 “)” 中间可能的合法的括号对数,而剩下的合法的括号对数在与第一个左括号 “(“ 配对的右括号 “)” 的后面,这就用到了以前的状态。
状态转移方程是:
1 dp[i] = "(" + dp[可能的括号对数] + ")" + dp[剩下的括号对数]
“可能的括号对数” 与 “剩下的括号对数” 之和得为 i,故“可能的括号对数” j 可以从 0 开始,最多不能超过 i, 即 i - 1;
“剩下的括号对数” + j = i - 1,故 “剩下的括号对数” = i - j - 1。
整理得:
1 dp[i] = "(" + dp[j] + ")" + dp[i- j - 1 ] , j = 0 , 1 , ..., i - 1
第 3 步:思考初始状态和输出 :
初始状态:因为我们需要 0 对括号这种状态,因此状态数组 dp 从 0 开始,0 个括号当然就是 [“”]。 输出:dp[n] 。 这个方法暂且就叫它动态规划,这么用也是很神奇的,它有下面两个特点:
1、自底向上:从小规模问题开始,逐渐得到大规模问题的解集;
2、无后效性:后面的结果的得到,不会影响到前面的结果。
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 public class Solution { public List<String> generateParenthesis (int n) { if (n == 0 ) { return new ArrayList<>(); } List<List<String>> dp = new ArrayList<>(n); List<String> dp0 = new ArrayList<>(); dp0.add("" ); dp.add(dp0); for (int i = 1 ; i <= n; i++) { List<String> cur = new ArrayList<>(); for (int j = 0 ; j < i; j++) { List<String> str1 = dp.get(j); List<String> str2 = dp.get(i - 1 - j); for (String s1 : str1) { for (String s2 : str2) { cur.add("(" + s1 + ")" + s2); } } } dp.add(cur); } return dp.get(n); } }
n对括号能组成多少种合法括号串 题目要求:请编程计算出结果,如果数字过大,给出它对100007取模之后的结果。
考虑几种情况,起手右括号,怎么都不合法,例如:)(())(
前面括号抵消之后剩下起手右括号,还是不合法,例如:()())(
剩下的只要左右括号总个数相同,都是合法情况
有点像“栈”的过程,入栈出栈
我们可以用递归来实现代码,每一次都是添加左括号或者添加右括号的过程,注意递归函数的理解,看代码
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 public class CountBracketPair { private int count (int total, int left, int right) { if (left == total) { return 1 ; } int leftCount = count(total, left + 1 , right); int rightCount = 0 ; if (left > right) { rightCount = count(total, left, right + 1 ); } return leftCount + rightCount; } public int countPair (int total) { int left = 0 , right = 0 ; return count(total, left, right); } } public class Main { public static void main (String[] args) { CountBracketPair countBracketPair = new CountBracketPair(); System.out.println(countBracketPair.countPair(12 )); System.out.println(countBracketPair.countPair(12 ) % 100007 ); } }