算法刷题记录——LeetCode篇(1.8) [第71~80题](持续更新)

更新时间：2025-04-10

• 算法题解目录汇总：算法刷题记录——题解目录汇总
• 技术博客总目录：计算机技术系列博客——目录页

优先整理热门100及面试150，不定期持续更新，欢迎关注！

---

72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3

解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5

解释：
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

---

方法一：标准动态规划

使用二维数组 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作数。通过状态转移方程处理插入、删除、替换三种操作。

• 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]
• 否则：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

代码实现(Java)：

class Solution {public int minDistance(String word1, String word2) {int m = word1.length(), n = word2.length();int[][] dp = new int[m+1][n+1];// 初始化边界条件for (int i = 0; i <= m; i++) dp[i][0] = i;for (int j = 0; j <= n; j++) dp[0][j] = j;// 填充dp表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1.charAt(i-1) == word2.charAt(j-1)) {dp[i][j] = dp[i-1][j-1];} else {dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]),dp[i-1][j-1]) + 1;}}}return dp[m][n];}
}

复杂度分析：

• 时间复杂度：O(m×n)，双重循环遍历所有字符组合。
• 空间复杂度：O(m×n)，存储二维动态规划表。

---

方法二：空间优化动态规划

通过滚动数组将二维空间压缩为一维数组，利用临时变量保存左上角的值（对应二维数组的 dp[i-1][j-1]）。

代码实现(Java)：

class Solution {public int minDistance(String word1, String word2) {int m = word1.length(), n = word2.length();if (m < n) {return minDistance(word2, word1); // 确保word2较短以优化空间}int[] dp = new int[n+1];// 初始化第一行（word1为空时的操作数）for (int j = 0; j <= n; j++) dp[j] = j;// 逐行更新for (int i = 1; i <= m; i++) {int prev = dp[0]; // 保存左上角的值（对应dp[i-1][j-1]）dp[0] = i; // 当前行的第一个元素（word2为空时的操作数）for (int j = 1; j <= n; j++) {int temp = dp[j]; // 保存旧值，作为下一轮的左上角值if (word1.charAt(i-1) == word2.charAt(j-1)) {dp[j] = prev;} else {dp[j] = Math.min(Math.min(dp[j], dp[j-1]),prev) + 1;}prev = temp; // 更新左上角的值}}return dp[n];}
}

复杂度分析：

• 时间复杂度：O(m×n)，与标准动态规划相同。
• 空间复杂度：O(n)，仅维护一维数组。

---

方法三：递归 + 记忆化

递归计算每个子问题的解，并通过记忆化缓存避免重复计算。适用于小规模输入或理解问题本质，但不推荐用于大规模数据。

代码实现(Java)：

class Solution {private Integer[][] memo;private String word1, word2;public int minDistance(String word1, String word2) {this.word1 = word1;this.word2 = word2;memo = new Integer[word1.length()][word2.length()];return dfs(word1.length()-1, word2.length()-1);}private int dfs(int i, int j) {if (i < 0) return j+1; // word1已空，需插入j+1个字符if (j < 0) return i+1; // word2已空，需删除i+1个字符if (memo[i][j] != null) return memo[i][j];if (word1.charAt(i) == word2.charAt(j)) {memo[i][j] = dfs(i-1, j-1);} else {int insert = dfs(i, j-1) + 1;int delete = dfs(i-1, j) + 1;int replace = dfs(i-1, j-1) + 1;memo[i][j] = Math.min(Math.min(insert, delete), replace);}return memo[i][j];}
}

复杂度分析：

• 时间复杂度：O(m×n)，但递归调用栈可能带来额外开销。
• 空间复杂度：O(m×n)，用于存储记忆化表。

---

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4

---

方法一：二维转一维的二分查找

将二维矩阵视为连续的一维有序数组，通过数学计算将一维索引转换为二维坐标，进行标准二分查找。

代码实现(Java)：

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int left = 0, right = m * n - 1;while (left <= right) {int mid = left + (right - left) / 2;// 计算对应的二维坐标int row = mid / n;int col = mid % n;int val = matrix[row][col];if (val == target) {return true;} else if (val < target) {left = mid + 1;} else {right = mid - 1;}}return false;}
}

复杂度分析：

• 时间复杂度：O(log(mn))，
• 空间复杂度：O(1)。

---

方法二：两次二分查找

先通过二分确定目标所在行，再在该行中进行二分查找。

代码实现(Java)：

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;// 查找目标所在行int low = 0, high = m - 1;while (low <= high) {int mid = (low + high) / 2;if (matrix[mid][0] > target) {high = mid - 1;} else {low = mid + 1;}}// high是可能所在行if (high < 0) return false;int row = high;// 检查该行范围if (matrix[row][n - 1] < target) return false;// 行内二分查找int left = 0, right = n - 1;while (left <= right) {int mid = (left + right) / 2;if (matrix[row][mid] == target) {return true;} else if (matrix[row][mid] < target) {left = mid + 1;} else {right = mid - 1;}}return false;}
}

复杂度分析：

• 时间复杂度：O(log m + log n)，
• 空间复杂度：O(1)。

---

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

示例 2：

输入：s = "a", t = "a"
输出："a"

解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""

解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 10^5
• s 和 t 由英文字母组成

进阶：
你能设计一个在 O(m+n) 时间内解决此问题的算法吗？

---

方法一：滑动窗口 + 双指针（最优解法）

• 使用滑动窗口维护一个可变区间，通过移动左右指针动态调整窗口大小。
• 利用数组统计目标字符出现次数，并通过计数器 valid 判断当前窗口是否满足条件。
• 当窗口满足条件时收缩左边界，寻找最小覆盖子串。

代码实现(Java)：

public class Solution {public String minWindow(String s, String t) {int[] need = new int[128];  // 存储t中各字符的需求量int count = 0;              // 记录t中不同字符的数量for (char c : t.toCharArray()) {if (need[c] == 0) count++;need[c]++;}int[] window = new int[128];// 当前窗口各字符的出现次数int left = 0, right = 0;    // 滑动窗口的左右指针int valid = 0;              // 满足条件的字符数量int start = 0;              // 最小窗口的起始位置int minLen = Integer.MAX_VALUE; // 最小窗口长度while (right < s.length()) {char c = s.charAt(right);right++;// 若当前字符是目标字符，更新窗口统计if (need[c] > 0) {window[c]++;// 当该字符数量刚好满足需求时，valid加1if (window[c] == need[c]) {valid++;}}// 当前窗口满足条件时，尝试收缩左边界while (valid == count) {// 更新最小窗口信息if (right - left < minLen) {start = left;minLen = right - left;}char d = s.charAt(left);left++;// 若移除的是目标字符，更新窗口统计if (need[d] > 0) {if (window[d] == need[d]) {valid--; // 该字符不再满足需求，valid减1}window[d]--;}}}return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);}
}

复杂度分析：

• 时间复杂度：O(m + n)，其中 m 和 n 分别为 s 和 t 的长度。每个字符最多被左右指针各访问一次。
• 空间复杂度：O(1)，固定长度的数组（ASCII 字符集）。

---

方法二：优化哈希表版本

与滑动窗口思路一致，但使用哈希表（HashMap）替代数组统计字符频率。虽然逻辑更通用，但性能略低于数组实现。

代码实现(Java)：

public class Solution {public String minWindow(String s, String t) {Map<Character, Integer> need = new HashMap<>();for (char c : t.toCharArray()) {need.put(c, need.getOrDefault(c, 0) + 1);}Map<Character, Integer> window = new HashMap<>();int left = 0, right = 0, valid = 0;int start = 0, minLen = Integer.MAX_VALUE;while (right < s.length()) {char c = s.charAt(right);right++;if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) + 1);if (window.get(c).equals(need.get(c))) {valid++;}}while (valid == need.size()) {if (right - left < minLen) {start = left;minLen = right - left;}char d = s.charAt(left);left++;if (need.containsKey(d)) {if (window.get(d).equals(need.get(d))) {valid--;}window.put(d, window.get(d) - 1);}}}return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);}
}

