题解 | #牛群分组II# Java
牛群分组II
https://www.nowcoder.com/practice/9ebc32fee9b54bfa9f9c3deca80febb0
首先,我们定义一个 cowCombinationSum2
函数,它接受一个整数数组 candidates
和一个目标整数 target
作为参数。我们首先将 candidates
数组排序,然后创建一个空的结果列表 res
和一个空的临时列表 re
。
接下来,我们调用 dfs
函数,它接受结果列表 res
、临时列表 re
、整数数组 candidates
、目标整数 target
和起始索引 start
作为参数。在 dfs
函数中,我们首先检查目标值是否为0,如果是,则将临时列表加入结果列表中并返回。
然后,我们从起始索引开始遍历整个数组。对于每个元素,如果它小于等于目标值,则将其加入临时列表中,并递归调用 dfs
函数,将目标值减去当前元素的值,并将起始索引加1。最后,我们将临时列表中最后一个元素删除。
当所有可能的组合都被找到后,我们将结果列表转换为二维数组并返回。
import java.util.*; public class Solution { public int[][] cowCombinationSum2 (int[] candidates, int target) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(candidates); dfs(res, new ArrayList<>(), candidates, target, 0); int[][] result = new int[res.size()][]; for (int i = 0; i < res.size(); i++) { result[i] = new int[res.get(i).size()]; for (int j = 0; j < res.get(i).size(); j++) { result[i][j] = res.get(i).get(j); } } return result; } void dfs(List<List<Integer>> res, List<Integer> re, int[] candidates, int target, int start) { if (target == 0) { res.add(re); return; } for (int i = start; i < candidates.length; i++) { if (candidates[i] <= target) { re.add(candidates[i]); dfs(res, new ArrayList<>(re), candidates, target - candidates[i], i+1); re.remove(re.size() - 1); } } } }
算法题刷刷刷 文章被收录于专栏
数组、链表、栈、队列、堆、树、图等。 查找和排序:二分查找、线性查找、快速排序、归并排序、堆排序等。 动态规划:背包问题、最长公共子序列、最短路径 贪心算法:活动选择、霍夫曼编码 图:深度优先搜索、广度优先搜索、拓扑排序、最短路径算法(如 Dijkstra、Floyd-Warshall) 字符串操作:KMP 算法、正则表达式匹配 回溯算法:八皇后问题、0-1 背包问题 分治算法:归并排序、快速排序