一、括号生成【中等】题目转变成“放n个左括号和n个右括号放的过程中保证左括号的数量始终大于等于右括号的数量一共有多少种放法”暴力搜索的思想递归的手段回溯。递归的第一件事是先分清用的是分治还是搜索刚刚我们已经确定了思想就是深度优先搜索。第二件事是画图然后定义递归子问题generate(ans,left-1,right,temp() 表示。。这里要注意一定要先放左括号不然在根节点就会全局退出。然后根据递归出口写法的不同有两种方式我们先采用“先污染再治理”的方式也就是递归出口都写在方法的最前面这种方式也就是在第n1轮的时候判断。class Solution { public ListString generateParenthesis(int n) { ArrayListString ans new ArrayList(); generate(ans,n,n,); return ans; } //left记录左括号剩下的right记录右括号剩下的 public void generate(ArrayListString ans,int left, int right, String temp){ //1.找到一个答案退出 if(left0right0){ ans.add(temp); return; } //2.剪枝 if(left0) return; //3.剪枝 if(leftright) return; //用“(”巧妙回溯 generate(ans,left-1,right,temp(); //用“)”巧妙回溯 generate(ans,left,right-1,temp)); } }递归出口的第二种方式在进入第n1次递归之前判断也就是第n轮进行判断class Solution { public ListString generateParenthesis(int n) { LinkedListString ans new LinkedList(); generate(ans,n,n,); return ans; } //left记录左括号剩下的right记录右括号剩下的 public void generate(LinkedListString ans,int left, int right, String thisTurnResult){ //没有第n1轮的递归出口 //1、第n轮判断只剩一个右括号了不用进入下次递归了直接在这一轮结束 if(left0 right 1){ ans.add(thisTurnResult)); return; } ///2、只能放左括号需要回溯。这里通过传参的方式进行巧妙的回溯 if(left right){ generate(ans,left-1,right,thisTurnResult(); //3、左括号、右括号都能放 }else{ //一定是左括号先用完 if(left0){ generate(ans,left-1,right,thisTurnResult(); } generate(ans,left,right-1,thisTurnResult)); } } }还有递归出口混着写的第n1轮也判断第n轮也判断class Solution { public ListString generateParenthesis(int n) { LinkedListString ans new LinkedList(); generate(ans,n,n,); return ans; } //left记录左括号剩下的right记录右括号剩下的 public void generate(LinkedListString ans,int left, int right, String thisTurnResult){ //第n1轮退出 if(left0 right 0){ ans.add(thisTurnResult); return; } //第n轮退出 //1、只能放左括号需要回溯。这里通过传参的方式进行巧妙的回溯 if(left right){ generate(ans,left-1,right,thisTurnResult(); //2、左括号、右括号都能放 }else{ //一定是左括号先用完 if(left0){ generate(ans,left-1,right,thisTurnResult(); } generate(ans,left,right-1,thisTurnResult)); } } }二、最长有效括号【困难】思路1先遍历一遍把能“对对碰”消掉的都消掉。消不掉的把下标入栈。比如 )( ( ) )(( )(( ) ( )栈里面剩的是[0, 5, 8]然后把栈里剩的下标从后往前两两相减再-1就能得到长度需要注意的就是要给[0, 5, 8]补充上首尾两端首取-1尾取s.length()也就是[-1, 0, 5, 8, s.length()]。这样最大长度就从s.length() - 8 -18 -5 -15 -0 -10 --1-1里面取最大的。时间复杂度OnOn空间复杂度一个栈class Solution { public int longestValidParentheses(String s) { //特殊情况 if(s.length()0 || s.length()1){ return 0; } //1、遍历一遍字符串把能消掉的都消掉消不掉的下标都留在stack里。时间复杂度O(n) DequeInteger stack new LinkedList(); for(int i0; is.length(); i){ if(s.charAt(i)(){ stack.push(i); }else{ if(!stack.isEmpty()s.charAt(stack.peek())(){ stack.pop(); }else{ stack.push(i); } } } //2、遍历stack时间复杂度O(n) //俩特殊情况 if(stack.size()0) return s.length(); if(stack.size()s.length()) return 0; int maxLength 0; int lastIndex s.length(); while(!stack.isEmpty()){ maxLength java.lang.Integer.max(maxLength,lastIndex-stack.peek()-1); lastIndex stack.peek(); stack.pop(); } maxLengthjava.lang.Integer.max(maxLength,lastIndex-(-1)-1); return maxLength; } }思路2同样也是“对对碰消消乐”但只遍历一次遍历完这一次顺便数出来哪一块是最大长度。如下图我计算出下图中红色框框出的每个“对对碰小区间”的长度通过比较得到最大值。这样根本不行因为你无法得知什么时候这个对对碰的小区间该结束了。根本原因在于只有遍历完一遍以后才知道哪个左括号没被消掉你想一边遍历一遍判断根本做不到。比如输入是“( ) ( ( )”对于下标为2的那个左括号你一直抱有后面有右括号和他配对的希望但直到遍历完才发现并没有然而你在遍历的过程当中是判断不出来的。也就是下面这种写法会在输入是“( ) ( ( )”的时候爆雷。class Solution { public int longestValidParentheses(String s) { int length s.length(); //特殊情况 if(length0 ||length1){ return 0; } //只遍历一遍字符串 int maxLength 0; int i0; DequeInteger stack new LinkedList(); while(ilength){ int thisTurnMaxLength 0; while(ilength){ //左括号 if(s.charAt(i)(){ stack.push(i); i; //可以消掉的右括号且没到最后 }else if(s.charAt(i)) !stack.isEmpty() s.charAt(stack.peek())( i!length-1){ stack.pop(); thisTurnMaxLength thisTurnMaxLength2; i; //可以消掉的右括号到最后了 }else if(s.charAt(i)) !stack.isEmpty() s.charAt(stack.peek())( ilength-1){ stack.pop(); thisTurnMaxLength thisTurnMaxLength2; maxLength java.lang.Integer.max(maxLength,thisTurnMaxLength); break; //无法消掉的右括号 }else{ maxLength java.lang.Integer.max(maxLength,thisTurnMaxLength); break; } } i; } return maxLength; } }思路3遍历一次真的数不出来吗动态规划可以做到或者问你如果不用栈你能做到吗