Python 算法题解：链表、二叉树、动态规划等

BM4 合并两个排序的链表

class Solution:
    def Merge(self, pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        dummy = ListNode(0)
        cur = dummy
        p1, p2 = pHead1, pHead2
        while p1 and p2:
            if p1.val <= p2.val:
                cur.next = p1
                p1 = p1.next
            else:
                cur.next = p2
                p2 = p2.next
            cur = cur.next
        cur.next = p1 if p1 else p2
        return dummy.next

BM5 合并 k 个已排序的链表

class Solution:
    def merge(self, p1, p2):
        dummy = ListNode(-1)
        pre = dummy
        while p1 and p2:
            if p1.val <= p2.val:
                pre.next = p1
                p1 = p1.next
            else:
                pre.next = p2
                p2 = p2.next
            pre = pre.next
        pre.next = p1 if p1 else p2
        return dummy.next

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # write code here
        if not lists:
            return None
        res = lists[0]
        for i in range(1, len(lists)):
            res = self.merge(res, lists[i])
        return res

BM6 判断链表中是否有环

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        s = set()
        while head:
            if head in s:
                return True
            else:
                s.add(head)
            head = head.next
        return False

BM7 链表中环的入口结点

class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        slow, fast = pHead, pHead
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        if not fast or not fast.next:
            return None
        slow = pHead
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return slow

BM8 链表中倒数最后 k 个结点

class Solution:
    def FindKthToTail(self, pHead: ListNode, k: int) -> ListNode:
        # write code here
        fast, slow = pHead, pHead
        while k > 0 and fast:
            k -= 1
            fast = fast.next
        if k > 0:
            return None
        while fast:
            fast = fast.next
            slow = slow.next
        return slow

BM9 删除链表的倒数第 n 个节点

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # write code here
        dummy = ListNode(-1)
        dummy.next = head
        pre = dummy
        cur = head
        for i in range(n):
            cur = cur.next
        while cur:
            cur = cur.next
            pre = pre.next
        pre.next = pre.next.next
        return dummy.next

BM10 两个链表的第一个公共结点

class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        p1, p2 = pHead1, pHead2
        len1, len2 = 0, 0
        while p1:
            p1 = p1.next
            len1 += 1
        while p2:
            p2 = p2.next
            len2 += 1
        if len1 < len2:
            pHead1, pHead2 = pHead2, pHead1
            len1, len2 = len2, len1
        p1, p2 = pHead1, pHead2
        for i in range(len1 - len2):
            p1 = p1.next
        while p1 != p2:
            p1 = p1.next
            p2 = p2.next
        return p1

BM11 链表相加 (二)

class Solution:
    def addInList(self, head1: ListNode, head2: ListNode) -> ListNode:
        # write code here
        nums1, nums2 = [], []
        while head1:
            nums1.append(head1.val)
            head1 = head1.next
        while head2:
            nums2.append(head2.val)
            head2 = head2.next
        s, c = 0, 0
        tmp = None
        while nums1 or nums2:
            if nums1 and nums2:
                s = nums1.pop() + nums2.pop() + c
                s1 = s % 10
                c = s // 10
                node = ListNode(s1)
                node.next = tmp
                tmp = node
            elif nums1:
                s = nums1.pop() + c
                s1 = s % 10
                c = s // 10
                node = ListNode(s1)
                node.next = tmp
                tmp = node
            else:
                s = nums2.pop() + c
                s1 = s % 10
                c = s // 10
                node = ListNode(s1)
                node.next = tmp
                tmp = node
        if c:
            node = ListNode(c)
            node.next = tmp
            tmp = node
        return tmp

BM12 单链表的排序

class Solution:
    def sortInList(self, head: ListNode) -> ListNode:
        # write code here
        if not head or not head.next:
            return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None
        left = self.sortInList(head)
        right = self.sortInList(mid)
        dummy = cur = ListNode(-1)
        while left and right:
            if left.val <= right.val:
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next
        cur.next = left if left else right
        return dummy.next

BM13 判断一个链表是否为回文结构

class Solution:
    def isPail(self, head: ListNode) -> bool:
        # write code here
        s = []
        while head:
            s.append(head.val)
            head = head.next
        return s == s[::-1]

BM14 链表的奇偶重排

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # write code here
        if not head or not head.next:
            return head
        evenhead = head.next
        odd, even = head, evenhead
        while even and even.next:
            odd.next = even.next
            odd = even.next
            even.next = odd.next
            even = odd.next
        odd.next = evenhead
        return head

BM15 删除有序链表中重复的元素-I

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # write code here
        cur = head
        if not head or not head.next:
            return head
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

BM16 删除有序链表中重复的元素-II

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # write code here
        dummy = pre = ListNode(-1)
        dummy.next = head
        cur = head
        while cur:
            while cur.next and cur.val == cur.next.val:
                cur = cur.next
            if pre.next == cur:
                pre = cur
            else:
                pre.next = cur.next
            cur = cur.next
        return dummy.next

BM17 二分查找-I

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # write code here
        if not nums:
            return -1
        l, r = 0, len(nums)
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        return -1

BM18 二维数组中的查找

class Solution:
    def Find(self, target: int, array: List[List[int]]) -> bool:
        # write code here
        def binary(target, nums):
            if not nums:
                return False
            l, r = 0, len(nums) - 1
            while l <= r:
                mid = l + (r - l) // 2
                if nums[mid] == target:
                    return True
                elif nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return False
        for nums in array:
            result = binary(target, nums)
            if result:
                return result
        return False

BM19 寻找峰值

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        # write code here
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (r + l) // 2
            if nums[mid] <= nums[mid + 1]:
                l = mid + 1
            else:
                r = mid
        return l

BM20 数组中的逆序对

class Solution:
    def rr(self, data):
        if len(data) < 2:
            return 0
        big, small = [], []
        ans = 0
        pre = data[0]
        for num in data[1:]:
            if num > pre:
                big.append(num)
            else:
                small.append(num)
                ans += len(big) + 1
        return ans + self.rr(big) + self.rr(small)

    def InversePairs(self, nums: List[int]) -> int:
        # write code here
        return self.rr(nums) % 1000000007

BM21 旋转数组的最小数字

class Solution:
    def minNumberInRotateArray(self, nums: List[int]) -> int:
        # write code here
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (l + r) // 2
            if nums[mid] > nums[r]:
                l = mid + 1
            elif nums[mid] < nums[l]:
                r = mid
            else:
                r -= 1
        return nums[l]

BM22 比较版本号

class Solution:
    def compare(self, version1: str, version2: str) -> int:
        # write code here
        nums1 = version1.split('.')
        nums2 = version2.split('.')
        while nums1 and nums2:
            if int(nums1[0]) > int(nums2[0]):
                return 1
            elif int(nums1[0]) < int(nums2[0]):
                return -1
            else:
                nums1.pop(0)
                nums2.pop(0)
        if nums1:
            if int(''.join(nums1)):
                return 1
            else:
                return 0
        elif nums2:
            if int(''.join(nums2)):
                return -1
            else:
                return 0
        else:
            return 0

BM23 二叉树的前序遍历

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # write code here
        def preorder(list1, root):
            if not root:
                return
            list1.append(root.val)
            if root.left:
                preorder(list1, root.left)
            if root.right:
                preorder(list1, root.right)
        list1 = []
        preorder(list1, root)
        return list1

BM24 二叉树的中序遍历

class Solution:
    def inorder(self, l, root):
        if not root:
            return
        if root.left:
            self.inorder(l, root.left)
        l.append(root.val)
        if root.right:
            self.inorder(l, root.right)

    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # write code here
        l = []
        self.inorder(l, root)
        return l

BM25 二叉树的后序遍历

class Solution:
    def postorder(self, l, root):
        if not root:
            return
        self.postorder(l, root.left)
        self.postorder(l, root.right)
        l.append(root.val)

    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # write code here
        l = []
        self.postorder(l, root)
        return l

BM26 二叉树的层序遍历

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        # write code here
        res = []
        if not root:
            return res
        q = []
        q.append(root)
        while q:
            path = []
            for i in range(len(q)):
                root = q.pop(0)
                path.append(root.val)
                if root.left:
                    q.append(root.left)
                if root.right:
                    q.append(root.right)
            res.append(path)
        return res

BM27 按之字形顺序打印二叉树

class Solution:
    def Print(self, pRoot: TreeNode) -> List[List[int]]:
        # write code here
        if not pRoot:
            return []
        q = [pRoot]
        res = []
        flag = True
        while q:
            path = []
            for i in range(len(q)):
                root = q.pop(0)
                path.append(root.val)
                if root.left:
                    q.append(root.left)
                if root.right:
                    q.append(root.right)
            if flag:
                res.append(path)
            else:
                res.append(path[::-1])
            flag = not flag
        return res

BM28 二叉树的最大深度

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # write code here
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

BM29 二叉树中和为某一值的路径 (一)

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        # write code here
        if not root:
            return False
        if not root.left and not root.right:
            if root.val == sum:
                return True
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

BM30 二叉搜索树与双向链表

class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None
        arr = []

        def midtraverse(root):
            if not root:
                return
            midtraverse(root.left)
            arr.append(root)
            midtraverse(root.right)

        midtraverse(pRootOfTree)
        for i in range(len(arr) - 1):
            arr[i].right = arr[i + 1]
            arr[i + 1].left = arr[i]
        return arr[0]

BM31 对称的二叉树

class Solution:
    def isSymmetrical(self, pRoot: TreeNode) -> bool:
        # write code here
        if not pRoot:
            return True

        def isSym(p1, p2):
            if not p1 and not p2:
                return True
            elif not p1 or not p2:
                return False
            elif p1.val != p2.val:
                return False
            else:
                return isSym(p1.left, p2.right) and isSym(p1.right, p2.left)

        return isSym(pRoot.left, pRoot.right)

BM32 合并二叉树

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        # write code here
        if not t1:
            return t2
        if not t2:
            return t1
        head = TreeNode(t1.val + t2.val)
        head.left = self.mergeTrees(t1.left, t2.left)
        head.right = self.mergeTrees(t1.right, t2.right)
        return head

BM33 二叉树的镜像

class Solution:
    def Mirror(self, pRoot: TreeNode) -> TreeNode:
        # write code here
        if not pRoot:
            return None
        tmp = pRoot.left
        pRoot.left = self.Mirror(pRoot.right)
        pRoot.right = self.Mirror(tmp)
        return pRoot

BM34 判断是不是二叉搜索树

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # write code here
        if not root:
            return True

        def recur(root, lower, up):
            if not root:
                return True
            if lower < root.val < up:
                return recur(root.left, lower, root.val) and recur(root.right, root.val, up)
            else:
                return False

        return recur(root, float('-inf'), float('+inf'))

BM35 判断是不是完全二叉树

class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        # write code here
        q = [root]
        flag = True
        while q:
            for i in range(len(q)):
                root = q.pop(0)
                if not root:
                    flag = False
                else:
                    if not flag:
                        return False
                    q.append(root.left)
                    q.append(root.right)
        return True

BM36 判断是不是平衡二叉树

class Solution:
    def IsBalanced_Solution(self, pRoot: TreeNode) -> bool:
        # write code here
        def depth(root):
            if not root:
                return 0
            return max(depth(root.left), depth(root.right)) + 1

        if not pRoot:
            return True
        return abs(depth(pRoot.left) - depth(pRoot.right)) <= 1 and self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)

