力扣热题100Day06:20. 有效的括号，21. 合并两个有序链表，22. 括号生成

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);}}}