海淀区网站建设公司苏州seo营销
20. 有效的括号
题目链接：20. 有效的括号 - 力扣（Leetcode）
思路：使用栈
（1）遇到左括号就将其对应的右括号压入到栈中
（2）如果遇到右括号
a. 如果弹出的元素与当前不等，false
b. 如果相等就弹出
（3）遍历s结束后，若栈还是不为空，说明有多余的右括号，返回false
Java代码：
class Solution {public boolean isValid(String s) {Stack<Character> st = new Stack<>();for(int i = 0; i < s.length();i++){char ch = s.charAt(i);//遇到左括号就压入对应的右括号if(ch == '('){st.push(')');}else if(ch == '{'){st.push('}');}else if(ch == '['){st.push(']');}else if(st.isEmpty() || ch != st.peek()){return false;}else{st.pop();}}//遍历结束后，如果st不为空，说明有多余的右括号return st.isEmpty();}
}21. 合并两个有序链表
题目链接：21. 合并两个有序链表 - 力扣（Leetcode）
看完别人文章后的思路（该文章链接里的热评有对于递归的理解，一定要看！！！）： 文章链接 21. 合并两个有序链表 - 力扣（Leetcode）
递归三部曲
（1）确定函数返回值及参数
（2）确定终止条件
如果两个链表有一个为空，说明可以终止
（3）确定单层递归逻辑
Java代码：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1 == null){return list2;}else if(list2 == null){return list1;}else if(list1.val < list2.val){//list1的值小，所以考虑list1节点的链接//下一个节点要看下一层递归了，就看list1.next(因为list1已经在该层递归选了) 和 list2list1.next = mergeTwoLists(list1.next,list2);//告诉上一次递归，我返回了个节点给你，你链接这个节点return list1;}else{list2.next = mergeTwoLists(list1,list2.next);return list2;}}
}22. 括号生成
题目链接：21. 合并两个有序链表 - 力扣（Leetcode）
思路：组合问题，且题目中提到说是要是有效的括号组合，考虑使用回溯算法，回溯三部曲
（1）确定回溯函数返回值和参数
返回值：void
参数：String str，int left（剩余左括号的个数）,int right（剩余右括号的个数）
（2）确定终止条件
如果left == 0 && right == 0，收获str
（3）确定单层递归逻辑
看完官方题解的反思：
（1）自己不知道如何确定有效的括号组合：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合
（2）剩余左括号总数要小于等于右括号
Java代码：
class Solution {List<String> res = new ArrayList<>();public List<String> generateParenthesis(int n) {if(n <= 0){return res;}getParenthesis("",n,n);return res;}private void getParenthesis(String str,int left, int right) {if(left == 0 && right == 0 ){res.add(str);return;}if(left == right){//剩余左右括号数相等，下一个只能用左括号getParenthesis(str+"(",left-1,right);}else if(left < right){//剩余左括号小于右括号，下一个可以用左括号也可以用右括号if(left > 0){getParenthesis(str+"(",left-1,right);}getParenthesis(str+")",left,right-1);}}}