精选-LC

10. 正则表达式匹配

class Solution:
    def isMatch(self, text, pattern):
        dp = [[False] * (len(pattern) + 1) for _ in range(len(text) + 1)]

        dp[-1][-1] = True
        for i in range(len(text), -1, -1):
            for j in range(len(pattern) - 1, -1, -1):
                first_match = i < len(text) and pattern[j] in {text[i], '.'}
                if j+1 < len(pattern) and pattern[j+1] == '*':
                    dp[i][j] = dp[i][j+2] or first_match and dp[i+1][j]
                else:
                    dp[i][j] = first_match and dp[i+1][j+1]

        return dp[0][0]

617. 合并二叉树

class Solution:
    def mergeTrees(self, t1, t2):
        def dfs(r1,r2):
            # 如果 r1和r2中，只要有一个是null，函数就直接返回
            if not (r1 and r2):
                return r1 if r1 else r2
            # 让r1的值 等于  r1和r2的值累加
            # 再递归的计算两颗树的左节点、右节点
            r1.val += r2.val
            r1.left = dfs(r1.left,r2.left)
            r1.right = dfs(r1.right,r2.right)
            return r1
        return dfs(t1,t2)

class Solution(object):
    def mergeTrees(self, t1, t2):
    # 如果 t1和t2中，只要有一个是null，函数就直接返回
        if not (t1 and t2):
            return t2 if not t1 else t1
        queue = [(t1,t2)]
        while queue:
            r1,r2 = queue.pop(0)
            r1.val += r2.val
            # 如果r1和r2的左子树都不为空，就放到队列中
            # 如果r1的左子树为空，就把r2的左子树挂到r1的左子树上
            if r1.left and r2.left:
                queue.append((r1.left,r2.left))
            elif not r1.left:
                r1.left = r2.left
            # 对于右子树也是一样的
            if r1.right and r2.right:
                queue.append((r1.right,r2.right))
            elif not r1.right:
                r1.right = r2.right
        return t1

104. 二叉树的最大深度

class Solution:
    def maxDepth(self, root):
        stack = []
        if root is not None:
            stack.append((1, root))        
        depth = 0
        while stack != []:
            current_depth, root = stack.pop()
            if root is not None:
                depth = max(depth, current_depth)
                stack.append((current_depth + 1, root.left))
                stack.append((current_depth + 1, root.right))        
        return depth

class Solution:
    def maxDepth(self, root):
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1

557. 反转字符串中的单词 III

class Solution:
    def reverseWords(self, s: str) -> str:
        s=s+" "
        stack,res=[],""
        for i in s:
            stack.append(i)
            if i==" ":
                while(stack):
                    res=res+stack.pop()
        return res[1:]

557. 反转字符串中的单词 III

class Solution:
    def reverseWords(self, s: str) -> str:
        s=s+" "
        stack,res=[],""
        for i in s:
            stack.append(i)
            if i==" ":
                while(stack):
                    res=res+stack.pop()
        return res[1:]

344. 反转字符串

难度简单218

class Solution:
    def reverseString(self, s: List[str]) -> None:
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left, right = left + 1, right - 1

206. 反转链表

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 申请两个节点，pre和 cur，pre指向None
        pre = None
        cur = head
        # 遍历链表，while循环里面的内容其实可以写成一行
        # 这里只做演示，就不搞那么骚气的写法了
        while cur:
            # 记录当前节点的下一个节点
            tmp = cur.next
            # 然后将当前节点指向pre
            cur.next = pre
            # pre和cur节点都前进一位
            pre = cur
            cur = tmp
        return pre  
```
#### [206\. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/)
```
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 申请两个节点，pre和 cur，pre指向None
        pre = None
        cur = head
        # 遍历链表，while循环里面的内容其实可以写成一行
        # 这里只做演示，就不搞那么骚气的写法了
        while cur:
            # 记录当前节点的下一个节点
            tmp = cur.next
            # 然后将当前节点指向pre
            cur.next = pre
            # pre和cur节点都前进一位
            pre = cur
            cur = tmp
        return pre  
```
#### [92\. 反转链表 II](https://leetcode-cn.com/problems/reverse-linked-list-ii/)
```
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        # Empty list
        if not head:
            return None

        # Move the two pointers until they reach the proper starting point
        # in the list.
        cur, prev = head, None
        while m > 1:
            prev = cur
            cur = cur.next
            m, n = m - 1, n - 1

        # The two pointers that will fix the final connections.
        tail, con = cur, prev

        # Iteratively reverse the nodes until n becomes 0.
        while n:
            third = cur.next
            cur.next = prev
            prev = cur
            cur = third
            n -= 1

        # Adjust the final connections as explained in the algorithm
        if con:
            con.next = prev
        else:
            head = prev
        tail.next = cur
        return head
```