长沙城市建设档案馆网站,做网站一般都用什么字体,企业网站设计哪个好,020模版网站制作文章目录 组合总和⛅前言#x1f512;题目#x1f511;题解 组合总和
⛅前言 大家好#xff0c;我是知识汲取者#xff0c;欢迎来到我的LeetCode热题100刷题专栏#xff01; 精选 100 道力扣#xff08;LeetCode#xff09;上最热门的题目#xff0c;适合初识算法与数… 文章目录 组合总和⛅前言题目题解 组合总和
⛅前言 大家好我是知识汲取者欢迎来到我的LeetCode热题100刷题专栏 精选 100 道力扣LeetCode上最热门的题目适合初识算法与数据结构的新手和想要在短时间内高效提升的人熟练掌握这 100 道题你就已经具备了在代码世界通行的基本能力。在此专栏中我们将会涵盖各种类型的算法题目包括但不限于数组、链表、树、字典树、图、排序、搜索、动态规划等等并会提供详细的解题思路以及Java代码实现。如果你也想刷题不断提升自己就请加入我们吧QQ群号827302436。我们共同监督打卡一起学习一起进步。 博客主页知识汲取者的博客 LeetCode热题100专栏LeetCode热题100 Gitee地址知识汲取者 (aghp) - Gitee.com Github地址Chinafrfq · GitHub 题目来源LeetCode 热题 100 - 学习计划 - 力扣LeetCode全球极客挚爱的技术成长平台 PS作者水平有限如有错误或描述不当的地方恳请及时告诉作者作者将不胜感激 题目 原题链接39. 组合总和 - 力扣LeetCode 题解 解法一回溯剪枝 这个解法应该是最容易想到的有一点比较肯当满足题意的时候一定要通过new一个新对象加入到ans中 import java.util.*;
import java.util.stream.Collectors;/*** author ghp* title 组合总和*/
class Solution {public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger ans new ArrayList(10);ListInteger path new ArrayList(10);dfs(ans, path, candidates, target);// 去重for (ListInteger list : ans) {Collections.sort(list);}SetListInteger set ans.stream().collect(Collectors.toSet());ans new ArrayList(set);return ans;}private void dfs(ListListInteger ans, ListInteger path, int[] candidates, int target) {if (target 0) {// 剪枝return;}if (target 0) {// target0符合题意直接将遍历的路径添加到ans中一定要new一个新对象ans.add(new ArrayList(path));}for (int i 0; i candidates.length; i) {if (target - candidates[i] 0){// 当前不符合题意直接下一个continue;}target - candidates[i];path.add(candidates[i]);dfs(ans, path, candidates, target);target candidates[i];path.remove(path.size() - 1);}}
}复杂度分析 时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( n ) O(n) O(n) 其中 n n n 为数组中元素的个数 备注这里只是给出一个大概的时间复杂度我估算的 经过提交发现在所有Java提交中排名特别靠后所以这段代码肯定是可以优化的优化代码如下 这里主要有两个优化点 数据结构的优化原来的path是ArrayList现在的path是Deque。因为Deque进行删除和新增操作的耗时要远远低于ArrayListDeque删除和新增的时间复杂度是 O ( 1 ) O(1) O(1)而ArrayList的时间复杂度是 O ( n ) O(n) O(n)剪枝优化之前剪枝是在for循环外面实现的剪枝不够彻底会多遍历一层无用的数据。现在直接先对待遍历的元素进行排序然后直接在for循环中进行剪枝一下就提前将一些无用数据给剪枝了这样剪枝更加彻底代码逻辑优化前面我们每次递归都需要重新枚举所有元素的种类现在我们每次递归都传递当前层这样就能避免下次递归时遍历到重复的元素了从而有效避免了元素重复也减少了去重的时间和空间损耗 之前剪枝在for循环外面会多遍历一层无用的数据增加时间损耗 import java.util.*;/*** author ghp* title 组合总和*/
class Solution {public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger ans new ArrayList(10);DequeInteger path new LinkedList();// 对待选元素进行排序升序这是剪枝的前提Arrays.sort(candidates);dfs(ans, path, candidates, 0, target);return ans;}private void dfs(ListListInteger ans, DequeInteger path, int[] candidates, int step, int target) {if (target 0) {ans.add(new ArrayList(path));return;}for (int i step; i candidates.length; i) {if (target - candidates[i] 0) {// 剪枝。当前i已经比target大了那么i后面的肯定都要比target大break;}path.addLast(candidates[i]);dfs(ans, path, candidates, i, target - candidates[i]);// 恢复现场用于回溯path.removeLast();}}
}优化后的代码时间复杂度和前面的是一样的但是却能够提前过滤掉许多数据同时降低了递归的次数不仅有效降低了时间损耗也降低了空间损耗 解法二LeetCode官放提供的解法回溯剪枝 import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;/*** author ghp* title 组合总和*/
class Solution {public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger ans new ArrayList(10);DequeInteger path new LinkedList();dfs(ans, candidates, target, path, 0);return ans;}public void dfs(ListListInteger ans, int[] candidates, int target, DequeInteger path, int step) {if (step candidates.length) {// 遍历到最底层了还没有发现return;}if (target 0) {ans.add(new ArrayList(path));return;}// 直接遍历下一层dfs(ans, candidates, target, path, step 1);// 遍历当前层if (target - candidates[step] 0) {// 这个if相当于进行一个筛选也就是剪枝path.addLast(candidates[step]);dfs(ans, candidates, target - candidates[step], path, step);path.removeLast();}}
}复杂度分析 时间复杂度 O ( S ) O(S) O(S)S为所有可行解的长度之和空间复杂度 O ( t a r g e t ) O(target) O(target)
