1. 被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例 1：
输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
示例 2：
输入：board = [["X"]]
输出：[["X"]]
提示：
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 'X' 或 'O'
出处：
https://edu.csdn.net/practice/26945724
代码：
from typing import List class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ if not board or len(board) == 0: return m = len(board) n = len(board[0]) from collections import deque queue = deque() for i in range(m): if board[i][0] == "O": queue.append((i, 0)) if board[i][n - 1] == "O": queue.append((i, n - 1)) for j in range(n): if board[0][j] == "O": queue.append((0, j)) if board[m - 1][j] == "O": queue.append((m - 1, j)) while queue: x, y = queue.popleft() board[x][y] = "M" for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]: if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == "O": queue.append((nx, ny)) for i in range(m): for j in range(n): if board[i][j] == "O": board[i][j] = "X" if board[i][j] == "M": board[i][j] = "O" #%% s = Solution() board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] s.solve(board) print(board)
输出：
[['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'X']]
2. 两数之和 II
给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
提示：
2 <= numbers.length <= 3 * 10^4
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案
出处：
https://edu.csdn.net/practice/26945725
代码：
class Solution(object): def twoSum(self, numbers, target): """ :type numbers: List[int] :type target: int :rtype: List[int] """ d = {} size = 0 while size < len(numbers): if not numbers[size] in d: d[numbers[size]] = size + 1 if target - numbers[size] in d: if d[target - numbers[size]] < size + 1: answer = [d[target - numbers[size]], size + 1] return answer size = size + 1 #%% s = Solution() print(s.twoSum(numbers = [2,7,11,15], target = 9)) print(s.twoSum(numbers = [2,3,4], target = 6)) print(s.twoSum(numbers = [-1,0], target = -1))
输出：
[1, 2]
[1, 3]
[1, 2]
3. 二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[0]
提示：
树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
出处：
https://edu.csdn.net/practice/26945726
代码：
class TreeNode(object): def __init__(self, val): self.val = val self.left = None self.right = None class Solution: def flatten(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ while root != None: if root.left == None: root = root.right else: pre = root.left while pre.right != None: pre = pre.right pre.right = root.right root.right = root.left root.left = None root = root.right def listToTree(lst): if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if i<len(lst) and lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i<len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root def preorderTraversal(root: TreeNode): res = [] if not root: return res res.append(root.val) res.extend(preorderTraversal(root.left)) res.extend(preorderTraversal(root.right)) return res s = Solution() null = None nums = [1,2,5,3,4,null,6] root = listToTree(nums) s.flatten(root) print(preorderTraversal(root))
输出：
[1, 2, 3, 4, 5, 6]
