LeetCode 热题 HOT 100 经典算法题 Python 解法汇总 | 极客日志

Python算法

LeetCode 热题 HOT 100 经典算法题 Python 解法汇总

本文整理了 LeetCode 热题 HOT 100 中的经典算法题 Python 解法，涵盖树、字符串、搜索查找、排列、链表、位运算、数组计算、数据结构设计、矩阵及数学计算等多个模块。内容包括二叉树遍历、动态规划、双指针、滑动窗口、回溯法等核心算法思想，并提供了完整的代码实现与思路解析，适合 Python 开发者进行算法训练与面试准备。

星河入梦发布于 2026/3/30更新于 2026/4/131 浏览

树

104. 二叉树的最大深度【简单】

思路：递归、最终深度需要 +1

 ():
     ():
        
         root  :
             
        :
            left_height = .maxDepth(root.left)
            right_height = .maxDepth(root.right)
             (left_height, right_height) +

class Solution(object):
    def inorderTraversal(self, root):
        """ :type root: Optional[TreeNode] :rtype: List[int] """
        if root is None:
            return []
        else:
            # 中序
            return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

# 前序
return [root.val] + self.inorderTraversal(root.left) + self.inorderTraversal(root.right)
# 后序
return self.inorderTraversal(root.left) + self.inorderTraversal(root.right) + [root.val]

class Solution(object):
    def isValidBST(self, root):
        """ :type root: Optional[TreeNode] :rtype: bool """
        def solve(root):
            if root is None:
                return []
            else:
                return solve(root.left) + [root.val] + solve(root.right)
        tree_values = solve(root)
        ans = True
        for i in range(len(tree_values) - 1):
            if tree_values[i] >= tree_values[i + 1]:
                ans = False
        return ans

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """ :type root: Optional[TreeNode] :rtype: int """
        self.ans = 1  # 最大 node 数（全局变量）
        def solve(node):
            if node is None:
                return 0
            left_depth = solve(node.left)
            right_depth = solve(node.right)
            total_length = left_depth + right_depth
            self.ans = max(self.ans, total_length + 1)  # 加上 root 的 node 数
            return max(left_depth, right_depth) + 1  # node 数
        solve(root)
        return self.ans - 1  # 得到的 node 数减 1 得到路径长

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        # 特殊情况
        if not root1:
            return root2
        if not root2:
            return root1
        # 深度优先搜索
        merge_tree = TreeNode(val=root1.val + root2.val)
        merge_tree.left = self.mergeTrees(root1.left, root2.left)
        merge_tree.right = self.mergeTrees(root1.right, root2.right)
        return merge_tree

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        ans = []
        queue = deque()
        queue.append(root)
        while queue:
            n = len(queue)
            cur_level = []
            for _ in range(n):  # 当前层的 node 数
                node = queue.popleft()  # 丢掉最前面的一项（当前层）
                cur_level.append(node.val)  # 当前层的 node 值都放进一个 sublist
                if node.left:
                    queue.append(node.left)  # 把下一层存进来
                if node.right:
                    queue.append(node.right)  # 把下一层存进来
            ans.append(cur_level)
        return ans

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left = right
        root.right = left
        return root

class Solution:
    def lowestCommonAncestor(self, root:'TreeNode', p:'TreeNode', q:'TreeNode') ->'TreeNode':
        if not root:
            return None
        if root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        return root

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum:int)->bool:
        if not root:
            return False
        if not root.left and not root.right:  # 叶子结点
            return targetSum == root.val  # 当叶子结点的值等于当前'还需要凑多少'时，说明存在这个路径
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

class Trie:
    def __init__(self):
        self.children = [None]*26  # 指向子节点的指针数组：26 个字母
        self.isEnd = False  # 该节点是否是字符串的结尾字母
    
    def searchPrefix(self, prefix:str):
        node = self
        for c in prefix:
            idx = ord(c)-ord('a')
            if not node.children[idx]:  # 如果该字符不在指针数组中，搜索不到
                return None
            node = node.children[idx]  # 能搜索到该字符，移动指针到子节点
        return node
    
    def insert(self, word:str)->None:
        node = self
        for c in word:
            idx = ord(c)-ord('a')
            if not node.children[idx]:  # 如果该字符不在指针数组中，创建新的子节点
                node.children[idx]= Trie()
            node = node.children[idx]  # 创建子节点之后，移动指针到子节点
        node.isEnd = True  # 移动到字符串末尾，给节点打一个标记
    
    def search(self, word:str)->bool:
        node = self.searchPrefix(word)
        return (node is not None) and (node.isEnd)  # 注意需要 isEnd=True，说明字符串被完整搜索到了
    
    def startsWith(self, prefix:str)->bool:
        node = self.searchPrefix(prefix)
        return node is not None

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode])->bool:
        if p is None or q is None:  # 如果有一棵树是 None，则都必须是 None
            return p is None and q is None
        # 当前节点相同，并且递归左右树分别相同
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

class Solution:
    def isSymmetric(self, root: Optional[TreeNode])->bool:
        def helper(p, q):
            if not p or not q:  # 如果有一棵树是 None，则都必须是 None
                return not p and not q
            # 当前节点相同，但是递归左右树相反（镜像对称！）
            return p.val == q.val and helper(p.left, q.right) and helper(p.right, q.left)
        return helper(root.left, root.right)  # 把一棵树看作左右两棵树

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        # 广度优先搜索模板
        queue = deque()
        queue.append(root)
        ans = []
        while queue:
            n = len(queue)  # 当前层的 node 数
            ans.append(queue[-1].val)  # 将当前层最右侧的 node 存进答案
            for _ in range(n):
                node = queue.popleft()  # 取出当前层的每个 node
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return ans

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        queue = [root]
        ans = []
        layer_idx = 0
        while queue:
            n = len(queue)
            cur_level = []
            for _ in range(n):
                node = queue.pop(0)
                cur_level.append(node.val)
                if layer_idx % 2 == 1:  # 注意是在为下一层存，所以 layer_idx=0 时应该从右往左存，1 时从左往右存
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                else:
                    if node.right:
                        queue.append(node.right)
                    if node.left:
                        queue.append(node.left)
            ans.append(cur_level)
            layer_idx += 1
        return ans

class Solution:
    def __init__(self):
        self.ans = -float('inf')  # 定义全局最大路径答案
    
    def maxPathSum(self, root: Optional[TreeNode])->int:
        if not root:
            return 0
        def dfs(node):
            if not node:
                return 0
            left = max(dfs(node.left), 0)  # 左树最大路径，要>0 才可取
            right = max(dfs(node.right), 0)  # 右树最大路径，要>0 才可取
            cur_sum = node.val + left + right  # 当前路径和
            self.ans = max(self.ans, cur_sum)  # 更新答案的最大路径
            return node.val + max(left, right)  # 返回当前节点下的最大路径
        dfs(root)
        return self.ans

# self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int])-> Optional[TreeNode]:
        if not nums:
            return None
        # 从中间位置将元素分成两拨，左右分别递归构造搜索数
        n = len(nums)//2
        left = self.sortedArrayToBST(nums[:n])
        right = self.sortedArrayToBST(nums[n+1:])
        return TreeNode(nums[n], left, right)

class Solution(object):
    def isValid(self, s):
        """ :type s: str :rtype: bool """
        if len(s)%2==1:
            return False
        else:
            # 预定义匹配对
            pairs_dict = {")":"(","}":"{","]":"["}
            stack = []  # 空栈
            for c in s:
                if c in pairs_dict:  # 是右符号 待匹配
                    if not stack or stack[-1]!= pairs_dict[c]:
                        return False
                    stack.pop()
                else:  # 是左符号 入栈
                    stack.append(c)
            # 最终 stack 必须被消耗为空才行
            if not stack:
                return True
            else:
                return False

class Solution(object):
    def longestValidParentheses(self, s):
        """ :type s: str :rtype: int """
        stack = []
        ans = 0  # 存储最大长度的答案
        stack.append(-1)  # 为了后面计算下标差值时，有足够的元素减
        for i in range(len(s)):
            if s[i]=="(":
                stack.append(i)
            else:
                stack.pop()
                if stack:  # 非空
                    ans = max(ans, i - stack[-1])
                else:
                    stack.append(i)
        return ans

class Solution(object):
    def countSubstrings(self, s):
        """ :type s: str :rtype: int """
        n = len(s)
        def solve(left, right):
            cnt = 0  # 中心扩展法
            while 0<= left < n and 0<= right < n and s[left]== s[right]:
                cnt += 1
                left -= 1
                right += 1
            return cnt
        ans = 0
        for i in range(n):
            ans += solve(i, i)  # 奇数长度回文
            ans += solve(i, i+1)  # 偶数长度回文
        return ans

class Solution:
    def wordBreak(self, s:str, wordDict: List[str])->bool:
        n = len(s)
        dp = [True]+[False]* n
        for i in range(n):
            for j in range(i+1, n+1):
                if dp[i] and s[i:j] in wordDict:  # 前面的字符串满足，且后面的字符串满足
                    dp[j]=True
        return dp[-1]