BM37 二叉搜索树的最近公共祖先

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, o1: int, o2: int) -> int:
        # 该子树没找到，返回 -1
        if not root:
            return -1
        # 该节点是其中某一个节点
        if root.val == o1 or root.val == o2:
            return root.val
        # 左子树寻找公共祖先
        left = self.lowestCommonAncestor(root.left, o1, o2)
        # 右子树寻找公共祖先
        right = self.lowestCommonAncestor(root.right, o1, o2)
        # 左子树为没找到，则在右子树中
        if left == -1:
            return right
        # 右子树没找到，则在左子树中
        if right == -1:
            return left
        # 否则是当前节点
        return root.val

BM38 在二叉树中找到两个节点的最近公共祖先

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, o1: int, o2: int) -> int:
        # write code here
        if not root:
            return -1
        if root.val == o1 or root.val == o2:
            return root.val
        left = self.lowestCommonAncestor(root.left, o1, o2)
        right = self.lowestCommonAncestor(root.right, o1, o2)
        if left == -1:
            return right
        elif right == -1:
            return left
        else:
            return root.val

BM39 序列化二叉树

class Solution:
    def Serialize(self, root):
        def serial(root):
            if not root:
                self.s.append('#')
                return
            self.s.append(root.val)
            serial(root.left)
            serial(root.right)
        self.s = []
        serial(root)
        return self.s

    def Deserialize(self, s):
        # write code here
        s_iter = iter(s)
        t = next(s_iter)
        if t == '#':
            return None
        root = TreeNode(t)
        root.left = self.Deserialize(s_iter)
        root.right = self.Deserialize(s_iter)
        return root

