笺札

2044. 统计按位或能得到最大值的子集数目 🎯 问题描述（来源于LeetCode） 描述： 给你一个整数数组 nums，找出所有可能的子集（包括空集）的按位或（OR）运算结果。 返回能够获得最大按位或值的子集个数。 注意：子集可以是空集，空集按位或为 0。 说明： 子集定义为原数组中任意元素组成的集合（顺序无关）。 不同子集如果元素相同但顺序不同视为同一个子集。 示例： 示例 1： 123输入: nums = [3,1]输出: 2解释: 子集按位或值：[]=0, [3]=3, [1]=1, [3,1]=3，最大值为3，出现2次。 示例 2： 123输入: nums = [2,2,2]输出: 7解释: 所有子集（共8个）的按位或均为2，最大值为2，出现7次（空集为0，不计入）。 💻 解题思路 思路：回溯法（DFS）枚举所有子集 算法步骤 获取数组长度 n，初始化 max_num = -1（确保任何非负的 OR 值都会大于它），cnt = 0。 定义递归函数 dfs(i, path)，其中 i 表示当前处理的下标，path 为当前子集的按位或值： 如果...

130. 被围绕的区域 - Surrounded Regions 🎯 问题描述（来源于LeetCode） 描述： 给你一个 m x n 的矩阵 board，由字符 'X' 和 'O' 组成。 如果所有与边界连通的 'O' 区域称为「不被围绕的区域」，而完全被 'X' 包围的 'O' 区域（即无法通过上下左右走到边界）需要被翻转成 'X'。 请原地修改矩阵，将所有被 'X' 包围的 'O' 翻转为 'X'。 说明： 边界上的 'O' 不会被翻转。 与边界上的 'O' 连通的 'O' 也不会被翻转。 示例： 示例 1： 123输入: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X&qu...

1034. 边界着色 - Coloring A Border 🎯 问题描述（来源于LeetCode） 描述： 给定一个二维整数网格 grid，以及一个起始坐标 (row, col) 和一个新颜色 color。 将与起点四方向连通且颜色相同的所有格子组成的连通分量称为“连通分量”。 请将该连通分量的边界格子（即该格子至少有一个相邻格子（上下左右）不在同一连通分量内，或者位于网格边界）的颜色改为 color，并返回修改后的网格。 说明： 连通分量中的内部格子（所有邻居都在同一连通分量内）保持原色不变。 边界格子包括：网格边缘的格子，以及邻居中存在不同颜色或越界的格子。 起始点 (row, col) 一定在网格内。 示例： 示例 1： 123输入: grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2输出: [[2,2,2],[2,1,2],[2,2,2]]解释: 整个网格都是相同颜色，边界上的格子被着色为2，内部中心格子保持1。 示例 2： 12输入: grid = [[1,2,2],[2,3,2...

1020. 飞地的数量 - Number of Enclaves 🎯 问题描述（来源于LeetCode） 描述： 给定一个 m x n 的二维网格 grid，其中 1 表示陆地，0 表示水域。 如果一个陆地格子无法通过上下左右移动到网格边界（即被水域包围），则称为“飞地”。 返回飞地的数量（即所有满足条件的陆地格子数）。 说明： 移动只能在四方向上。 边界上的陆地不算飞地（因为它们可以走到边界）。 示例： 示例 1： 123输入: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]输出: 3解释: 有三个1被水包围，无法到达边界。 示例 2： 123输入: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]输出: 0解释: 所有1都能到达边界。 💻 解题思路 思路：从边界 DFS 标记所有可达陆地，再统计剩余陆地 算法步骤 获取网格尺寸 m, n。 定义 DFS 函数 dfs(i, j)： 如果坐标越界或当前格子不是陆地（grid[i][j] != 1），则返...

733. 图像渲染 - Flood Fill 🎯 问题描述（来源于LeetCode） 描述： 给定一个二维整数数组 image（表示图像，每个整数代表一个像素值），以及一个起点坐标 (sr, sc) 和一个新的颜色值 color。 从起点开始，将所有与起点四方向连通且颜色相同的像素（即同一连通区域）都改为 color，并返回修改后的图像。 说明： 连通区域定义为上下左右相连且原始颜色相同的像素集合。 如果起点的原始颜色已经等于 color，则无需修改。 示例： 示例 1： 12输入: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2输出: [[2,2,2],[2,2,0],[2,0,1]] 示例 2： 12输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0输出: [[0,0,0],[0,0,0]] 💻 解题思路 思路：深度优先搜索（DFS） 算法步骤 获取图像尺寸 m, n 和起点原始颜色 ori = image[sr]...