class Solution:
    def decodeString(self, s:str)->str:
        stack = []
        for c in s:
            if c !=']':
                stack.append(c)  # 不是']'则入栈
            if c ==']':  # 是']'则出栈
                # 提取'[]'之间的所有字母
                chars = ''
                while stack and stack[-1]!='[':
                    chars = stack[-1]+ chars  # 把'['右边的字符弹出
                    stack.pop()
                stack.pop()  # 把栈顶的'['弹出
                # 提取'['左边的数字
                num = ''
                while stack and stack[-1].isdigit():
                    num = stack[-1]+ num
                    stack.pop()
                num = int(num)
                chars_repeat = num * chars
                stack.append(chars_repeat)
        ans = ''
        while stack:
            ans = stack[-1]+ ans  # 可能有多段结果需要拼接
            stack.pop()
        return ans

class Solution:
    def minDistance(self, word1:str, word2:str)->int:
        m, n = len(word1),len(word2)
        dp =[[0]*(n +1)for _ inrange(m +1)]  # (m+1)x(n+1)：dp[i][j]表示 word1 前 i 个字符=>word2 前 j 个字符的操作数（多加 1 行 1 列目的：word1/word2 长度为 0 的边界情况）
        for i inrange(m +1):  # word2 长度为 0，从 word1=>到长度为 i 的 word2 需要删除 i 步
            dp[i][0]= i
        for i inrange(n +1):  # word1 长度为 0，从 word1=>长度为 i 的 word2 需要插入 i 步
            dp[0][i]= i
        for i inrange(1, m +1):
            for j inrange(1, n +1):
                if word1[i -1]== word2[j -1]:  # 如果某 2 个字符相同，则这一步不需要操作
                    dp[i][j]= dp[i -1][j -1]
                else:  # 需要操作
                    dp[i][j]=min(dp[i][j -1], dp[i -1][j], dp[i -1][j -1])+1  # 增、删、改三种情况取最小
                    """ dp[i][j - 1] + 1: 增
                        dp[i - 1][j] + 1: 删
                        dp[i - 1][j - 1] + 1: 改 """
        return dp[m][n]  # 从 word1 的前 m 个字符=>word2 的前 n 个字符的最小操作数

class Solution:
    def convertToTitle(self, columnNumber:int)->str:
        ans = []
        while columnNumber >0:
            columnNumber -=1  # A 是从 1 开始编码的
            ch =chr(columnNumber %26+ord('A'))
            ans.append(ch)
            columnNumber //=26
        return"".join(ans[::-1])

class Solution:
    def addStrings(self, num1:str, num2:str)->str:
        ans =""
        carry =0
        while num1 or num2:
            x =int(num1[-1])if num1 else0  # 取最后一位
            y =int(num2[-1])if num2 else0  # 取最后一位
            sum_val = x + y + carry
            value =sum_val%10
            ans =str(value)+ ans
            carry =sum_val//10  # 0 or 1
            num1 = num1[:-1]  # 丢掉最后一位
            num2 = num2[:-1]  # 丢掉最后一位
        if carry:
            ans =str(carry)+ ans
        return ans

class Solution:
    def findDisappearedNumbers(self, nums: List[int])-> List[int]:
        n = len(nums)
        ans = []
        flag = [0]*(n +1)  # 因为元素范围是 1～n，所以只在下标 1～n 的位置记录
        for x in nums:
            flag[x]=1
        for i inrange(1, n +1):  # 只在下标 1～n 的位置记录
            if flag[i]==0:
                ans.append(i)
        return ans

class Solution(object):
    def singleNumber(self, nums):
        """ :type nums: List[int] :rtype: int """
        nums_set =set(nums)  # 去重
        nums_set_sum =sum(nums_set)  # 去重后集合的和
        gap = nums_set_sum *2-sum(nums)  # 去重后两倍元素的和 - 原来的和
        return gap