BM40 重建二叉树

class Solution:
    def reConstructBinaryTree(self, preOrder: List[int], vinOrder: List[int]) -> TreeNode:
        # write code here
        if not preOrder:
            return None
        root = TreeNode(preOrder[0])
        r = vinOrder.index(preOrder[0])
        root.left = self.reConstructBinaryTree(preOrder[1:r + 1], vinOrder[:r])
        root.right = self.reConstructBinaryTree(preOrder[r + 1:], vinOrder[r + 1:])
        return root

BM41 输出二叉树的右视图

class Solution:
    def construct(self, preOrder, inOrder):
        if not preOrder:
            return None
        root = TreeNode(preOrder[0])
        mid = inOrder.index(preOrder[0])
        root.left = self.construct(preOrder[1:mid + 1], inOrder[:mid])
        root.right = self.construct(preOrder[mid + 1:], inOrder[mid + 1:])
        return root

    def solve(self, preOrder: List[int], inOrder: List[int]) -> List[int]:
        # write code here
        root = self.construct(preOrder, inOrder)
        if not root:
            return []
        l = []
        q = [root]
        while q:
            size = len(q)
            for i in range(size):
                node = q.pop(0)
                if i == size - 1:
                    l.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return l

BM42 用两个栈实现队列

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, node):
        # write code here
        self.stack1.append(node)

    def pop(self):
        # return xx
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