复杂度分析：

• 时间复杂度：O(m + n)，哈希表操作的时间复杂度为均摊 O(1)。
• 空间复杂度：O(k)，k 为 t 中不同字符的数量。

---

方法三：暴力枚举

枚举所有可能的子串，检查是否覆盖 t 的所有字符。该方法时间复杂度为 O(m²)，无法通过大规模数据测试，但有助于理解问题本质。

代码实现(Java)：

public class Solution {public String minWindow(String s, String t) {int minLen = Integer.MAX_VALUE;String result = "";for (int i = 0; i < s.length(); i++) {for (int j = i + t.length(); j <= s.length(); j++) {String sub = s.substring(i, j);if (isCover(sub, t)) {if (j - i < minLen) {minLen = j - i;result = sub;}}}}return result;}private boolean isCover(String sub, String t) {int[] count = new int[128];for (char c : sub.toCharArray()) count[c]++;for (char c : t.toCharArray()) {count[c]--;if (count[c] < 0) return false;}return true;}
}

复杂度分析：

• 时间复杂度：O(m² × n)，其中 m 为 s 的长度，n 为 t 的长度。
• 空间复杂度：O(1)，统计字符频率的数组长度固定。

---

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素互不相同

---

方法一：回溯法

通过递归生成所有子集，每次递归选择一个元素加入路径，并确保后续元素不重复选择。

代码实现(Java)：

public class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> res = new ArrayList<>();backtrack(res, new ArrayList<>(), nums, 0);return res;}private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, int start) {res.add(new ArrayList<>(path)); // 添加当前路径到结果for (int i = start; i < nums.length; i++) {path.add(nums[i]);          // 选择当前元素backtrack(res, path, nums, i + 1); // 递归处理后续元素path.remove(path.size() - 1); // 撤销选择（回溯）}}
}