class Solution(object):
    def search(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: int """
        left =0
        right =len(nums)-1
        while left <= right:
            mid =(left + right)//2
            if nums[mid]== target:
                return mid
            elif nums[mid]> target:
                right = mid -1
            elif nums[mid]< target:
                left = mid +1
        return-1

class Solution:
    def maxProfit(self, prices: List[int])->int:
        ans =0
        n =len(prices)
        for i inrange(0, n):
            for j inrange(i+1, n):
                cur_profit = prices[j]- prices[i]
                ans =max(ans, cur_profit)
        return ans

class Solution:
    def maxProfit(self, prices: List[int])->int:
        min_price =1e4
        max_profit =0
        n =len(prices)
        for i inrange(n):
            min_price =min(min_price, prices[i])  # 动态更新当前最低点
            max_profit =max(max_profit, prices[i]- min_price)  # 记录当前最大收益
        return max_profit

class Solution:
    def maxProfit(self, prices: List[int])->int:
        n =len(prices)
        ans =0  # 如果仅一条数据（如 [1]），则当天买入卖出，结果是 0
        for i inrange(1, n):
            ans +=max(prices[i]- prices[i -1],0)
        return ans

class Solution:
    def maxProfit(self, prices: List[int])->int:
        n =len(prices)
        dp =[[0]*2for _ inrange(n)]  # 2D 数组：dp[a][b]表示第 a 天的是否持有股票（0=否，1=是）
        dp[0][0], dp[0][1]=0,-prices[0]  # 第 0 天：不持有股票利润 0，持有股票利润-prices[0]
        for i inrange(1, n):
            dp[i][0]=max(dp[i-1][0], dp[i-1][1]+ prices[i])  # 第 i 天不持有股票，如 1）第 i-1 天也不持有，不操作；2）第 i-1 天持有，现卖出
            dp[i][1]=max(dp[i-1][1], dp[i-1][0]- prices[i])  # 第 i 天持有股票，如 1）第 i-1 天也持有，不操作；2）第 i-1 天不持有，现买入
        return dp[n-1][0]  # 最后持有股票一定不如清仓

class Solution:
    def majorityElement(self, nums: List[int])->int:
        n =len(nums)
        threshold = n //2
        count_dict ={}
        for num in nums:
            if num in count_dict.keys():
                count_dict[num]+=1
            else:
                count_dict.update({num:1})
        ans =0
        max_cnt =0
        for k, v in count_dict.items():
            if v >= threshold and v > max_cnt:  # 不仅要数量达到阈值，还需要取数量最大的那个
                max_cnt = v
                ans = k
        return ans

class Solution:
    def dailyTemperatures(self, temperatures: List[int])-> List[int]:
        n =len(temperatures)
        ans =[0]* n
        for i inrange(n):
            for j inrange(i+1, n):
                if temperatures[j]> temperatures[i]:
                    ans[i]= j - i
                    break
        return ans

class Solution:
    def dailyTemperatures(self, temperatures: List[int])-> List[int]:
        n =len(temperatures)
        ans =[0]* n
        stack =[]  # 用栈存 index
        for i inrange(n-1,-1,-1):
            while stack and temperatures[i]>= temperatures[stack[-1]]:  # 单调栈
                stack.pop()
            if stack:  # 右边存在更大的数（如不存在，则就是 0）
                ans[i]= stack[-1]- i
            stack.append(i)  # 更新栈顶
        return ans

class Solution:
    def dailyTemperatures(self, temperatures: List[int])-> List[int]:
        n =len(temperatures)
        ans =[0]* n
        stack =[]  # 用栈存 index
        for i inrange(n):
            while stack and temperatures[i]> temperatures[stack[-1]]:
                j = stack.pop()
                ans[j]= i - j
            stack.append(i)
        return ans

class Solution:
    def twoSum(self, nums: List[int], target:int)-> List[int]:
        n =len(nums)
        for i inrange(n):
            for j inrange(i+1, n):
                if nums[i]+ nums[j]== target:
                    return[i, j]

class Solution:
    def twoSum(self, nums: List[int], target:int)-> List[int]:
        n =len(nums)
        hash_table ={}
        for i inrange(n):
            diff = target - nums[i]  # 先判断再 update 哈希表，避免重复使用当前元素
            if diff in hash_table:
                return[i, hash_table[diff]]
            else:
                hash_table.update({nums[i]: i})

class Solution:
    def twoSum(self, numbers: List[int], target:int)-> List[int]:
        n =len(numbers)
        hash_table ={}
        for i inrange(n):
            diff = target - numbers[i]  # 先判断再 update 哈希表，避免重复使用当前元素
            if diff in hash_table:
                return[i +1, hash_table[diff]+1]if i +1< hash_table[diff]+1else[hash_table[diff]+1, i +1]  # index 从 1 开始，并且注意输出 index 升序
            else:
                hash_table[numbers[i]]= i

class Solution:
    def twoSum(self, numbers: List[int], target:int)-> List[int]:
        n =len(numbers)
        left, right =0, n -1  # 相向双指针
        while left < right:
            s = numbers[left]+ numbers[right]
            if s < target:  # 如果求和偏小，说明 left 应该向右走
                left +=1
            elif s > target:  # 如果求和偏大，说明 right 应该向左走
                right -=1
            else:
                return[left +1, right +1]

class Solution:
    def threeSum(self, nums: List[int])-> List[List[int]]:
        n =len(nums)
        nums.sort()  # 有序，即可用相向双指针
        ans =[]
        for i inrange(n-2):
            a = nums[i]
            if i >=1and a == nums[i-1]:  # 如果当前遍历的值和上一步相同，就跳过（避免重复），注意第 2 个元素开始才有前置元素
                continue
            left, right = i +1, n -1  # 相向双指针
            while left < right:
                s = a + nums[left]+ nums[right]
                if s <0:
                    left +=1
                elif s >0:
                    right -=1
                elif s ==0:
                    ans.append([a, nums[left], nums[right]])  # 结果
                    # 继续找结果：left 指针向右（避开重复）、right 指针向左（避开重复）
                    left +=1
                    while left < right and nums[left]== nums[left -1]:
                        left +=1
                    right -=1
                    while left < right and nums[right]== nums[right +1]:
                        right -=1
        return ans

class MinStack:
    def __init__(self):
        self.stack =[]
        self.min_stack =[float('inf')]
    
    def push(self, val:int)->None:
        self.stack.append(val)
        self.min_stack.append(min(self.min_stack[-1], val))
    
    def pop(self)->None:
        self.stack.pop()
        self.min_stack.pop()
    
    def top(self)->int:
        return self.stack[-1]
    
    def getMin(self)->int:
        return self.min_stack[-1]

class Solution:
    def topKFrequent(self, nums: List[int], k:int)-> List[int]:
        n =len(nums)
        ans =[]
        hash_table ={}
        for i inrange(n):
            if nums[i]notin hash_table:
                hash_table[nums[i]]=1
            else:
                hash_table[nums[i]]+=1
        # 降序排列：[(k1, v1), (k2, v2), ...]
        rank_value =sorted(hash_table.items(), key=lambda x:x[1], reverse=True)
        i =0
        for key, value in rank_value:
            i +=1
            ans.append(key)
            if i == k:
                break
        return ans

class Solution:
    def findDuplicate(self, nums: List[int])->int:
        if not nums:
            return-1
        n =len(nums)
        hash_table =set()
        for i inrange(n):
            if nums[i]in hash_table:
                return nums[i]
            hash_table.add(nums[i])

class Solution:
    def trap(self, height: List[int])->int:
        n =len(height)
        max_left, max_right =0,0  # 记录从左往右最高点、左右往左最高点
        left, right =0, n -1  # 相向双指针
        ans =0
        while left < right:
            max_left, max_right =max(height[left], max_left),max(height[right], max_right)  # 动态更新两边的最高点
            # 较低的那边去接雨水（说明有容纳雨水的可能性）
            if max_left <= max_right:
                ans += max_left - height[left]  # 统计低洼的情况
                left +=1
            if max_left > max_right:
                ans += max_right - height[right]  # 统计低洼的情况
                right -=1
        return ans

class Solution:
    def maxArea(self, height: List[int])->int:
        n =len(height)
        if n ==2:
            returnmin(height[0], height[1])*1
        ans =0
        left, right =0, n -1
        while left < right:
            width = right - left
            cur_s = width *min(height[left], height[right])
            ans =max(ans, cur_s)  # 面积取决于最矮的那边，所以哪边矮哪边就往前走一步，保留高的那边
            if height[left]<= height[right]:
                left +=1
            elif height[left]> height[right]:
                right -=1
        return ans

class Solution:
    def countTarget(self, scores: List[int], target:int)->int:
        n =len(scores)
        def helper(target):
            left, right =0, n -1
            while left <= right:
                mid =(left + right)//2
                if scores[mid]< target:
                    left = mid +1
                elif scores[mid]>= target:
                    right = mid -1
            return left
        l = helper(target)
        r = helper(target +1)
        return r - l

class Solution:
    def searchRange(self, nums: List[int], target:int)-> List[int]:
        if not nums:
            return[-1,-1]
        n =len(nums)
        def helper(target):
            left, right =0, n -1
            while left <= right:
                mid =(left + right)//2
                if nums[mid]< target:
                    left = mid +1
                else:
                    right = mid -1
            return left
        l = helper(target)
        r = helper(target +1)
        if r > l:
            return[l, r -1]
        return[-1,-1]

class Solution:
    def findSpecialInteger(self, arr: List[int])->int:
        n =len(arr)
        if n ==1:
            return arr[0]
        thre =int(n *0.25)
        hash_table ={}
        for a in arr:
            if a notin hash_table:
                hash_table[a]=1
            else:
                hash_table[a]+=1
            # 得先统计上当前的元素
            if hash_table[a]> thre:
                return a

class Solution:
    def findKthLargest(self, nums: List[int], k:int)->int:
        import random
        def quick_select(nums, k):
            pivot = random.choice(nums)  # 随机选择基准数
            big, equal, small =[],[],[]  # 将大于、小于、等于 pivot 的元素划分到三个列表中
            for x in nums:
                if x > pivot:
                    big.append(x)
                elif x < pivot:
                    small.append(x)
                else:
                    equal.append(x)
            iflen(big)>= k:  # 第 k 大的元素在 big 中，递归划分 big
                return quick_select(big, k)
            iflen(big)+len(equal)< k:  # 第 k 大的元素在 small 中，递归划分 small
                return quick_select(small, k -len(big)-len(equal))
            return pivot  # 第 k 大的元素在 equal 中，返回 pivot
        return quick_select(nums, k)

class Solution:
    def minSubArrayLen(self, target:int, nums: List[int])->int:
        n =len(nums)
        ans = n +1
        s =0  # 初始化滑窗中的和
        left =0  # 初始化滑窗的左端点
        # 枚举滑窗右端点
        for right, x inenumerate(nums):  # x: nums[right]
            s += x  # 加一个右边的端点进来
            while s >= target:
                ans =min(ans, right - left +1)
                s -= nums[left]
                left +=1
        return ans if ans <= n else0

class Solution:
    def minSubArrayLen(self, target:int, nums: List[int])->int:
        n =len(nums)
        ans = n +1
        s =0  # 初始化滑窗中的和
        left =0  # 初始化滑窗的左端点
        # 枚举滑窗右端点
        for right, x inenumerate(nums):  # x: nums[right]
            s += x  # 加一个右边的端点进来
            while s - nums[left]>= target:  # 如果减去左端点还>=targe，可以安全丢掉
                s -= nums[left]
                left +=1
            if s >= target:
                ans =min(ans, right - left +1)
        return ans if ans <= n else0

class Solution:
    def minWindow(self, s:str, t:str)->str:
        from collections import Counter
        cnt_win = Counter()  # s 的滑窗字符计数器
        cnt_t = Counter(t)  # t 的字符计数器
        ans_left, ans_right =-float('inf'), float('inf')
        left =0
        for right, x inenumerate(s):  # 枚举右端点
            cnt_win[x]+=1
            while cnt_win >= cnt_t:  # s 滑窗能覆盖 t
                if right - left < ans_right - ans_left:  # 找到了更短字符串，更新答案
                    ans_left, ans_right = left, right
                cnt_win[s[left]]-=1  # 丢掉左端点
                left +=1
        return s[ans_left:ans_right+1]if ans_left >=0else""

class Solution:
    def lengthOfLongestSubstring(self, s:str)->int:
        n =len(s)
        ans =0
        visited =set()  # 用 set 检测重复元素
        left =0
        for right, x inenumerate(s):  # x: s[right]
            while x in visited:  # 当前元素重复了
                visited.remove(s[left])  # 丢掉左端点
                left +=1
            visited.add(x)  # 加上右端点
            ans =max(ans, right - left +1)  # 更新最大长度答案
        return ans

class Solution(object):
    def sortArray(self, nums):
        """ :type nums: List[int] :rtype: List[int] """
        # 冒泡排序 O(n^2)
        n =len(nums)
        for i inrange(1, n):  # n-1 趟：每趟可以将一个大数放到最后
            for j inrange(0, n-i):  # 无需再到最后了
                if nums[j]> nums[j+1]:
                    nums[j], nums[j+1]= nums[j+1], nums[j]
        return nums

class Solution:
    def sortArray(self, nums: List[int])-> List[int]:
        import random
        def quicksort(arr, low, high):
            if low < high:
                pivot_idx = partition(arr, low, high)
                quicksort(arr, low, pivot_idx -1)
                quicksort(arr, pivot_idx +1, high)
            return arr
        
        def partition(arr, low, high):
            r = random.randint(low, high)
            arr[r], arr[high]= arr[high], arr[r]
            pivot = arr[high]
            slow = fast = low
            while fast <= high:
                if arr[fast]< pivot:
                    arr[fast], arr[slow]= arr[slow], arr[fast]
                    slow +=1
                fast +=1
            arr[high], arr[slow]= arr[slow], arr[high]
            return slow
        
        n =len(nums)
        nums = quicksort(nums,0, n -1)
        return nums

class Solution(object):
    def moveZeroes(self, nums):
        """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """
        left =0
        for right inrange(len(nums)):
            if nums[right]!=0:
                nums[right], nums[left]= nums[left], nums[right]
                left +=1
        return nums

class Solution(object):
    def moveZeroes(self, nums):
        """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """
        right =len(nums)-1
        left =0
        while left < right:
            if nums[left]==0:
                nums[right], nums[left]= nums[left], nums[right]
                right -=1
                left +=1
        return nums

class Solution(object):
    def moveZeroes(self, nums):
        """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """
        idx_non_zero =0
        for i inrange(len(nums)):
            if nums[i]!=0:
                nums[idx_non_zero]= nums[i]
                idx_non_zero +=1
        for i inrange(idx_non_zero,len(nums)):
            nums[i]=0
        return nums

class Solution:
    def sortColors(self, nums: List[int])->None:
        """ Do not return anything, modify nums in-place instead. """
        n =len(nums)
        p0, p2 =0, n -1
        i =0
        while i <= p2:
            if nums[i]==2:
                nums[i], nums[p2]= nums[p2], nums[i]
                p2 -=1
            elif nums[i]==0:
                nums[i], nums[p0]= nums[p0], nums[i]
                p0 +=1
                i +=1
            elif nums[i]==1:
                i +=1

class Solution:
    def reconstructQueue(self, people: List[List[int]])-> List[List[int]]:
        n =len(people)
        ans =[]
        # 身高 h 降序，相同 h 中 k 升序：先处理高个子，相同身高里先处理前面人少的
        people_sort =sorted(people, key=lambda x:(-x[0], x[1]))
        for person in people_sort:
            ans.insert(person[1], person)
        return ans

class Solution:
    def sortedSquares(self, nums: List[int])-> List[int]:
        n =len(nums)
        left, right =0, n -1
        ans =[]
        while left <= right:
            if nums[left]**2<= nums[right]**2:
                ans.append(nums[right]**2)
                right -=1
            elif nums[left]**2> nums[right]**2:
                ans.append(nums[left]**2)
                left +=1
        return ans[::-1]

class Solution:
    def nextPermutation(self, nums: List[int])->None:
        """ Do not return anything, modify nums in-place instead. """
        n =len(nums)
        # 从右往左找到第一个小于右侧邻居的元素 nums[i]，nums[i]右侧一定是递减
        # 为什么 nums[i]右侧一定是递减？反证法：如果不是，说明 nums[i]不应该是第一个被找到的
        i = n -2
        while i >=0and nums[i]>= nums[i +1]:
            i -=1
        # 如果找到了 nums[i]，继续找 nums[i]右边大于它且最小的元素 nums[j]
        if i >=0:
            j = n -1
            while nums[j]<= nums[i]:
                j -=1
            nums[i], nums[j]= nums[j], nums[i]  # 交换两个元素
        # 将右侧的元素翻转：从递减到递增，保证右侧字典序最小
        # 如果找不到（即 i=-1），说明当前是最大排列，直接翻转即可得到最小排列
        left, right = i +1, n -1
        while left < right:
            nums[left], nums[right]= nums[right], nums[left]
            left +=1
            right -=1

class Solution(object):
    def groupAnagrams(self, strs):
        """ :type strs: List[str] :rtype: List[List[str]] """
        d ={}
        for s in strs:
            sorted_s =''.join(sorted(s))  # 把字符串按字符排序
            d[sorted_s]= d.get(sorted_s,[])+[s]  # 返回 d 中 key=sorted_s 的 value，如果 value 为空，返回 []
            # 字典存储：key=排序后的字符串，value=原始的字符串
            # 将具有相同排序后的字符串放在同一个 value 列表中
        return d.values()

class Solution(object):
    def subsets(self, nums):
        """ :type nums: List[int] :rtype: List[List[int]] """
        ans =[[]]  # 初始化包含空列表的答案
        for num in nums:
            tmp =[]
            for i in ans:
                tmp.append([num]+ i)
            ans += tmp
        return ans

class Solution:
    def permute(self, nums: List[int])-> List[List[int]]:
        n =len(nums)
        ans =[]
        # 回溯法
        def dfs(start):
            # 固定一个元素
            if start == n:  # 所有元素都确定，记录当前组合
                ans.append(nums[:])  # 注意！这里需要用 list(nums)活着 nums[:]，相当于对 nums 进行了一次浅拷贝
                return
            for i inrange(start, n):
                nums[i], nums[start]= nums[start], nums[i]  # 交换元素
                dfs(start +1)  # 下一层递归
                nums[i], nums[start]= nums[start], nums[i]  # 恢复交换
        dfs(0)  # 从第一个元素开始固定
        return ans

class Solution:
    def permuteUnique(self, nums: List[int])-> List[List[int]]:
        n =len(nums)
        ans =[]
        # 回溯法
        def dfs(start):
            # 固定一个元素
            if start == n:  # 所有元素都确定，记录当前组合
                ans.append(nums[:])  # 注意！这里需要用 list(nums)活着 nums[:]，相当于对 nums 进行了一次浅拷贝
                return
            dic =set()  # 用集合去重
            for i inrange(start, n):
                if nums[i]in dic:  # 判断存在性，进行剪枝
                    continue
                dic.add(nums[i])  # 更新集合
                # 下面就是正常的交换->递归->恢复流程
                nums[i], nums[start]= nums[start], nums[i]  # 交换元素
                dfs(start +1)  # 下一层递归
                nums[i], nums[start]= nums[start], nums[i]  # 恢复交换
        dfs(0)  # 从第一个元素开始固定
        return ans

class Solution:
    def goodsOrder(self, goods:str)-> List[str]:
        n =len(goods)
        lst =list(goods)  # 必须把字符串转 list，才支持在回溯时交换元素
        ans =[]
        # 回溯法
        def dfs(start):
            if start == n:
                ans.append(''.join(lst))
                return
            for i inrange(start, n):
                lst[i], lst[start]= lst[start], lst[i]
                dfs(start +1)
                lst[i], lst[start]= lst[start], lst[i]
        dfs(0)
        returnlist(set(ans))  # list 中元素是字符串时，可以直接转 set 然后再转 list 去重

class Solution(object):
    def reverseList(self, head):
        """ :type head: Optional[ListNode] :rtype: Optional[ListNode] """
        prev =None
        curr = head
        while curr:
            next_node = curr.next  # 先把本来的 curr.next 拿到
            curr.next= prev  # curr 的后面接 prev，即链表方向反转
            # prev 和 curr 一起往后走
            prev = curr
            curr =next_node
        return prev

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left:int, right:int)-> Optional[ListNode]:
        if not head:
            return None
        # 用 p0 节点定位 left 位置左边的节点
        # 需要加入哨兵节点，为什么？因为当 left=1 时，left 位置左边不存在节点，哨兵节点用于处理特殊情况
        dummy = ListNode(next=head)
        p0 = dummy
        for _ inrange(left -1):
            p0 = p0.next  # 此时，p0 走到了 left 位置的左边
        cur, prev = p0.next,None
        for _ inrange(right - left +1):  # 反转中间的元素
            next_node = cur.next
            cur.next= prev
            prev = cur
            cur =next_node
        # 处理最后两个指向
        p0.next.next= cur  # 把图中的 1 指向 5
        p0.next= prev  # 把图中的 1 指向 4
        return dummy.next

class Solution(object):
    def isPalindrome(self, head):
        """ :type head: Optional[ListNode] :rtype: bool """
        l =[]
        while head:
            l.append(head.val)
            head = head.next
        ans =(l == l[::-1])
        return ans

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode)-> Optional[ListNode]:
        if not headA or not headB:
            return None
        link_set =set()  # 用 hash 避免 timeout，因为 hash 的搜素是 O(1)，而 list 是 O(n)
        cur = headA
        while cur:
            link_set.add(cur)
            cur = cur.next
        cur = headB
        while cur:
            if cur in link_set:  # 判断节点的存在性
                return cur
            cur = cur.next
        return None

class Solution:
    def hasCycle(self, head: Optional[ListNode])->bool:
        if not head:
            return False
        link_set =set()  # 用 hash 而不是 list 的原因：hash 的搜索更快
        cur = head
        while cur:
            if cur in link_set:  # 如果是环形，则会返回 True 跳出循环
                return True
            link_set.add(cur)
            cur = cur.next  # 如果不是环形，则一定会执行到 cur=None 跳出循环
        return False

class Solution:
    def hasCycle(self, head: Optional[ListNode])->bool:
        if not head:
            return False
        # 核心：设置快慢指针，慢指针每次走 1 步，快指针走 2 步
        # 如果不存在环，则快指针会走到尽头，返回 False
        # 如果存在环，则快指针迟早会在环中追上慢指针，返回 True
        slow, fast = head, head.next
        while fast and fast.next:
            if fast == slow:
                return True
            slow = slow.next
            fast = fast.next.next
        return False

class Solution:
    def detectCycle(self, head: Optional[ListNode])-> Optional[ListNode]:
        if not head:
            return None
        link_set =set()  # 用 hash 而不是 list 的原因：hash 的搜索更快
        cur = head
        while cur:
            if cur in link_set:  # 如果是环形，则会返回 cur 跳出循环
                return cur
            link_set.add(cur)
            cur = cur.next  # 如果不是环形，则一定会执行到 cur=None 跳出循环
        return None

class Solution:
    def detectCycle(self, head: Optional[ListNode])-> Optional[ListNode]:
        if not head:
            return None
        # 设置快慢指针，定位相遇时 slow 指针在环中的位置
        fast, slow = head, head
        flag =False  # flag 标记是否有环
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                flag =True
                break
        # 如果不存在环，则返回 None
        if not flag:
            return None
        # 如果存在环，则进一步计算环的入口
        # 再加入一个指针从头开始走，速度为 1，和环中的 slow 指针相遇时，即环的入口
        tmp = head
        while tmp != slow:
            slow = slow.next
            tmp = tmp.next
        return slow

class Solution:
    def sortList(self, head: Optional[ListNode])-> Optional[ListNode]:
        cur = head  # 链表转列表
        head_list =[]
        while cur:
            head_list.append(cur.val)
            cur = cur.next
        head_list.sort()  # 列表升序排列
        # 列表转链表
        cur = head
        i =0
        while cur:
            cur.val = head_list[i]
            i +=1
            cur = cur.next
        return head

class Solution:
    def sortList(self, head: Optional[ListNode])-> Optional[ListNode]:
        if not head or not head.next:
            return head
        # 步骤 1. 递归每次分割成 2 组
        slow, fast = head, head.next
        while fast and fast.next:  # 定位中点的位置
            slow = slow.next  # slow 走一步
            fast = fast.next.next  # fast 走两步
        mid = slow.next
        slow.next=None
        left = self.sortList(head)  # 递归
        right = self.sortList(mid)  # 递归
        # 步骤 2. 迭代两两合并在一起（有序）
        ans = ListNode()
        cur = ans
        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
        # 处理不同长度
        if left:
            cur.next= left
        else:
            cur.next= right
        return ans.next

class Solution:
    def deleteNode(self, node):
        """ :type node: ListNode :rtype: void Do not return anything, modify node in-place instead. """
        node.val = node.next.val
        node.next= node.next.next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n:int)-> Optional[ListNode]:
        dummy = ListNode(next=head)  # 在头节点前面加一个 dummy 节点（更方便支持删除头节点的边界情况）
        right = dummy
        for _ inrange(n):  # 右指针先往右走 n 步
            right = right.next
        left = dummy  # 左指针初始和右指针保持 n 的距离
        while right.next:  # 右指针走到末尾前，左右指针同时向右走
            left = left.next
            right = right.next
        left.next= left.next.next  # 右指针走到末尾了，左指针刚到'待删除节点'的前面，开始跳过
        return dummy.next  # dummy 是头节点之前的虚拟节点，所以要返回真正的头节点 dummy.next

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode])-> Optional[ListNode]:
        if not head:
            return None
        cur = head
        while cur.next:  # 如果存在下一个节点
            if cur.next.val == cur.val:  # 该节点和下一个节点值相同
                cur.next= cur.next.next  # 跳过下一个节点
            else:
                cur = cur.next  # 继续
        return head

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode])-> Optional[ListNode]:
        dummy = ListNode(next=head)
        cur = dummy
        while cur.next and cur.next.next:  # 保证下个节点和下下个节点存在
            val = cur.next.val  # 下个节点的值
            if cur.next.next.val == val:  # 发现相同值的节点了！要通过循环从 cur.next 开始跳过
                while cur.next and cur.next.val == val:
                    cur.next= cur.next.next
            else:
                cur = cur.next
        return dummy.next

class Solution:
    def removeElements(self, head: Optional[ListNode], val:int)-> Optional[ListNode]:
        if not head:
            return None
        dummy = ListNode(next=head)  # 哨兵节点，处理头节点被删除的情况
        cur = dummy
        while cur and cur.next:
            if cur.next.val == val:  # 注意提前一个节点开始判断，方便跨过
                cur.next= cur.next.next
            else:
                cur = cur.next
        return dummy.next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode])-> Optional[ListNode]:
        ans = ListNode(0)  # 用来存答案的链表
        cur = ans
        carry =0  # 进位
        while l1 or l2:  # 两个链表长度可能不同，只要有一个没遍历完，则继续算
            x = l1.val if l1 else0  # 长度不够就补 0
            y = l2.val if l2 else0  # 长度不够就补 0
            s = x + y + carry
            value = s %10
            carry = s //10
            cur.next= ListNode(value)
            cur = cur.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        if carry:
            cur.next= ListNode(carry)
        return ans.next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode])-> Optional[ListNode]:
        if not list1 and not list2:
            return None
        ans = ListNode()  # 答案链表，初始化一个 dummy 节点，答案节点都存储在后面
        cur = ans
        while list1 and list2:  # 先处理共同长度的部分
            # 思路：先取较小的，然后移动其指针
            if list1.val < list2.val:
                cur.next= list1
                list1 = list1.next
            else:
                cur.next= list2
                list2 = list2.next
            cur = cur.next
        # 处理不等长情况：可能有一个链表更长，还没有被遍历完
        if list1:
            cur.next= list1
        elif list2:
            cur.next= list2
        return ans.next  # 跳过初始化的第一个 dummy 节点

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]])-> Optional[ListNode]:
        # 先写两个有序链表的合并
        def mergeTwoLists(list1, list2):
            dummy = ListNode()  # 哨兵节点简化代码
            cur = dummy
            while list1 and list2:  # 先处理链表等长的部分
                if list1.val < list2.val:
                    cur.next= list1
                    list1 = list1.next
                else:
                    cur.next= list2
                    list2 = list2.next
                cur = cur.next
            # 链表不等长，还有剩余的情况
            if list1:
                cur.next= list1
            elif list2:
                cur.next= list2
            return dummy.next
        
        # 主代码
        n =len(lists)
        if n ==0:
            return None
        if n ==1:
            return lists[0]
        left = self.mergeKLists(lists[:n //2])  # 递归合并前半部分
        right = self.mergeKLists(lists[n //2:])  # 递归合并后半部分
        return mergeTwoLists(left, right)  # 合并前后两个部分

class Solution:
    def hammingDistance(self, x:int, y:int)->int:
        bit_num =32
        dist =0  # 初始化答案
        for i inrange(bit_num):
            one_bit_x =1if x &(1<< i)else0  # x 的每一位是否为 1
            one_bit_y =1if y &(1<< i)else0  # y 的每一位是否为 1
            if one_bit_x != one_bit_y:
                dist +=1
        return dist

class Solution(object):
    def hammingDistance(self, x, y):
        """ :type x: int :type y: int :rtype: int """
        xor =bin(x ^ y)  # 得到二进制异或结果
        dist =list(xor[2:]).count('1')  # 统计 1 的数目
        return dist

class Solution:
    def countBits(self, n:int)-> List[int]:
        bit_num =32
        ans =[]
        for i inrange(n +1):  # n 个 sample
            one_bit =[]
            for b inrange(bit_num):
                if(1<< b)& i:
                    one_bit.append(1)
            ans.append(sum(one_bit))
        return ans

class Solution(object):
    def countBits(self, n):
        """ :type n: int :rtype: List[int] """
        ans =[]
        for i inrange(n+1):
            bin_num =list(bin(i))[2:]
            ans.append(bin_num.count('1'))
        return ans

class Solution:
    def hammingWeight(self, n:int)->int:
        bit_num =32
        one_bit =[]  # 记录每一位是否为 1（是=1，否=0）
        for i inrange(bit_num):  # if n & (2 ** i):
            if n &(1<< i):  # 从低往高判断每一位是否为 1（比如 5&010=101&010=000，则说明第 2 位不是 1）
                one_bit.append(1)
        ans =sum(one_bit)
        return ans

class Solution:
    def isPowerOfTwo(self, n:int)->bool:
        if n <=0:  # 2 的幂次一定是正数！
            return False
        num_bits =32
        bits =[]
        for i inrange(num_bits):
            cur_bit =1if(2** i)& n else0
            bits.append(cur_bit)
        # 2 的幂次转二进制一定有且只有一个 1
        returnTrueif bits.count(1)==1elseFalse

class Solution:
    def productExceptSelf(self, nums: List[int])-> List[int]:
        n =len(nums)
        ans =[0]* n
        # 计算前缀元素乘积
        front_mul =[1]+[0]*(n -1)  # [1, 0, 0, ...]
        for i inrange(1, n):
            front_mul[i]= front_mul[i -1]* nums[i -1]
        # 计算后缀元素乘积
        behind_mul =[0]*(n -1)+[1]  # [0, ..., 0, 1]
        for i inrange(n-2,-1,-1):
            behind_mul[i]= behind_mul[i +1]* nums[i +1]
        # 把前缀乘积和后缀成绩再乘起来得到答案
        for i inrange(n):
            ans[i]= front_mul[i]* behind_mul[i]
        return ans

class Solution:
    def maxProduct(self, nums: List[int])->int:
        n =len(nums)
        if n ==1:
            return nums[0]
        cur_max =[0]* n
        cur_min =[0]* n
        ans = nums[0]
        cur_max[0], cur_min[0]= nums[0], nums[0]
        for i inrange(n):
            cur_max[i]=max(nums[i]* cur_min[i -1], nums[i]* cur_max[i -1], nums[i])
            cur_min[i]=min(nums[i]* cur_min[i -1], nums[i]* cur_max[i -1], nums[i])
            ans =max(ans, cur_max[i])
        return ans

class Solution:
    def maxSubArray(self, nums: List[int])->int:
        n =len(nums)
        if n ==1:
            return nums[0]
        dp =[0]* n
        dp[0]= nums[0]
        for i inrange(n):
            dp[i]=max(nums[i], dp[i -1]+ nums[i])
        returnmax(dp)

class Solution:
    def lengthOfLIS(self, nums: List[int])->int:
        n =len(nums)
        if n ==1:
            return1
        dp =[1]* n
        for i inrange(n):
            for j inrange(i):
                if nums[i]> nums[j]:
                    dp[i]=max(dp[i], dp[j]+1)
        returnmax(dp)

class Solution:
    def longestConsecutive(self, nums: List[int])->int:
        n =len(nums)
        hash_set =set(nums)  # 去重且查找元素的效率高
        ans =0
        for num in hash_set:
            if num -1in hash_set:  # 说明 num 不是连续序列的开头
                continue  # 跳过，因为希望从连续序列的开头开始计数
            elif num -1notin hash_set:  # 说明 num 是连续序列的开头，可以计数了
                length_from_here =1  # 从本次起点出发，能达到的最大长度
                cur_num = num
                while cur_num +1in hash_set:
                    cur_num +=1
                    length_from_here +=1
                ans =max(ans, length_from_here)  # 更新最大答案长度
        return ans

class Solution:
    def findAnagrams(self, s:str, p:str)-> List[int]:
        window_size =len(p)
        n =len(s)
        ans =[]
        p_cnt =[0]*26
        for c in p:
            p_cnt[ord(c)-ord('a')]+=1
        for i inrange(n):
            window_s = s[i:i+window_size]  # "cba"
            iflen(window_s)!= window_size:
                continue
            # if sorted(window_s) == sorted(p): # O(nlogn)会 timeout
            # ans.append(i)
            window_cnt =[0]*26
            for c in window_s:
                window_cnt[ord(c)-ord('a')]+=1
            # print(p_cnt, window_cnt)
            if p_cnt == window_cnt:
                ans.append(i)
        return ans

class Solution:
    def findAnagrams(self, s:str, p:str)-> List[int]:
        window_size =len(p)
        n =len(s)
        ans =[]
        window_cnt =[0]*26  # 维持一个随着窗口更新的字符统计分布（每次只改变 2 个）
        p_cnt =[0]*26
        for c in p:
            p_cnt[ord(c)-ord('a')]+=1
        for c in s[:window_size]:
            window_cnt[ord(c)-ord('a')]+=1
        # print(p_cnt, window_cnt)
        if p_cnt == window_cnt:
            ans.append(0)
        for i inrange(1, n - window_size +1):
            left_del_char, right_new_char = s[i -1], s[i + window_size -1]  # 记录要删除的左字符、要添加的右字符
            # print(left_del_char, right_new_char)
            window_cnt[ord(left_del_char)-ord('a')]-=1
            window_cnt[ord(right_new_char)-ord('a')]+=1
            # print(p_cnt, window_cnt)
            if p_cnt == window_cnt:
                ans.append(i)
        return ans

class Solution:
    def addToArrayForm(self, num: List[int], k:int)-> List[int]:
        n =len(num)
        i = n -1  # 从右往左遍历 num 的每一位
        carry =0
        ans =[]
        while i >=0or k !=0:  # num 和 k 长度可能不一致，只要还有没遍历完的，就要继续算
            x = num[i]if i >=0else0  # 不够长就补 0
            y = k %10if k !=0else0  # 不够长就补 0
            s = x + y + carry
            value = s %10  # 值
            carry = s //10  # 进位：注意是除完取整！
            ans.append(value)
            i -=1
            k //=10
        if carry:
            ans.append(carry)
        return ans[::-1]

class Solution:
    def getRow(self, rowIndex:int)-> List[int]:
        row_num = rowIndex +1  # rowIndex 是从 0 开始的，注意行数要 +1
        T =[[1]*(i+1)for i inrange(row_num)]  # rowIndex * 1,2,3,...
        for i inrange(row_num):
            for j inrange(1, i):  # 不算每行的首尾，默认是 1
                T[i][j]= T[i-1][j-1]+ T[i-1][j]
        return T[rowIndex]

class Solution:
    def rob(self, nums: List[int])->int:
        n =len(nums)
        if n ==1:
            return nums[0]
        if n ==2:
            returnmax(nums[0], nums[1])  # 两间房，只能偷一家最有钱的
        dp =[0]* n  # dp[i]表示前 i 间房最高金额
        dp[0]= nums[0]
        dp[1]=max(nums[0], nums[1])
        for i inrange(2, n):  # 当前 dp[i]的可能性：
            # 1）前一间偷过了 dp[i-1]，这间不能偷；2）前一间没偷，这间还可以偷 nums[i]
            dp[i]=max(dp[i -1], dp[i -2]+ nums[i])
        return dp[-1]

class Solution:
    def rob(self, nums: List[int])->int:
        # 核心：第 0 天和第 n-1 天不能同时偷
        n =len(nums)
        if n ==1:
            return nums[0]
        if n ==2:
            returnmax(nums[0], nums[1])
        dp =[0]* n
        # 情况 1：如果第 0 天可以偷，第 n-1 天不能偷
        dp[0]= nums[0]
        dp[1]=max(nums[0], nums[1])
        for i inrange(2, n -1):
            dp[i]=max(dp[i -1], dp[i -2]+ nums[i])
        ans1 = dp[-2]
        # 情况 2：第 n-1 天可以偷，第 0 天不能偷
        dp[1]= nums[1]
        dp[2]=max(nums[1], nums[2])
        for i inrange(3, n):
            dp[i]=max(dp[i -1], dp[i -2]+ nums[i])
        ans2 = dp[-1]
        returnmax(ans1, ans2)

class Solution:
    def rob(self, root: Optional[TreeNode])->int:
        def dfs(node):
            # 返回两个值：偷这个节点的最大收益、不偷这个节点的最大收益
            if not node:
                return0,0
            left_rob, left_not_rob = dfs(node.left)
            right_rob, right_not_rob = dfs(node.right)
            cur_rob = node.val + left_not_rob + right_not_rob  # 当前节点要偷，左右节点就不能偷
            cur_not_rob =0+max(left_rob, left_not_rob)+max(right_rob, right_not_rob)  # 当前节点不偷，左右节点都可以偷，分别取偷或不偷的最大值
            return cur_rob, cur_not_rob
        returnmax(dfs(root))

class Solution:
    def maxSlidingWindow(self, nums: List[int], k:int)-> List[int]:
        n =len(nums)
        ans =[]
        q = deque()  # 双端队列
        for i, x inenumerate(nums):  # 入队
            while q and x >= nums[q[-1]]:
                q.pop()
            q.append(i)  # 记录 index，方便后面判断距离进行出队
            # 出队
            if i - q[0]>= k:  # 控制不要超过窗口距离
                q.popleft()
            # 记录答案
            if i >= k -1:  # 刚开始没到窗口大小时不记录答案
                ans.append(nums[q[0]])  # 队列左端点是最大值
        return ans

class Solution:
    def merge(self, intervals: List[List[int]])-> List[List[int]]:
        intervals.sort(key=lambda p: p[0])  # 按左端点升序排列
        ans =[]
        for p in intervals:
            if ans and p[0]<= ans[-1][1]:  # 当前区间左端点<=上一个区间右端点（可融合）
                ans[-1][1]=max(p[1], ans[-1][1])  # 更新上一个区间右端点=最大右端点值
            else:  # 当前区间和上一个区间不重叠
                ans.append(p)
        return ans

class Solution:
    def findTargetSumWays(self, nums: List[int], target:int)->int:
        # 假设：nums 中元素和是 s
        # 正数之和（+）=p，负数之和（-）=s-p
        # p-(s-p)=target => p=(target+s)/2
        # 转化成了一个'0-1 背包问题'：从 nums 中选若干个数，使和为 (target+sum(nums))/2
        n =len(nums)
        target +=sum(nums)
        if target <0or target %2!=0:  # 必须正数且偶数
            return0
        target //=2
        @lru_cache(None)  # 用@cache 实现'记忆化'搜索，缓存中间结果，避免重复计算（用空间换时间）
        def dfs(i, target):
            # dfs(i, target)表示 nums 前 i 个数中，选中数之和为 target 的方案数
            if i <0:  # 没有数可选
                return1if target ==0else0  # target==0 表示刚好 1 种方案，返回 1，否则返回 0
            if nums[i]> target:  # 如果这个数比 target 大，则不选
                return dfs(i-1, target)
            return dfs(i-1, target)+ dfs(i-1, target-nums[i])  # 选或不选当前数的情况相加
        return dfs(n-1, target)

class Solution:
    def coinChange(self, coins: List[int], amount:int)->int:
        n =len(coins)
        @lru_cache(None)
        def dfs(i, t):  # 表示 coins 中前 i 个硬币能凑出 t 的最小硬币数
            if i <0:  # 没有硬币了
                return0if t ==0else inf  # 如果要凑的金额是 0，则需要 0 个硬币，否则 inf（凑不出）
            if coins[i]> t:  # 当前硬币超过要凑的数，不选
                return dfs(i-1, t)
            returnmin(dfs(i-1, t), dfs(i, t-coins[i])+1)  # 关键问题：为什么是 dfs(i, t-coins[i])而不是 dfs(i-1, t-coins[i])？
            # 因为'每种硬币可以使用无限次'，所以选了一枚 coins[i]后，仍可以继续选当前种类的硬币，所以保持 i 不变
        ans = dfs(n-1, amount)
        return ans if ans < inf else-1

class RandomizedSet:
    def __init__(self):
        self.nums =[]
    
    def insert(self, val:int)->bool:
        if val notin self.nums:
            self.nums.append(val)
            returnTrue
        returnFalse
    
    def remove(self, val:int)->bool:
        if val in self.nums:
            idx = self.nums.index(val)
            del self.nums[idx]
            returnTrue
        returnFalse
    
    def getRandom(self)->int:
        if not self.nums:
            return[]
        return choice(self.nums)

class RandomizedSet:
    def __init__(self):
        self.nums =[]
        self.hash={}  # {val: index}
    
    def insert(self, val:int)->bool:
        if val notin self.hash:
            self.nums.append(val)
            self.hash[val]=len(self.nums)-1  # {val: index}
            returnTrue
        returnFalse
    
    def remove(self, val:int)->bool:
        if val in self.hash:
            index = self.hash[val]  # 接下来是重点：如何 O(1)丢弃index位置的元素？只能用pop()操作
            self.nums[index]= self.nums[-1]  # 把末尾的元素值备份到要丢的位置上
            self.hash[self.nums[-1]]= index  # 记录末尾元素的 hash：index 改成要丢的那个位置（补位）
            del self.hash[val]  # 丢弃 hash 中 val 及对应的 index
            self.nums.pop()  # 丢弃末尾元素
            returnTrue
        returnFalse
    
    def getRandom(self)->int:
        if not self.nums:
            return[]
        return choice(self.nums)

class LRUCache:
    def __init__(self, capacity:int):
        self.capacity = capacity
        self.cache = OrderedDict()  # dict + 双向链表
    
    def get(self, key:int)->int:
        if key notin self.cache:  # 找不到这个 key
            return-1
        self.cache.move_to_end(key, last=False)  # 找到这个 key，移动到链表表头
        return self.cache[key]
    
    def put(self, key:int, value:int)->None:
        self.cache[key]= value  # 加入这个 key-value 对
        self.cache.move_to_end(key, last=False)  # 移动到链表表头
        iflen(self.cache)> self.capacity:  # 超过容量了，剔除最后一个
            self.cache.popitem()

class Node:
    # 提高访问属性的速度，并节省内存
    __slots__ ='prev','next','key','value'
    
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value

class LRUCache:
    def __init__(self, capacity:int):
        self.capacity = capacity
        self.dummy = Node()  # 哨兵节点
        self.dummy.prev = self.dummy
        self.dummy.next= self.dummy
        self.key_to_node ={}  # 获取 key 对应的节点，同时把该节点移到链表头部
    
    def get_node(self, key:int)-> Optional[Node]:
        if key notin self.key_to_node:  # 没有这本书
            returnNone
        node = self.key_to_node[key]  # 有这本书
        self.remove(node)  # 把这本书抽出来
        self.push_front(node)  # 放到最上面
        return node
    
    def get(self, key:int)->int:
        node = self.get_node(key)  # get_node 会把对应节点移到链表头部
        return node.value if node else-1
    
    def put(self, key:int, value:int)->None:
        node = self.get_node(key)  # get_node 会把对应节点移到链表头部
        if node:  # 有这本书
            node.value = value  # 更新 value
            return
        self.key_to_node[key]= node = Node(key, value)  # 新书
        self.push_front(node)  # 放到最上面
        iflen(self.key_to_node)> self.capacity:  # 书太多了
            back_node = self.dummy.prev
            del self.key_to_node[back_node.key]
            self.remove(back_node)  # 去掉最后一本书
    
    # 删除一个节点（抽出一本书）
    def remove(self, x: Node)->None:
        x.prev.next= x.next
        x.next.prev = x.prev
    
    # 在链表头添加一个节点（把一本书放到最上面）
    def push_front(self, x: Node)->None:
        x.prev = self.dummy
        x.next= self.dummy.next
        x.prev.next= x
        x.next.prev = x

class Solution:
    def numIslands(self, grid: List[List[str]])->int:
        def dfs(grid, r, c):
            row_num =len(grid)
            col_num =len(grid[0])  # 边界条件处理
            if r <0or r > row_num -1or c <0or c > col_num -1:
                return  # 指 dfs 退一层
            if grid[r][c]!="1":  # 如果当前访问的位置不是 1，则退出递归（0 说明不满足；2 说明访问过了，不能走重复路）
                return  # 指 dfs 退一层
            grid[r][c]="2"  # 定义 2 表示已访问（修改当前位置的状态）
            # 搜索前后左右的位置
            dfs(grid, r+1, c)
            dfs(grid, r-1, c)
            dfs(grid, r, c+1)
            dfs(grid, r, c-1)
        
        row_num =len(grid)
        col_num =len(grid[0])
        ans =0
        for r inrange(row_num):
            for c inrange(col_num):
                if grid[r][c]=='1':  # 遍历到了岛屿
                    dfs(grid, r, c)  # 递归：深度优先搜索
                    ans +=1  # 答案 +1
        return ans

class Solution:
    def maximalSquare(self, matrix: List[List[str]])->int:
        rows, cols =len(matrix),len(matrix[0])
        if rows ==0or cols ==0:  # 如果正方形不存在，返回 0
            return0
        dp =[[0]* cols for _ inrange(rows)]  # dp[i][j]表示以 (i, j) 为右下角的正方形的边长
        max_side =0
        for i inrange(rows):
            for j inrange(cols):
                if matrix[i][j]=='1':  # 只有当遍历到'1'这个位置，才能去探索
                    if i ==0and j ==0:  # 右下角在边界上，边长只能是 1
                        dp[i][j]=1
                    else:  # 当前右下角最大边长取决于左、上、左上角最大边长的最小值
                        dp[i][j]=min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1
                    max_side =max(max_side, dp[i][j])  # 更新最大边长
        return max_side **2

class Solution:
    def setZeroes(self, matrix: List[List[int]])->None:
        """ Do not return anything, modify matrix in-place instead. """
        rows =len(matrix)
        cols =len(matrix[0])
        row_flag, col_flag =[0]* rows,[0]* cols  # 设置行列 flag：初始化 0，matrix 某行某列出现 0 时则改成 1
        for r inrange(rows):
            for c inrange(cols):
                if matrix[r][c]==0:  # 如果 matrix 某个元素是 0，则把行列 flag 改成 1
                    row_flag[r]=1
                    col_flag[c]=1
        for r inrange(rows):
            for c inrange(cols):
                if row_flag[r]or col_flag[c]:  # 如果行或列 flag 是 1，就需要把 matrix 的整行整列改成 0
                    matrix[r][c]=0

class Solution:
    def rotate(self, matrix: List[List[int]])->None:
        """ Do not return anything, modify matrix in-place instead. """
        # 顺时针旋转 90 度 = 水平翻转 + 主对角线翻转
        n =len(matrix)
        # 水平翻转
        for i inrange(n //2):
            for j inrange(n):
                matrix[i][j], matrix[n - i -1][j]= matrix[n - i -1][j], matrix[i][j]
        # 主对角线翻转
        for i inrange(n):
            for j inrange(i):
                matrix[i][j], matrix[j][i]= matrix[j][i], matrix[i][j]

class Solution:
    def rotate(self, matrix: List[List[int]])->None:
        """ Do not return anything, modify matrix in-place instead. """
        # 顺时针旋转 90 度：原来的 i 行 j 列 => 旋转后的倒数 i 列 j 行
        n =len(matrix)
        matrix_rot =[[0]* n for _ inrange(n)]
        for i inrange(n):
            for j inrange(n):
                matrix_rot[j][n - i -1]= matrix[i][j]
        matrix[:]= matrix_rot

class Solution:
    def rotate(self, matrix: List[List[int]])->None:
        n =len(matrix)
        for i inrange(n //2):
            for j inrange((n +1)//2):
                matrix[i][j], matrix[n - j -1][i], matrix[n - i -1][n - j -1], matrix[j][n - i -1] \
                = matrix[n - j -1][i], matrix[n - i -1][n - j -1], matrix[j][n - i -1], matrix[i][j]

class Solution:
    def transpose(self, matrix: List[List[int]])-> List[List[int]]:
        rows =len(matrix)
        cols =len(matrix[0])
        ans =[[0]* rows for _ inrange(cols)]  # cols * rows
        for i inrange(rows):
            for j inrange(cols):
                ans[j][i]= matrix[i][j]
        return ans

class Solution:
    def mySqrt(self, x:int)->int:
        left, right =0, x
        ans =-1
        while left <= right:
            mid =(left + right)//2
            if mid **2<= x:
                ans = mid
                left = mid +1
            else:
                right = mid -1
        return ans

class Solution:
    def mySqrt(self, x:int)->int:
        if x ==0:
            return0
        x0 = x
        whileTrue:
            x1 =0.5*(x0 + x / x0)
            ifabs(x0 - x1)<1e-6:
                break
            x0 = x1
        returnint(x0)

import random
defrandom_coin(p):  # 生成概率为 p 的 0/1
    return1if random.random()< p else0

def Rand1(self):  # 周期性地产生 2 个数，直到生成 01 或者 10 才满足
    i1 = random_coin()  # 生成 0/1
    i2 = random_coin()  # 生成 0/1
    if i1 ==0and i2 ==1:
        return0
    elif i1 ==1and i2 ==0:
        return1
    else:
        return Rand1()  # 重新生成

defRandN(self, n:int):  # 以 1/n 的概率返回 1~n 之间的数
    # int(res, 2)指二进制转十进制
    k = math.log2(n)+1
    res =''
    for _ inrange(k):
        res +=str(Rand1())
    ifint(res,2)> n:
        return RandN(n)  # 重新生成
    else:
        returnint(res,2)

class Solution:
    def integerBreak(self, n:int)->int:
        if n ==1:
            return1
        dp =[0]*(n +1)  # dp[i]表示整数 i 时的乘积最大值
        dp[1]=1
        for i inrange(2, n +1):
            for j inrange(0, i):  # 对于整数 i，可以拆分成 j 和 i-j
                dp[i]=max(dp[i], j *(i - j), j * dp[i - j])  # j*(i-j)表示两段都不能拆，j*dp[i-j]表示有一段还能拆（和 dp[j]*(i-j)是对称的）
        return dp[n]

class Solution:
    def isUgly(self, n:int)->bool:
        if n <=0:
            returnFalse
        while n %2==0:
            n //=2
        while n %3==0:
            n //=3
        while n %5==0:
            n //=5
        returnTrueif n ==1elseFalse

class Solution:
    def nthUglyNumber(self, n:int)->int:
        a =[0]*(n +1)  # 下标从 1 开始更方便
        a[1]=1
        p2, p3, p5 =1,1,1  # 三指针
        for i inrange(2, n +1):
            num2, num3, num5 = a[p2]*2, a[p3]*3, a[p5]*5
            a[i]=min(num2, num3, num5)
            print(a[i], num2, num3, num5)
            if a[i]== num2:
                p2 +=1
            if a[i]== num3:
                p3 +=1
            if a[i]== num5:
                p5 +=1
        # 不能用 elif 的原因：6=3*2 同时 6=2*3，所以 p2、p3 都要加 1 才行
        return a[n]

class Solution:
    def addDigits(self, num:int)->int:
        if num ==0:
            return0
        while num >=10:  # 只要不是个位数，就要继续
            sum_val =0
            while num >0:
                sum_val += num %10
                num //=10
            num =sum_val
        return num

class Solution:
    def addDigits(self, num:int)->int:
        if num ==0:
            return0
        if num %9==0:
            return9
        return num %9

class Solution:
    def addDigits(self, num:int)->int:
        if num ==0:
            return0
        return(num -1)%9+1

class Solution:
    def isHappy(self, n:int)->bool:
        if n ==1:
            returnTrue
        def compute_next(n):
            sum_val =0
            while n >0:
                sum_val +=(n %10)**2
                n //=10
            return sum_val
        # 核心思想：如果结果回不到 1，则一定会出现重复的数（当然也可以用快慢指针做，参考 141.环形链表）
        hash_table =set()
        while n !=1:
            if n in hash_table:
                break
            hash_table.add(n)
            n = compute_next(n)
        if n ==1:
            returnTrue
        returnFalse

class Solution:
    def isHappy(self, n:int)->bool:
        if n ==1:
            returnTrue
        def compute_next(n):
            sum_val =0
            while n >0:
                sum_val +=(n %10)**2
                n //=10
            return sum_val
        # 核心思想：快慢指针判断环，参考 141.环形链表
        slow, fast = n, compute_next(n)
        whileTrue:
            if slow == fast:  # 快慢指针相遇，说明出现重复数，一定到不了 1
                returnFalse
            if fast ==1:  # 如果能到 1，则一定是 fast 指针先到
                returnTrue
            slow = compute_next(slow)  # slow 指针走一步
            fast = compute_next(compute_next(fast))  # fast 指针走两步

class Solution:
    def canFinish(self, numCourses:int, prerequisites: List[List[int]])->bool:
        # 思路：判断节点构成的图是否存在环，存在说明无法存在冲突，则无法完成课程
        # 构图：存储节点与其后继节点
        graph =[[]for _ inrange(numCourses)]
        for a, b in prerequisites:
            graph[b].append(a)
        states =[0]* numCourses  # 定义节点状态
        """ 0：节点 x 未被访问
            1：节点 x 正在访问中，dfs(x)尚未结束
            2：节点 x 已经完全访问完，说明从 x 出发无法找到环 """
        # DFS：返回 True 表示找到了环
        def dfs(x):
            states[x]=1
            for node in graph[x]:
                if states[node]==1or(states[node]==0and dfs(node)==True):
                    returnTrue
            states[x]=2
            returnFalse
        for i, s inenumerate(states):
            if s ==0and dfs(i)==True:  # 存在环
                returnFalse
        returnTrue

class Solution:
    def minPathSum(self, grid: List[List[int]])->int:
        rows, cols =len(grid),len(grid[0])
        dp =[[0]* cols for _ inrange(rows)]  # dp[i][j]表示在第 i 行 j 列的最小路径和
        dp[0][0]= grid[0][0]  # 处理第 1 列
        for i inrange(1, rows):
            dp[i][0]= dp[i -1][0]+ grid[i][0]
        # 处理第 1 行
        for j inrange(1, cols):
            dp[0][j]= dp[0][j -1]+ grid[0][j]
        # 处理中间元素
        for i inrange(1, rows):
            for j inrange(1, cols):  # 当前状态由左边状态/上边状态的最小值决定
                dp[i][j]=min(dp[i][j -1], dp[i -1][j])+ grid[i][j]
        return dp[rows -1][cols -1]

LeetCode 热题 HOT 100 经典算法题 Python 解法汇总

树

104. 二叉树的最大深度【简单】

94. 二叉树的中序遍历【简单】

98. 验证二叉搜索树【中等】

543. 二叉树的直径【简单】

617. 合并二叉树【简单】

102. 二叉树的层序遍历【中等】

226. 翻转二叉树【简单】

236. 二叉树的最近公共祖先【中等】

112. 路径总和【简单】

208. 实现 Trie (前缀树)【中等】

100. 相同的树【简单】

101. 对称二叉树【简单】

199. 二叉树的右视图【中等】

103. 二叉树的锯齿形层序遍历【中等】

124. 二叉树中的最大路径和【困难】

108. 将有序数组转换为二叉搜索树【简单】

字符串

20. 有效的括号【简单】

32. 最长有效括号【困难】

647. 回文子串【中等】

139. 单词拆分【中等】

394. 字符串解码【中等】

72. 编辑距离【中等】

168. Excel 表列名称【简单】

415. 字符串相加【简单】

搜索查找

448. 找到所有数组中消失的数字【简单】

136. 只出现一次的数字【简单】

704. 二分查找【简单】

121. 买卖股票的最佳时机【简单】

122. 买卖股票的最佳时机 II【中等】

169. 多数元素【简单】

739. 每日温度【中等】

1. 两数之和【简单】

167. 两数之和 II - 输入有序数组【中等】

15. 三数之和【中等】

155. 最小栈【中等】

347. 前 K 个高频元素【中等】

287. 寻找重复数【中等】

42. 接雨水【困难】

11. 盛最多水的容器【中等】

LCR 172. 统计目标成绩的出现次数【简单】

34. 在排序数组中查找元素的第一个和最后一个位置【中等】

1287. 有序数组中出现次数超过 25% 的元素【简单】

215. 数组中的第 K 个最大元素【中等】

209. 长度最小的子数组【中等】

76. 最小覆盖子串【困难】

3. 无重复字符的最长子串【中等】

排列

冒泡排序【排序模板】

快速排序【排序模板】

283. 移动零【简单】

75. 颜色分类【中等】

406. 根据身高重建队列【中等】

977. 有序数组的平方【简单】

31. 下一个排列【中等】

组合

49. 字母异位词分组【中等】

78. 子集【中等】

46. 全排列【中等】

47. 全排列 II【中等】

LCR 157. 套餐内商品的排列顺序【中等】

链表

206. 反转链表【简单】

92. 反转链表 II【中等】

234. 回文链表【简单】

160. 相交链表【简单】

141. 环形链表【简单】

142. 环形链表 II【中等】

148. 排序链表【中等】

237. 删除链表中的节点【中等】

19. 删除链表的倒数第 N 个节点【中等】

83. 删除排序链表中的重复元素【简单】

82. 删除排序链表中的重复元素 II【中等】

203. 移除链表元素【简单】

2. 两数相加【中等】

21. 合并两个有序链表【简单】

23. 合并 K 个升序链表【困难】