1
2

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []  # 用于存储最终的结果
        if root is None:  # 如果根节点为空，直接返回空列表
            return []
        else:
            queue = deque([root])  # 初始化队列，将根节点加入队列

        while len(queue) > 0:  # 当队列不为空时，继续遍历
            level = []  # 用于存储当前层的节点值
            level_len = len(queue)  # 记录当前层的节点数量
            for _ in range(level_len):  # 遍历当前层的所有节点
                node = queue.popleft()  # 从队列中取出一个节点
                if node.left:  # 如果该节点有左子节点，将左子节点加入队列
                    queue.append(node.left)
                if node.right:  # 如果该节点有右子节点，将右子节点加入队列
                    queue.append(node.right)
                level.append(node.val)  # 将当前节点的值加入当前层的列表
            result.append(level)  # 将当前层的列表加入结果列表
      
        return result

1
2
3

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

1
2
3
4
5
6
7
8

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}  # 初始化哈希表，用于存储元素及其下标
        for i in range(len(nums)):  # 遍历数组
            if target - nums[i] in dict:  # 检查差值是否存在于哈希表中
                return [dict[target - nums[i]], i]  # 如果存在，返回两个下标
            dict[nums[i]] = i  # 如果不存在，将当前元素及其下标存入哈希表
        return [-1, -1]  # 如果没有找到满足条件的数对，返回 [-1, -1]

1
2
3
4
5
6
7

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i, j):
            # 如果当前格子超出边界或者不是陆地，则返回
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
                return
            # 将当前陆地标记为已访问
            grid[i][j] = '0'
            # 递归遍历上下左右四个方向的格子
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)

        # 初始化岛屿数量
        count = 0
        # 遍历整个网格
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # 如果发现陆地，则开始 DFS，并将岛屿数量加 1
                if grid[i][j] == '1':
                    dfs(i, j)
                    count += 1
        return count

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def bfs(i, j):
            # 初始化队列
            queue = deque([(i, j)])
            # 标记当前陆地为已访问
            grid[i][j] = '0'
            # 遍历队列中的每一个格子
            while queue:
                x, y = queue.popleft()
                # 检查上下左右四个方向的格子
                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    nx, ny = x + dx, y + dy
                    # 如果新格子是陆地，则加入队列并标记为已访问
                    if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == '1':
                        grid[nx][ny] = '0'
                        queue.append((nx, ny))

        # 初始化岛屿数量
        count = 0
        # 遍历整个网格
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # 如果发现陆地，则开始 BFS，并将岛屿数量加 1
                if grid[i][j] == '1':
                    bfs(i, j)
                    count += 1
        return count

1
2

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 处理空数组的情况
        if not nums:
            return -1
      
        # 找到旋转点（最大值的位置）
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right + 1) // 2  # 向上取整，避免死循环
            if nums[mid] >= nums[0]:  # 旋转点在右侧
                left = mid
            else:
                right = mid - 1
      
        # 根据旋转点确定搜索范围
        if target >= nums[0] :  # 目标值在左侧有序部分
            left, right = 0, left
        elif l + 1 == len(nums): # 必须排除
	        return -1
        else:  # 目标值在右侧有序部分
            left, right = left + 1, len(nums) - 1
      
        # 在搜索范围内进行二分查找
        while left < right:
            mid = (left + right + 1) // 2
            if nums[mid] <= target:  # 目标值在右侧
                left = mid
            else:
                right = mid - 1
      
        # 检查是否找到目标值
        if nums[left] == target:
            return left
        else:
            return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []

        def dfs(path, visit):
            # 如果当前路径是一个排列，添加到结果集
            if len(path) == len(nums):
                result.append(path[:])  # 添加 path 的副本
                return

            # 遍历所有可能的选项
            for i in range(len(nums)):
                if visit[i]:  # 如果该元素已经被选择过，跳过
                    continue
                visit[i] = True  # 标记该元素已被选择
                path.append(nums[i])  # 选择该元素
                dfs(path, visit)  # 递归搜索
                path.pop()  # 撤销选择
                visit[i] = False  # 标记该元素未被选择

        dfs([], [False] * len(nums))  # 从空路径开始搜索
        return result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

from typing import List

def solveProblem(nums: List[int]) -> List[List[int]]:
    # 1. 预处理（排序/初始化）
    nums.sort()  # 如果需要去重，先排序
    res = []

    # 2. 定义回溯函数（使用闭包捕获外部变量）
    def backtrack(
        path: List[int],         # 当前路径：已做出的选择序列
        selection: List[int],    # 选择列表：当前可选的元素集合
        used: List[bool],        # 辅助参数：标记已使用的元素（根据问题调整）
        start: int               # 辅助参数：组合问题中的起始位置（根据问题调整）
    ):
        # 终止条件（根据具体问题修改）
        if len(path) == len(nums):  # 示例：路径长度等于输入数组长度
            res.append(path[:])     # 添加当前路径的副本到结果集
            return
        
        # 横向遍历选择列表（根据问题调整遍历方式）
        for i in range(start, len(selection)):  # 组合问题从start开始，排列问题从0开始
            # 剪枝判断（根据问题需要添加条件）
            if used[i]:
                continue  # 示例：跳过已使用的元素
            if i > start and selection[i] == selection[i-1] and not used[i-1]:
                continue  # 示例：横向去重
            
            # 做选择（更新路径和状态）
            path.append(selection[i])  # 将当前选择加入路径
            used[i] = True             # 标记当前选择为已使用
            
            # 进入下一层决策树（更新选择列表和参数）
            backtrack(
                path,         # 更新后的路径
                selection,    # 新的选择列表（可能保持不变）
                used,         # 更新后的使用状态
                i+1 if start is not None else 0  # 新的起始位置（组合问题用）
            )
            
            # 撤销选择（回溯操作）
            path.pop()       # 移除当前选择
            used[i] = False  # 标记当前选择为未使用

    # 3. 初始调用（根据问题设置初始参数）
    backtrack(
        [],           # 初始路径：空路径
        nums,         # 初始选择列表：完整数组
        [False] * len(nums),  # 初始辅助参数：未使用的标记数组
        0 if start is not None else None  # 初始起始位置：组合问题从0开始，排列问题为None
    )

    return res

