Day03 leecode#有效的括号#合并两个有序链表

题目描述：

有效的括号
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

题目解读：判断字符串s中的符号能不能配对，符号取出放入栈中，配成功的弹出栈，最后判断栈为空就是真，此外当s中个数为奇数一定不行

初级代码：

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in s:
            if i == '(':
                stack.append('(')
            elif i == '[':
                stack.append('[')
            elif i == '{':
                stack.append('{')
            if not stack:
                return False
            if i == ')':
                if stack[-1] == '(':
                    stack.pop()
                else:
                    return False
            elif i == ']':
                if stack[-1] == '[':
                    stack.pop()
                else:
                    return False
            elif i == '}':
                if stack[-1] == '{':
                    stack.pop()
                else:
                    return False
        if len(stack) != 0:
            return False
        return True

技巧，在遍历到左括号时，对应的右括号入栈！在之后遍历到右括号的时候，只需要比较当前右括号和栈顶元素想不想等就可以了，比左括号直接入栈实现起来要简单不少。

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
 
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item:
                return False
            else:
                stack.pop()
 
        return True if not stack else False

加字典实现：

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
 
        pairs = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = list()
        for ch in s:
            if ch in pairs:                                   
                if not stack or stack[-1] != pairs[ch]:
                    return False
                stack.pop()
            else:
                stack.append(ch)
 
        return not stack

#not stack 是一个布尔表达式，代表栈为空，stack[-1]！=pairs(ch) 代表栈顶元素不匹配 pairs(ch)，也就是说，ch 是右括号，stack[-1]代表的左括号与ch不匹配

题目描述：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

 分析：1、暴力解法

                逐一比较，取最小值

代码：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)  #相当于一个循环
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
 

elif里面自己调用自己函数，相当于循环

val()函数的功能为：将一组字符型数据的数字部分转换成相应的数值型数据

next相当于链表接下去后面只想哪 

小的链表指向大的，当其中一个链表为空，停止