Leetcode代码以及解答（2）

### Leetcode代码以及解答（2） #### 127. Word Ladder **知识点：** - **问题描述：** - 找到由开始到结尾的字符串的转换字符串集合，中间的转换字符串都要在给定的列表中，并且每一步只能改变一个字符。 - **解决方案分析：** - **原始方法：** - 遍历整个给定字符串集合来寻找可能的转换。 - 当数据量较大时，这种方法会导致超时。 - **优化方案：** - 使用哈希集存储给定的字符串集合。 - 对于给定的字符串，通过替换每个字符来生成所有可能的变化，检查这些变化是否存在于哈希集中。 - 这样可以显著提高搜索速度，避免了不必要的遍历操作。 #### 200. Number of Islands **知识点：** - **问题描述：** - 计算在一个二维矩阵中，有多少个由 '1' (表示陆地) 组成的连通区域。 - **解决方案分析：** - **四向深度优先搜索（DFS）：** - 从任意一个 '1' 开始进行 DFS 搜索。 - 搜索过程中标记访问过的 '1'，防止重复计算。 - 每次发现新的未被访问的 '1'，就增加岛屿计数器，并进行 DFS。 #### 303. Range Sum Query - Immutable **知识点：** - **问题描述：** - 给定一个只读的整数数组，需要高效地查询任意两个索引之间的元素之和。 - **解决方案分析：** - **前缀和：** - 构建一个前缀和数组 `prefixSum`，其中 `prefixSum[i] = nums[0] + nums[1] + ... + nums[i]`。 - 查询 `i` 到 `j` 之间的元素之和可以通过 `prefixSum[j] - prefixSum[i-1]` 得到。 #### 304. Range Sum Query 2D - Immutable **知识点：** - **问题描述：** - 给定一个只读的二维整数数组，需要高效地查询任意两个坐标之间元素之和。 - **解决方案分析：** - **二维前缀和：** - 构建一个二维前缀和数组 `prefixSum`，其中 `prefixSum[i][j] = sum(nums[m][n]) for m <= i and n <= j`。 - 查询 `(i1, j1)` 到 `(i2, j2)` 之间的元素之和可以通过 `prefixSum[i2][j2] - prefixSum[i1-1][j2] - prefixSum[i2][j1-1] + prefixSum[i1-1][j1-1]` 得到。 #### 307. Range Sum Query - Mutable **知识点：** - **问题描述：** - 给定一个可修改的整数数组，需要支持高效查询任意两个索引之间的元素之和，并且支持单个元素的更新。 - **解决方案分析：** - **线段树：** - 构建一棵线段树，每个节点表示一段区间 `[l, r)` 的和。 - 更新操作：找到覆盖这个元素的节点并更新。 - 查询操作：合并所有覆盖查询区间的节点的和。 #### 62. Unique Paths **知识点：** - **问题描述：** - 给定一个 `m x n` 的网格，只允许向右或向下移动，求从左上角到达右下角的不同路径数量。 - **解决方案分析：** - **动态规划：** - 定义 `dp[i][j]` 表示到达 `(i, j)` 的路径数量。 - 状态转移方程：`dp[i][j] = dp[i-1][j] + dp[i][j-1]`。 - 边界条件：`dp[0][j] = dp[i][0] = 1`。 #### 63. Unique Paths II **知识点：** - **问题描述：** - 同 62 题，但网格中存在障碍物。 - **解决方案分析：** - **动态规划：** - 定义 `dp[i][j]` 表示到达 `(i, j)` 的路径数量。 - 如果当前位置有障碍物，则 `dp[i][j] = 0`。 - 否则，`dp[i][j] = dp[i-1][j] + dp[i][j-1]`。 - 边界条件：`dp[0][j] = dp[i][0] = 1` 除非有障碍物。 #### 357. Count Numbers with Unique Digits **知识点：** - **问题描述：** - 给定一个整数 `n`，求出 `0` 到 `10^n - 1` 中所有数字中每一位都不相同的数字的数量。 - **解决方案分析：** - **数学：** - 通过观察规律来计算结果。 - 对于 `n` 位数，第一位可以选择 `9` 种数字（1-9），之后每一位都可以选择 `10 - i` 种数字（因为之前已经选择过的数字不能再选），直到 `n` 位。 #### 58. Length of Last Word **知识点：** - **问题描述：** - 给定一个字符串，返回最后一个单词的长度。 - **解决方案分析：** - **双指针：** - 从字符串末尾开始遍历，找到第一个非空格字符 `end`。 - 从 `end` 开始向前遍历，直到遇到空格或开头，找到 `start`。 - 返回 `end - start` 即为最后一个单词的长度。 #### 257. Binary Tree Paths **知识点：** - **问题描述：** - 给定一棵二叉树，返回所有从根节点到叶子节点的路径。 - **解决方案分析：** - **深度优先搜索（DFS）：** - 从根节点开始 DFS。 - 在叶子节点处记录路径。 - 回溯时移除最后加入的节点。 #### 113. Path Sum II **知识点：** - **问题描述：** - 给定一个二叉树和一个目标和，返回所有和为目标值的根节点到叶子节点的路径。 - **解决方案分析：** - **深度优先搜索（DFS）：** - 从根节点开始 DFS。 - 记录路径和累计和。 - 当达到叶子节点并且累计和等于目标和时，记录路径。 #### 19. Remove Nth Node From End of List **知识点：** - **问题描述：** - 删除链表中倒数第 `n` 个节点。 - **解决方案分析：** - **双指针：** - 定义两个指针 `p1` 和 `p2`。 - 先让 `p2` 向前移动 `n` 步。 - 然后同时移动两个指针，直到 `p2` 到达链表末尾。 - 此时 `p1` 指向倒数第 `n+1` 个节点，删除其下一个节点。 #### 121. Best Time to Buy and Sell Stock **知识点：** - **问题描述：** - 给定一个股票价格数组，找出买入和卖出的最佳时机，使得利润最大化。 - **解决方案分析：** - **动态规划：** - 遍历数组，记录最小价格 `minPrice` 和最大利润 `maxProfit`。 - 每次遍历时，更新 `minPrice` 和 `maxProfit`。 - 最终 `maxProfit` 即为最大利润。 #### 148. Sort List **知识点：** - **问题描述：** - 排序一个链表。 - **解决方案分析：** - **归并排序：** - 使用快慢指针找到中间节点。 - 递归排序左右两部分。 - 合并两个已排序的部分。 #### 21. Merge Two Sorted Lists **知识点：** - **问题描述：** - 合并两个已排序的链表。 - **解决方案分析：** - **迭代或递归：** - 比较两个链表的头节点。 - 将较小值节点链接到结果链表。 - 移动较小值节点所在链表的头指针。 - 直至一个链表遍历完，将另一个链表链接到结果链表末尾。 #### 312. Burst Balloons **知识点：** - **问题描述：** - 给定一组气球，每个气球有分数，每次戳破一个气球可以获得分数，求得分最大化的策略。 - **解决方案分析：** - **动态规划：** - 定义 `dp[i][j]` 为戳破 `i` 和 `j` 之间的所有气球的最大得分。 - 状态转移方程：`dp[i][j] = max(dp[i][j], nums[k]*nums[i-1]*nums[j+1] + dp[i][k] + dp[k][j])`，其中 `i <= k <= j`。 #### 24. Swap Nodes in Pairs **知识点：** - **问题描述：** - 给定一个链表，将每两个相邻节点交换。 - **解决方案分析：** - **迭代：** - 使用虚拟头节点简化边界处理。 - 依次处理每两个节点。 - 更新指针指向。 #### 75. Sort Colors **知识点：** - **问题描述：** - 给定一个只包含 `0`, `1`, `2` 的数组，将其按升序排序。 - **解决方案分析：** - **三指针：** - 定义三个指针 `low`, `mid`, `high`。 - `low` 和 `mid` 分别指向 `0` 和 `1` 的最后一个位置。 - `high` 指向 `2` 的第一个位置。 - 根据当前元素的值，交换位置或移动指针。 #### 48. Rotate Image **知识点：** - **问题描述：** - 将一个 `n x n` 的图像顺时针旋转 90 度。 - **解决方案分析：** - **原地旋转：** - 先将矩阵沿主对角线翻转。 - 再将每一行反转。 - 逆时针旋转 90 度的方法类似，但先反转每一行，再沿主对角线翻转。 #### 151. Reverse Words in a String **知识点：** - **问题描述：** - 给定一个字符串，反转其中的每个单词，并保持单词顺序不变。 - **解决方案分析：** - **双指针：** - 先反转整个字符串。 - 再从左到右遍历，使用两个指针找到每个单词的边界，并反转该单词。 - 跳过前后的空白字符。 #### 34. Search for a Range **知识点：** - **问题描述：** - 给定一个排序数组和一个目标值，在数组中查找目标值出现的第一个和最后一个位置。 - **解决方案分析：** - **二分查找：** - 分别查找目标值的第一个和最后一个位置。 - 对于第一个位置，当找到目标值时，继续在其左侧查找。 - 对于最后一个位置，当找到目标值时，继续在其右侧查找。 #### 42. Trapping Rain Water **知识点：** - **问题描述：** - 给定一个数组表示高度，计算能储存多少雨水。 - **解决方案分析：** - **动态规划：** - 计算每个位置左边最高和右边最高的值。 - 遍历数组，对于每个位置 `i`，计算能储存的水量为 `min(leftMax[i], rightMax[i]) - height[i]`。 - 累加所有位置的水量。 #### 11. Container With Most Water **知识点：** - **问题描述：** - 给定一个数组表示高度，求能围成的最大水量。 - **解决方案分析：** - **双指针：** - 定义两个指针 `left` 和 `right`。 - 计算当前围成的水量。 - 将指向较低高度的一端向内移动一位。 - 重复以上步骤直至两指针相遇。 这些算法问题涉及了多种数据结构和算法技术，包括但不限于图的遍历、动态规划、链表操作、二叉树遍历等。通过解决这些问题，不仅可以加深对基本数据结构和算法的理解，还能提升解决问题的能力。