BM43 包含 min 函数的栈

class Solution:
    A = []
    B = []

    def push(self, node):
        # write code here
        self.A.append(node)
        if not self.B or node <= self.B[-1]:
            self.B.append(node)

    def pop(self):
        # write code here
        val = self.A.pop()
        if self.B[-1] == val:
            self.B.pop()
        return val

    def top(self):
        # write code here
        return self.A[-1]

    def min(self):
        # write code here
        return self.B[-1]

BM44 有效括号序列

class Solution:
    def isValid(self, s: str) -> bool:
        # write code here
        A = []
        for c in s:
            if c == '(' or c == '{' or c == '[':
                A.append(c)
            elif c == ')':
                if not A or A.pop() != '(': 
                    return False
            elif c == ']':
                if not A or A.pop() != '[': 
                    return False
            elif c == '}':
                if not A or A.pop() != '{': 
                    return False
            else:
                return False
        return not A

BM45 滑动窗口的最大值

class Solution:
    def maxInWindows(self, num: List[int], size: int) -> List[int]:
        # 维持一个单调递减队列
        if not size:
            return []
        res = []
        queue = []
        for i in range(len(num)):
            if queue and i - queue[0] + 1 > size:
                queue.pop(0)
            while queue and num[queue[-1]] < num[i]:
                queue.pop()
            queue.append(i)
            if i - size + 1 >= 0:
                res.append(num[queue[0]])
        return res

BM46 最小的 K 个数

class Solution:
    def GetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]:
        # write code here
        input.sort()
        return input[:k]

BM47 寻找第 K 大

class Solution:
    def findKth(self, a: List[int], n: int, K: int) -> int:
        # write code here
        def quicksort(a, l, r):
            if l > r:
                return -1
            pivot = a[l]
            low, up = l, r
            while l < r:
                while l < r and a[r] <= pivot:
                    r -= 1
                while l < r and a[l] >= pivot:
                    l += 1
                a[l], a[r] = a[r], a[l]
            a[l], a[low] = a[low], a[l]
            if l == K - 1:
                return a[l]
            elif l < K - 1:
                return quicksort(a, l + 1, up)
            else:
                return quicksort(a, low, l - 1)
        return quicksort(a, 0, n - 1)

BM48 数据流中的中位数

