当前位置：首页 > news >正文

代码随想录算法训练营第二十二天

news 2025/7/18 19:21:41

LeetCode.77 组合

题目链接组合

题解

class Solution {List<List<Integer>> result= new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {dfs(n,k,1);return result;}public void dfs(int n,int k,int count){if(path.size() == k) {result.add(new ArrayList<>(path));return ;}for(int i = count;i<=n;i++){path.add(i);dfs(n,k,i+1);path.removeLast();}}
}

解题思路

这段代码实现了组合问题的求解，即从 1 到 n 中选取 k 个数字的所有可能组合，使用了深度优先搜索（DFS）和回溯算法的思想。

代码的主要逻辑如下：

定义了两个成员变量：
- result：用于存储所有符合条件的组合
- path：用于递归过程中临时间结果，存储当前正在构建的组合
combine方法是入口函数：
- 接收两个参数 n（范围上限）和 k（选取的数字个数）
- 调用 dfs 方法开始深度优先搜索
- 返回最终的结果集
dfs方法是核心递归函数：
- 参数 count 表示当前开始考虑的数字（用于避免重复组合）
- 递归终止条件：当 path 的大小等于 k 时，说明找到了一个有效组合，将其加入 result
- 循环从 count 到 n，尝试将每个数字加入当前组合：
  - 将数字 i 加入 path
  - 递归调用 dfs，注意下一次搜索从 i+1 开始（保证组合的有序性，避免重复）
  - 回溯：移除 path 中最后加入的数字，尝试其他可能性

这个算法的时间复杂度是 O (C (n,k)×k)，其中 C (n,k) 是组合数，空间复杂度是 O (k)（递归栈深度和 path 的大小）。

LeetCode.216 组合总和III

题目链接组合总和III

题解

class Solution {List<List<Integer>> resList = new ArrayList<List<Integer>>();List<Integer> res = new ArrayList<>();public List<List<Integer>> combinationSum3(int k, int n) {if(n < k * (k + 1) /2) return resList;if(n > 45) return resList;dfs(k,n,0,1);return resList;}public void dfs(int k,int n,int sum,int index){if(sum > n) return ;if(res.size() == k){if(sum == n)  resList.add(new ArrayList<>(res));return;}for(int i = index;i<=9;i++){res.add(i);sum += i;dfs(k,n,sum,i+1);sum-=i;res.remove(res.size()-1);}}
}

解题思路

这段代码实现了 "组合总和 III" 的问题求解，即从 1 到 9 中选取 k 个不重复的数字，使得它们的和等于 n，找出所有可能的组合。

代码的主要逻辑如下：

定义了两个成员变量：
- resList：用于存储所有符合条件的组合
- res：用于递归过程中存储当前正在构建的组合
combinationSum3方法是入口函数：
- 首先进行了两个边界条件判断：
  - 如果 n 小于 1 到 k 的最小和（k*(k+1)/2），直接返回空结果
  - 如果 n 大于 9 个数的最大和（45），直接返回空结果
- 调用 dfs 方法开始深度优先搜索
- 返回最终的结果集
dfs方法是核心递归函数：
- 参数说明：
  - k：需要选取的数字个数
  - n：目标和
  - sum：当前组合的数字和
  - index：当前开始考虑的数字（避免重复组合）
- 剪枝操作：如果当前和已经大于 n，直接返回
- 递归终止条件：当 res 的大小等于 k 时，检查和是否等于 n，如果是则加入结果集
- 循环从 index 到 9，尝试将每个数字加入当前组合：
  - 将数字 i 加入 res
  - 将 i 累加到 sum 中
  - 递归调用 dfs，下一次搜索从 i+1 开始（保证数字不重复）
  - 回溯：从 sum 中减去 i，从 res 中移除最后加入的数字，尝试其他可能性

这个算法通过回溯法高效地搜索所有可能的组合，并通过剪枝操作减少不必要的计算，提高了效率。

LeetCode.17 电话号码的字母组合

题目链接电话号码的字母组合

题解

import java.util.ArrayList;
import java.util.List;class Solution {// 数字到字母的映射表，索引对应数字private static final String[] LETTER_MAP = {"",     // 0"",     // 1"abc",  // 2"def",  // 3"ghi",  // 4"jkl",  // 5"mno",  // 6"pqrs", // 7"tuv",  // 8"wxyz"  // 9};List<String> resList = new ArrayList<>();StringBuilder sb = new StringBuilder();public List<String> letterCombinations(String digits) {if (digits == null || digits.length() == 0) {return resList;}dfs(digits, 0);return resList;}public void dfs(String digits, int index) {// 递归终止条件：已处理完所有数字if (index == digits.length()) {resList.add(sb.toString());return;}// 获取当前数字对应的字母char digit = digits.charAt(index);// 检查是否是有效的数字字符if (digit < '0' || digit > '9') {return;}String letters = LETTER_MAP[digit - '0'];// 遍历所有可能的字母for (int i = 0; i < letters.length(); i++) {sb.append(letters.charAt(i));dfs(digits, index + 1);// 回溯：删除最后一个字符sb.deleteCharAt(sb.length() - 1);}}
}

解题思路

这段代码实现了电话号码的字母组合问题，即根据输入的数字字符串，返回所有可能的字母组合。这是一个经典的回溯算法应用场景。

代码的主要逻辑如下：

首先定义了一个静态数组LETTER_MAP，存储了数字 0-9 对应的字母，其中：
- 0 和 1 没有对应的字母（空字符串）
- 2 对应 "abc"，3 对应 "def"，以此类推
- 7 对应 "pqrs"，9 对应 "wxyz"（这两个数字对应 4 个字母）
定义了两个成员变量：
- resList：用于存储所有可能的字母组合结果
- sb：StringBuilder对象，用于在递归过程中构建当前的字母组合
letterCombinations方法是入口函数：
- 首先处理边界情况，如果输入为空或长度为 0，直接返回空列表
- 调用dfs方法开始深度优先搜索
- 返回最终的结果集
dfs方法是核心递归函数：
- 参数index表示当前正在处理的数字在输入字符串中的位置
- 递归终止条件：当index等于输入字符串长度时，说明已处理完所有数字，将当前构建的组合加入结果集
- 获取当前数字对应的字母字符串
- 遍历该字符串中的每个字母：
  - 将字母添加到StringBuilder中
  - 递归处理下一个数字（index + 1）
  - 回溯：删除StringBuilder中最后添加的字母，尝试其他可能性