1
2

if i > 0 and nums[i] == nums[i - 1] and not visit[i - 1]:
    continue

1
2
3
4
5

def dfs(start, path):
    for i in range(start, len(nums)):
        path.append(nums[i])
        dfs(i + 1, path)
        path.pop()

1
2
3
4
5
6

def dfs(start, path):
    result.append(path[:])
    for i in range(start, len(nums)):
        path.append(nums[i])
        dfs(i + 1, path)
        path.pop()

1
2
3
4
5
6
7
8

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = prices[0]  # 初始化最低价格
        max_profit = 0         # 初始化最大利润
        for i in range(1, len(prices)):  # 遍历价格数组
            min_price = min(min_price, prices[i])  # 更新最低价格
            max_profit = max(max_profit, prices[i] - min_price)  # 更新最大利润
        return max_profit

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        k = m + n - 1  # 指向 nums1 的最后一个位置
        while n > 0 and m > 0:  # 从后向前遍历
            if nums1[m - 1] > nums2[n - 1]:  # 比较 nums1 和 nums2 的末尾元素
                nums1[k] = nums1[m - 1]  # 将较大的元素放入 nums1 的末尾
                k, m = k - 1, m - 1  # 移动指针
            else:
                nums1[k] = nums2[n - 1]  # 将较大的元素放入 nums1 的末尾
                k, n = k - 1, n - 1  # 移动指针
        if n > 0:  # 如果 nums2 还有剩余元素
            nums1[:n] = nums2[:n]  # 将剩余元素直接复制到 nums1 的前面

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import heapq
def mergeKLists(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))  # (value, list_idx, element_idx)
    res = []
    while heap:
        val, lst_idx, ele_idx = heapq.heappop(heap)
        res.append(val)
        if ele_idx + 1 < len(lists[lst_idx]):
            heapq.heappush(heap, (lists[lst_idx][ele_idx + 1], lst_idx, ele_idx + 1))
    return res

1
2

nums1[m:] = nums2
nums1.sort()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 if l1 else l2
    return dummy.next

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def isValid(self, s: str) -> bool:
        r2l = {  # 右括号到左括号的映射
            ')': '(',
            ']': '[',
            '}': '{',
        }
        stk = []  # 栈
        for i in range(len(s)):  # 遍历字符串
            if s[i] in r2l:  # 如果当前字符是右括号
                # 检查栈顶是否是对应的左括号
                if len(stk) > 0 and stk[-1] == r2l[s[i]]:
                    stk.pop()  # 匹配成功，弹出栈顶元素
                else:
                    return False  # 匹配失败，直接返回 False
            else:  # 如果当前字符是左括号
                stk.append(s[i])  # 将其压入栈中
        return len(stk) == 0  # 最后检查栈是否为空

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        # 递归终止条件：
        # 1. 如果当前节点为空，说明当前分支没有找到 p 或 q，返回 None。
        # 2. 如果当前节点是 p 或 q，说明找到了目标节点，返回当前节点。
        if not root or root == p or root == q:
            return root
        
        # 递归左子树，在左子树中查找 p 和 q。
        # left 表示在左子树中找到的 p 或 q 的最近公共祖先。
        left = self.lowestCommonAncestor(root.left, p, q)
        
        # 递归右子树，在右子树中查找 p 和 q。
        # right 表示在右子树中找到的 p 或 q 的最近公共祖先。
        right = self.lowestCommonAncestor(root.right, p, q)
        
        # 判断逻辑：
        # 1. 如果 left 和 right 都不为空，说明 p 和 q 分别位于当前节点的左右子树中，
        #    因此当前节点是 p 和 q 的最近公共祖先，返回 root。
        if left and right:
            return root
        
        # 2. 如果只有 left 不为空，说明 p 和 q 都在左子树中，返回 left。
        if left:
            return left
        
        # 3. 如果只有 right 不为空，说明 p 和 q 都在右子树中，返回 right。
        if right:
            return right
        
        # 4. 如果 left 和 right 都为空，说明当前子树中没有找到 p 或 q，返回 None。
        return None

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False 
        slow, fast = head, head 
        while fast and fast.next:
            slow = slow.next 
            fast = fast.next.next 
            if fast == slow:
                return True
        return False