class Solution:
    val = []

    def Insert(self, num):
        # write code here
        if len(self.val) == 0:
            self.val.append(num)
        else:
            i = 0
            while i < len(self.val):
                if num <= self.val[i]:
                    break
                i = i + 1
            self.val.insert(i, num)

    def GetMedian(self):
        # write code here
        n = len(self.val)
        if n % 2 == 1:
            return self.val[n // 2]
        else:
            return (self.val[n // 2] + self.val[n // 2 - 1]) / 2.0

BM49 表达式求值

class Solution:
    def solve(self, s: str) -> int:
        # write code here
        return eval(s)

BM50 两数之和

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # write code here
        dic = dict()
        for i, num in enumerate(numbers):
            if target - num in dic:
                return [dic[target - num] + 1, i + 1]
            dic[num] = i

BM51 数组中出现次数超过一半的数字

from collections import Counter

class Solution:
    def MoreThanHalfNum_Solution(self, numbers: List[int]) -> int:
        # write code here
        dic = Counter(numbers)
        l = len(numbers)
        for num in numbers:
            if dic[num] > l / 2:
                return num

BM52 数组中只出现一次的两个数字

from collections import Counter

class Solution:
    def FindNumsAppearOnce(self, nums: List[int]) -> List[int]:
        # write code here
        dic = Counter(nums)
        res = []
        for num in dic:
            if dic[num] == 1:
                res.append(num)
        return sorted(res)

BM53 缺失的第一个正整数

class Solution:
    def minNumberDisappeared(self, nums: List[int]) -> int:
        # write code here
        A = set()
        for num in nums:
            A.add(num)
        i = 1
        while True:
            if i not in A:
                return i
            i += 1

BM54 三数之和

class Solution:
    def threeSum(self, num: List[int]) -> List[List[int]]:
        # write code here
        res = []
        num.sort()
        n = len(num)
        i = 0
        while i < n - 2:
            j = i + 1
            k = n - 1
            while j < k:
                s = num[i] + num[j] + num[k]
                if s < 0:
                    j += 1
                elif s > 0:
                    k -= 1
                else:
                    res.append([num[i], num[j], num[k]])
                    j += 1
                    k -= 1
            i += 1
        res = [list(i) for i in set(tuple(i) for i in res)]
        return sorted(res)

BM55 没有重复项数字的全排列

class Solution:
    def permute(self, num: List[int]) -> List[List[int]]:
        # write code here
        def dfs(num, path, res):
            if not num:
                res.append(path)
                return
            for i in range(len(num)):
                dfs(num[:i] + num[i + 1:], path + [num[i]], res)
        path, res = [], []
        dfs(num, path, res)
        return sorted(res)

BM56 有重复项数字的全排列

class Solution:
    def permuteUnique(self, num: List[int]) -> List[List[int]]:
        # write code here
        def dfs(num, path, res):
            if not num:
                res.append(path)
                return
            for i in range(len(num)):
                dfs(num[:i] + num[i + 1:], path + [num[i]], res)
        res, path = [], []
        dfs(num, path, res)
        res = [list(i) for i in set(tuple(i) for i in res)]
        return sorted(res)

BM57 岛屿数量

class Solution:
    def solve(self, grid: List[List[str]]) -> int:
        # write code here
        def dfs(grid, i, j):
            if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0':
                return
            grid[i][j] = '0'
            dfs(grid, i - 1, j)
            dfs(grid, i, j - 1)
            dfs(grid, i + 1, j)
            dfs(grid, i, j + 1)

        m, n = len(grid), len(grid[0])
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    dfs(grid, i, j)
        return count

BM58 字符串的排列

class Solution:
    def Permutation(self, str: str) -> List[str]:
        # write code here
        def dfs(num, path, res):
            if not num:
                res.append(''.join(path))
                return
            for i in range(len(num)):
                dfs(num[0:i] + num[i + 1:], path + [num[i]], res)
        l = list(str)
        path, res = [], []
        dfs(l, path, res)
        return sorted(set(res))

BM59 N 皇后问题

class Solution:
    def Nqueen(self, n: int) -> int:
        # write code here
        def dfs(cols, d1, d2):
            r = len(cols)
            if r == n:
                res.append(cols)
                return
            for i in range(n):
                if i not in cols and r - i not in d1 and r + i not in d2:
                    dfs(cols + [i], d1 + [r - i], d2 + [r + i])
        cols, d1, d2 = [], [], []
        res = []
        dfs(cols, d1, d2)
        return len(res)

BM60 括号生成

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # write code here
        def dfs(l, r, path, res):
            if l > r or l < 0 or r < 0:
                return
            if l == 0 and r == 0:
                res.append(path)
                return
            dfs(l - 1, r, path + '(', res)
            dfs(l, r - 1, path + ')', res)
        path, res = '', []
        dfs(n, n, path, res)
        return res

BM61 矩阵最长递增路径

class Solution:
    def solve(self, matrix: List[List[int]]) -> int:
        # write code here
        m, n = len(matrix), len(matrix[0])
        mem = [[0] * n for i in range(m)]
        res = 0

        def dfs(i, j):
            if mem[i][j] != 0:
                return mem[i][j]
            mem[i][j] = 1
            for newx, newy in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                if 0 <= newx < m and 0 <= newy < n and matrix[newx][newy] > matrix[i][j]:
                    mem[i][j] = max(mem[i][j], dfs(newx, newy) + 1)
            return mem[i][j]

        for i in range(m):
            for j in range(n):
                dfs(i, j)
                res = max(res, mem[i][j])
        return res

BM62 斐波那契数列

class Solution:
    def Fibonacci(self, n: int) -> int:
        # write code here
        dp = [0] * n
        dp[0], dp[1] = 1, 1
        for i in range(2, n):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n - 1]

BM63 跳台阶

class Solution:
    def jumpFloor(self, number: int) -> int:
        # write code here
        n = number
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

BM64 最小花费爬楼梯

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # write code here
        n = len(cost)
        if n == 0:
            return 0
        elif n == 1:
            return cost[0]
        else:
            dp = [0] * (n + 1)
            for i in range(2, n + 1):
                dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1])
            return dp[n]

BM65 最长公共子序列 (二)