复杂度分析：

• 时间复杂度： O(n * 2^n)，每个子集生成需要 O(n) 时间，总共有 2^n 个子集。
• 空间复杂度： O(n)，递归栈深度最大为 n，结果空间额外占用 O(n * 2^n)。

---

方法二：迭代法

逐步扩展子集，每次将新元素添加到所有现有子集中，生成新子集。

代码实现(Java)：

public class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> res = new ArrayList<>();res.add(new ArrayList<>()); // 初始空集for (int num : nums) {List<List<Integer>> newSubsets = new ArrayList<>();for (List<Integer> subset : res) {List<Integer> newSubset = new ArrayList<>(subset);newSubset.add(num); // 生成新子集newSubsets.add(newSubset);}res.addAll(newSubsets); // 合并新子集}return res;}
}

复杂度分析：

• 时间复杂度： O(n * 2^n)，每次迭代处理 2^i 个子集，总操作次数为 2^(n+1) - 1。
• 空间复杂度： O(n * 2^n)，存储所有子集。

---

方法三：位运算法

利用二进制掩码表示元素是否被选中，遍历所有可能的掩码生成子集。

代码实现(Java)：

public class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> res = new ArrayList<>();int n = nums.length;int total = 1 << n; // 计算 2^nfor (int mask = 0; mask < total; mask++) {List<Integer> subset = new ArrayList<>();for (int i = 0; i < n; i++) {if ((mask & (1 << i)) != 0) { // 检查第i位是否为1subset.add(nums[i]);}}res.add(subset);}return res;}
}

复杂度分析：

• 时间复杂度： O(n * 2^n)，遍历所有掩码并检查每一位。
• 空间复杂度： O(n * 2^n)，存储所有子集。

---

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

进阶：
你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

---

方法：回溯法（DFS + 剪枝优化）

通过深度优先搜索遍历所有可能的路径，利用回溯和剪枝策略减少无效搜索。预处理阶段检查字符数量是否足够，大幅提升效率。

代码实现(Java)：

class Solution {public boolean exist(char[][] board, String word) {// 预处理：检查字符数量是否足够Map<Character, Integer> boardCount = new HashMap<>();for (char[] row : board) {for (char c : row) {boardCount.put(c, boardCount.getOrDefault(c, 0) + 1);}}Map<Character, Integer> wordCount = new HashMap<>();for (char c : word.toCharArray()) {wordCount.put(c, wordCount.getOrDefault(c, 0) + 1);}for (char c : wordCount.keySet()) {if (boardCount.getOrDefault(c, 0) < wordCount.get(c)) {return false;}}// 回溯搜索for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (board[i][j] == word.charAt(0) && dfs(board, i, j, word, 0)) {return true;}}}return false;}private boolean dfs(char[][] board, int i, int j, String word, int index) {if (index == word.length() - 1) return true;char tmp = board[i][j];board[i][j] = '#'; // 标记为已访问int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};for (int[] dir : dirs) {int x = i + dir[0], y = j + dir[1];if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) continue;if (board[x][y] != word.charAt(index + 1)) continue;if (dfs(board, x, y, word, index + 1)) {board[i][j] = tmp; // 提前回溯不影响结果return true;}}board[i][j] = tmp; // 回溯，恢复原字符return false;}
}

复杂度分析：

• 时间复杂度： 最坏情况 O(M*N*4^L)，其中 M、N 为网格尺寸，L 为单词长度。预处理优化后实际运行效率显著提升。
• 空间复杂度： O(L) 递归栈深度与单词长度相关。

---

80. 删除有序数组中的重复项 II

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下：

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {print(nums[i]);
}

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]

解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]

解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

提示：

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• nums 已按升序排列

---

方法：双指针

通过比较当前元素与写入位置的前两个元素来判断是否需要保留当前元素。

1. 边界处理：如果数组长度小于等于 2，直接返回原长度，因为所有元素都满足条件。
2. 初始化指针：index 表示当前可写入的位置，初始化为 2（因为前两个元素无需检查）。
3. 遍历数组：从第三个元素开始遍历：
   • 如果当前元素 nums[i] 与 index - 2 位置的元素不同，说明当前元素可以保留。
   • 将 nums[i] 写入 index 位置，并移动 index 指针。
4. 返回结果：最终 index 即为新数组的长度。

代码实现(Java)：

class Solution {public int removeDuplicates(int[] nums) {if (nums.length <= 2) {return nums.length;}int index = 2;for (int i = 2; i < nums.length; i++) {if (nums[i] != nums[index - 2]) {nums[index] = nums[i];index++;}}return index;}
}

复杂度分析：

• 时间复杂度：O(n)；
• 空间复杂度：O(1)。

---

声明

1. 本文版权归 CSDN 用户 Allen Wurlitzer 所有，遵循CC-BY-SA协议发布，转载请注明出处。
2. 本文题目来源 力扣-LeetCode ，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。