463. 岛屿的周长 - Island Perimeter 🎯 问题描述（来源于LeetCode） 描述： 给定一个 m x n 的二维网格 grid，其中 1 表示陆地，0 表示水域。 网格中的格子是水平或垂直相连的（四方向）。假设整个网格被水完全包围，且只有一个岛屿（即所有陆地格子是连通的，且没有“洞”）。 请计算该岛屿的周长。 说明： 一个格子的周长贡献取决于它四条边中，相邻格子为水域或边界的情况。 岛屿不会包含内陆湖（但此题假设没有洞）。 示例： 示例 1： 12输入: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]输出: 16 示例 2： 12输入: grid = [[1]]输出: 4 💻 解题思路 思路1：遍历每个陆地格子，统计边界边数 算法步骤 初始化：获取网格尺寸 m, n；定义四方向偏移量；答案 ans = 0。 遍历所有格子：若 grid[i][j] == 1，调用辅助函数计算该格子贡献的周长。 辅助函数 dfs(x, y)：对四个方向检查邻居是否越界或为水域，若是则计数加一；返回计...

面试题 16.19. 池塘大小 - Pond Sizes 🎯 问题描述（来源于LeetCode） 描述： 给定一个 m x n 的整数矩阵 land，其中： 0 表示池塘（水域）。 正整数表示陆地。 池塘是八方向（上、下、左、右、以及对角线方向）连通的 0 区域。 请返回所有池塘的大小（即每个池塘中包含的 0 的数量），并将结果按从小到大排序。 说明： 八方向连通包括水平、垂直和对角线相邻。 池塘的边界由陆地（正整数）或网格边界限定。 示例： 示例 1： 123456789输入:land = [ [0,2,1,0], [0,1,0,1], [1,1,0,1], [0,1,0,1]]输出: [1,2,4]解释: 左上角池塘大小为1（一个0），右上角池塘大小为2，中间池塘大小为4。 💻 解题思路 思路1：DFS 遍历八方向连通分量 算法步骤 初始化： 获取网格尺寸 m, n。 创建 visited 二维数组，标记已访问的格子。 定义八方向偏移量： [(-1,-1),(0,-1),(1,-1),(-1,0),(1,0),(-1,1),(0,1),...

1372. 二叉树中的最长交错路径 - Longest ZigZag Path in a Binary Tree 🎯 问题描述（来源于LeetCode） 描述： 给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下： 从任意节点开始，每一步可以向左或向右，但不能连续两次向同一方向移动（即必须左右交替）。 路径长度定义为路径上的边数（非节点数）。 返回该树中最长交错路径的长度。 说明： 路径可以从任意节点开始，不一定从根节点开始。 如果树为空，返回 0。 示例： 示例 1： 123输入: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]输出: 3解释: 最长交错路径为 3 条边（如右-左-右）。 示例 2： 12输入: root = [1,1,1,null,1,null,null,1,1,null,1]输出: 4 💻 解题思路 思路1：DFS 传递方向步数 算法步骤 全局变量 ans 记录最长交错路径的长度（边数）。 定义递归函数 dfs(node, l, r)： ...

814. 二叉树剪枝 - Binary Tree Pruning 🎯 问题描述（来源于LeetCode） 描述： 给定一棵二叉树的根节点 root，树的每个节点值都是 0 或 1。 要求剪去所有不包含 1 的子树（即子树中所有节点值均为 0），并返回结果树的根节点。 说明： 剪枝后，原树中所有不含 1 的子树都应被删除。 被删除的子树应包括该子树的所有节点。 如果整棵树不含 1，则返回空。 示例： 示例 1： 123输入: root = [1,null,0,0,1]输出: [1,null,0,null,1]解释: 最底层的左叶子 0 被删除（其子树和为 0），右子树中的 1 保留。 示例 2： 12输入: root = [1,0,1,0,0,0,1]输出: [1,null,1,null,1] 示例 3： 12输入: root = [1,1,0,1,1,0,1,0]输出: [1,1,0,1,1,null,1] 💻 解题思路 思路1：后序遍历 + 假根节点 算法步骤 定义递归函数 dfs(node)： 返回以 node 为根的子树中所有节点值之和。...

1110. 删点成林 - Delete Nodes And Return Forest 🎯 问题描述（来源于LeetCode） 描述： 给定二叉树的根节点 root，以及一个要删除的节点值列表 to_delete。 删除所有值为 to_delete 中的节点后，剩下的节点会形成若干棵不相交的子树（森林）。 返回森林中所有子树的根节点列表（顺序任意）。 说明： 删除一个节点会将其左右子树断开，分别成为新的树。 被删除的节点本身不保留。 森林中每棵树的根节点是原树中未被删除且父节点被删除（或原根节点）的节点。 示例： 示例 1： 123输入: root = [1,2,3,4,5,6,7], to_delete = [3,5]输出: [[1,2,null,4],[6],[7]]解释: 删除节点3和5后，剩下三个子树：以1为根（1-2-4），以6为根，以7为根。 示例 2： 12输入: root = [1,2,4,null,3], to_delete = [3]输出: [[1,2,4]] 💻 解题思路 思路1：DFS + 传递父节点删除状态 算法步骤 将待删...