class Solution:
    def LCS(self, s1: str, s2: str) -> str:
        # write code here
        if not s1 or not s2:
            return "-1"
        len1, len2 = len(s1), len(s2)
        dp = [[0 for i in range(len2 + 1)] for j in range(len1 + 1)]
        for i in range(1, len1 + 1):
            for j in range(1, len2 + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        i, j = len1, len2
        s = []
        while dp[i][j] != 0:
            if dp[i][j] == dp[i - 1][j]:
                i -= 1
            elif dp[i][j] == dp[i][j - 1]:
                j -= 1
            elif dp[i][j] > dp[i - 1][j - 1]:
                i -= 1
                j -= 1
                s.append(s1[i])
        return ''.join(s[::-1])

BM66 最长公共子串

class Solution:
    def LCS(self, str1: str, str2: str) -> str:
        # write code here
        maxlen = 0
        res = ""
        for i in range(len(str1)):
            if (str1[i - maxlen:i + 1] in str2):
                res = str1[i - maxlen:i + 1]
                maxlen += 1
        return res

BM67 不同路径的数目 (一)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # write code here
        dp = [[0] * n for i in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

BM68 矩阵的最小路径和

class Solution:
    def minPathSum(self, matrix: List[List[int]]) -> int:
        # write code here
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * n for i in range(m)]
        dp[0][0] = matrix[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] + matrix[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j - 1] + matrix[0][j]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = matrix[i][j] + min(dp[i - 1][j], dp[i][j - 1])
        return dp[m - 1][n - 1]

BM69 把数字翻译成字符串

class Solution:
    def solve(self, nums: str) -> int:
        # write code here
        n = len(nums)
        if n == 1:
            if '1' <= nums[0] <= '9':
                return 1
            else:
                return 0
        dp = [1] * (n + 1)
        for i in range(2, n + 1):
            if nums[i - 2:i] == '10' or nums[i - 2:i] == '20':
                dp[i] = dp[i - 2]
            elif '11' <= nums[i - 2:i] <= '19' or '21' <= nums[i - 2:i] <= '26':
                dp[i] = dp[i - 1] + dp[i - 2]
            elif nums[i - 1] == '0':
                return 0
            else:
                dp[i] = dp[i - 1]
        return dp[n]

BM70 兑换零钱 (一)

class Solution:
    def minMoney(self, arr: List[int], aim: int) -> int:
        # write code here
        dp = [float('+inf')] * (aim + 1)
        dp[0] = 0
        if not arr:
            return -1
        for i in range(1, aim + 1):
            for j in range(len(arr)):
                if arr[j] <= i:
                    dp[i] = min(dp[i], dp[i - arr[j]] + 1)
        return dp[aim] if dp[aim] != float('+inf') else -1

BM71 最长上升子序列 (一)

class Solution:
    def LIS(self, arr: List[int]) -> int:
        # write code here
        n = len(arr)
        if not n:
            return 0
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if arr[j] < arr[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

BM72 连续子数组的最大和

class Solution:
    def FindGreatestSumOfSubArray(self, array: List[int]) -> int:
        # write code here
        if not array:
            return 0
        n = len(array)
        s, res = float('-inf'), float('-inf')
        for i in range(n):
            s = max(s + array[i], array[i])
            res = max(res, s)
        return res

BM73 最长回文子串

class Solution:
    def getLongestPalindrome(self, A: str) -> int:
        # write code here
        def judge(A, l, r):
            if l > r:
                return 0
            while l >= 0 and r < len(A) and A[l] == A[r]:
                l -= 1
                r += 1
            return r - l - 1

        res = 1
        for i in range(len(A) - 1):
            len1 = judge(A, i, i)
            len2 = judge(A, i, i + 1)
            res = max(res, max(len1, len2))
        return res

BM74 数字字符串转化成 IP 地址

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        # write code here
        res = []
        n = len(s)
        i = 1
        while i < 4 and i < n - 2:
            j = i + 1
            while j < i + 4 and j < n - 1:
                k = j + 1
                while k < j + 4 and k < n:
                    if n - k > 3:
                        k += 1
                        continue
                    a = s[:i]
                    b = s[i:j]
                    c = s[j:k]
                    d = s[k:]
                    if int(a) > 255 or int(b) > 255 or int(c) > 255 or int(d) > 255:
                        k += 1
                        continue
                    if ((len(a) > 1 and int(a[0]) == 0) or (len(b) > 1 and int(b[0]) == 0) or (len(c) > 1 and int(c[0]) == 0) or (len(d) > 1 and int(d[0]) == 0)):
                        k += 1
                        continue
                    res.append(a + '.' + b + '.' + c + '.' + d)
                    k += 1
                j += 1
            i += 1
        return res

BM75 编辑距离 (一)

class Solution:
    def editDistance(self, str1: str, str2: str) -> int:
        # write code here
        m, n = len(str1), len(str2)
        dp = [[0] * (n + 1) for i in range(m + 1)]
        for i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] + 1
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j - 1] + 1
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
        return dp[m][n]

BM76 正则表达式匹配

class Solution:
    def match(self, str: str, pattern: str) -> bool:
        # write code here
        l = len(pattern)
        if l == 0:
            return not str
        elif l == 1:
            if len(str) == l and pattern[0] in {str[0], '.'}:
                return True
            else:
                return False
        else:
            firstmatch = str and pattern[0] in {str[0], '.'}
            if pattern[1] == '*':
                return self.match(str, pattern[2:]) or firstmatch and self.match(str[1:], pattern)
            else:
                return firstmatch and self.match(str[1:], pattern[1:])

BM77 最长的括号子串

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # write code here
        st = []
        start = -1
        res = 0
        for i in range(len(s)):
            if s[i] == '(':
                st.append(i)
            else:
                if not st:
                    start = i
                else:
                    st.pop()
                    if st:
                        res = max(res, i - st[-1])
                    else:
                        res = max(res, i - start)
        return res

BM78 打家劫舍 (一)

class Solution:
    def rob(self, nums: List[int]) -> int:
        # write code here
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        return dp[n - 1]

BM79 打家劫舍 (二)

class Solution:
    def caculate(self, nums):
        n = len(nums)
        dp = [0] * n
        if n == 1:
            return nums[0]
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
        return dp[n - 1]

    def rob(self, nums: List[int]) -> int:
        # write code here
        l1 = self.caculate(nums[:-1])
        l2 = self.caculate(nums[1:])
        return max(l1, l2)

BM80 买卖股票的最好时机 (一)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # write code here
        n = len(prices)
        dp = [[0] * 2 for i in range(n)]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
            dp[i][1] = max(dp[i - 1][1], -prices[i])
        return dp[n - 1][0]

BM81 买卖股票的最好时机 (二)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # write code here
        n = len(prices)
        dp = [[0] * 2 for i in range(n)]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        return dp[n - 1][0]

BM82 买卖股票的最好时机 (三)

import sys

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # write code here
        n = len(prices)
        dp = [[-sys.maxsize - 1] * 5 for i in range(n)]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1, n):
            dp[i][0] = dp[i - 1][0]
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])
        return max(dp[n - 1][2], max(0, dp[n - 1][4]))

BM83 字符串变形

class Solution:
    def trans(self, s: str, n: int) -> str:
        lst = s.split(' ')
        lst.reverse()
        return s.swapcase()

BM84 最长公共前缀

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ''
        for i in range(len(strs[0])):
            for s in strs[1:]:
                if i >= len(s) or s[i] != strs[0][i]:
                    return strs[0][:i]
        return strs[0]

BM85 验证 IP 地址

class Solution:
    def solve(self, IP):
        # write code here
        if '.' in IP:
            for ip in IP.split('.'):
                if ip.isdigit() is False or ip == '' or ip[0] == '0' or (not 0 <= int(ip) <= 255):
                    return 'Neither'
            return 'IPv4'
        if ':' in IP:
            for ip in IP.split(':'):
                if ip == '' or (len(ip) > 1 and len(ip) == ip.count('0')) or not all(c in '0123456789abcdefABCDEF' for c in ip):
                    return 'Neither'
            return 'IPv6'

BM86 大数加法

class Solution:
    def solve(self, s: str, t: str) -> str:
        s = [int(c) for c in s]
        t = [int(c) for c in t]
        res = []
        digi = 1
        carry = 0
        while s or t:
            if s and t:
                SUM = s.pop() + t.pop() + carry
                carry = SUM // 10
                s1 = SUM % 10
                res.insert(0, str(s1))
            elif s:
                SUM = s.pop() + carry
                carry = SUM // 10
                s1 = SUM % 10
                res.insert(0, str(s1))
            else:
                SUM = t.pop() + carry
                carry = SUM // 10
                s1 = SUM % 10
                res.insert(0, str(s1))
        if carry != 0:
            res.insert(0, str(carry))
        return ''.join(res)

BM87 合并两个有序的数组

class Solution:
    def merge(self, A, m, B, n):
        # write code here
        i = m - 1
        j = n - 1
        k = m + n - 1
        while i >= 0 and j >= 0:
            if A[i] > B[j]:
                A[k] = A[i]
                k -= 1
                i -= 1
            else:
                A[k] = B[j]
                k -= 1
                j -= 1
        if i < 0:
            while j >= 0:
                A[k] = B[j]
                k -= 1
                j -= 1

BM88 判断是否为回文字符串

class Solution:
    def judge(self, str: str) -> bool:
        # write code here
        l, r = 0, len(str) - 1
        while l < r:
            if str[l] == str[r]:
                l += 1
                r -= 1
                continue
            else:
                return False
        return True

BM89 合并区间

class Solution:
    def merge(self, intervals: List[Interval]) -> List[Interval]:
        # write code here
        res = []
        n = len(intervals)
        if n == 0:
            return res
        intervals.sort(key=lambda x: x.start)
        res.append(intervals[0])
        for i in range(1, n):
            if res[-1].end >= intervals[i].start:
                res[-1].end = max(res[-1].end, intervals[i].end)
            else:
                res.append(intervals[i])
        return res

BM90 最小覆盖子串

class Solution:
    def check(self, hash):
        for k, v in hash.items():
            if v < 0:
                return False
        return True

    def minWindow(self, S: str, T: str) -> str:
        # write code here
        res = len(S) + 1
        hash = dict()
        for c in T:
            if c in hash:
                hash[c] -= 1
            else:
                hash[c] = -1
        l, r = 0, 0
        cnt = len(S) + 1
        left, right = -1, -1
        while r < len(S):
            c = S[r]
            if c in hash:
                hash[c] += 1
            while self.check(hash):
                if cnt > r - l + 1:
                    cnt = r - l + 1
                    left = l
                    right = r
                t = S[l]
                if t in hash:
                    hash[S[l]] -= 1
                l += 1
            r += 1
        if left == -1:
            return ""
        return S[left:right + 1]

BM91 反转字符串

class Solution:
    def solve(self, str: str) -> str:
        # write code here
        return str[::-1]

BM92 最长无重复子数组

class Solution:
    def maxLength(self, arr: List[int]) -> int:
        # write code here
        l, r = 0, 0
        hash = dict()
        res = 0
        while r < len(arr):
            if arr[r] in hash:
                hash[arr[r]] += 1
            else:
                hash[arr[r]] = 1
            while hash[arr[r]] > 1:
                hash[arr[l]] -= 1
                l += 1
            res = max(res, r - l + 1)
            r += 1
        return res

BM93 盛水最多的容器

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # write code here
        n = len(height)
        if n < 2:
            return 0
        l, r = 0, n - 1
        res = 0
        while l < r:
            temp = min(height[l], height[r]) * (r - l)
            res = max(res, temp)
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return res

BM94 接雨水问题

class Solution:
    def maxWater(self, arr: List[int]) -> int:
        # write code here
        n = len(arr)
        if n <= 2:
            return 0
        l, r = 0, n - 1
        maxl, maxr = -1, -1
        res = 0
        while l < r:
            maxl = max(maxl, arr[l])
            maxr = max(maxr, arr[r])
            if maxl < maxr:
                res += maxl - arr[l]
                l += 1
            else:
                res += maxr - arr[r]
                r -= 1
        return res

BM95 分糖果问题

class Solution:
    def candy(self, arr: List[int]) -> int:
        # write code here
        n = len(arr)
        sweet = [1] * len(arr)
        for i in range(1, n):
            if arr[i] > arr[i - 1]:
                sweet[i] = sweet[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if arr[i] > arr[i + 1] and sweet[i] <= sweet[i + 1]:
                sweet[i] = sweet[i + 1] + 1
        return sum(sweet)

BM96 主持人调度（二）

class Solution:
    def minmumNumberOfHost(self, n: int, startEnd: List[List[int]]) -> int:
        # write code here
        start, end = list(), list()
        for i in range(len(startEnd)):
            start.append(startEnd[i][0])
            end.append(startEnd[i][1])
        start.sort()
        end.sort()
        i, j, res = 0, 0, 0
        for i in range(len(start)):
            if start[i] >= end[j]:
                j += 1
            else:
                res += 1
        return res

BM97 旋转数组

class Solution:
    def solve(self, n: int, m: int, a: List[int]) -> List[int]:
        # write code here
        return a[-(m % n):] + a[:-(m % n)]

BM98 螺旋矩阵

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # write code here
        res = list()
        while matrix:
            res += matrix.pop(0)
            matrix = list(zip(*matrix))[::-1]
        return res

BM99 顺时针旋转矩阵

class Solution:
    def rotateMatrix(self, mat: List[List[int]], n: int) -> List[List[int]]:
        # write code here
        for i in range(n):
            for j in range(i):
                mat[i][j], mat[j][i] = mat[j][i], mat[i][j]
        for i in range(n):
            mat[i].reverse()
        return mat

BM100 设计 LRU 缓存结构

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.pre = None

class Solution:
    def __init__(self, capacity: int):
        # write code here
        self.cap = capacity
        self.hash = dict()
        self.head = None
        self.tail = None

    def get(self, key: int) -> int:
        # write code here
        if key in self.hash:
            if self.hash[key].pre != None:
                self.freshListNode(self.hash[key])
            return self.hash[key].val[0]
        else:
            return -1

    def set(self, key: int, value: int) -> None:
        # write code here
        value = [value, key]
        if key in self.hash:
            self.hash[key].val = value
            if self.hash[key].pre != None:
                self.freshListNode(self.hash[key])
            return
        if self.cap > 0:
            ele = ListNode(value)
            self.hash[key] = ele
            self.addOneNode(ele)
            self.cap -= 1
        else:
            del self.hash[self.tail.val[1]]
            self.hash[key] = self.tail
            self.tail.val = value
            if self.tail.pre != None:
                self.freshListNode(self.tail)

    def freshListNode(self, ele):
        ele.pre.next = ele.next
        if self.tail == ele:
            self.tail = ele.pre
        else:
            ele.next.pre = ele.pre
        ele.pre = None
        self.head.pre = ele
        ele.next = self.head
        self.head = ele

    def addOneNode(self, ele):
        if self.head == None:
            self.head = ele
            self.tail = ele
        else:
            ele.pre = None
            ele.next = self.head
            self.head.pre = ele
            self.head = ele
# Your Solution object will be instantiated and called as such:
# solution = Solution(capacity)
# output = solution.get(key)
# solution.set(key,value)