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

【LeetCode热题100】打卡第16天:组合总和

文章目录

  • 组合总和
    • ⛅前言
    • 🔒题目
    • 🔑题解

组合总和

⛅前言

大家好,我是知识汲取者,欢迎来到我的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 List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> ans = new ArrayList<>(10);List<Integer> path = new ArrayList<>(10);dfs(ans, path, candidates, target);// 去重for (List<Integer> list : ans) {Collections.sort(list);}Set<List<Integer>> set = ans.stream().collect(Collectors.toSet());ans = new ArrayList<>(set);return ans;}private void dfs(List<List<Integer>> ans, List<Integer> path, int[] candidates, int target) {if (target < 0) {// 剪枝return;}if (target == 0) {// target==0,符合题意,直接将遍历的路径添加到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提交中,排名特别靠后,所以这段代码肯定是可以优化的,优化代码如下:

    这里主要有两个优化点:

    1. 数据结构的优化:原来的path是ArrayList,现在的path是Deque。因为Deque进行删除和新增操作的耗时要远远低于ArrayList(Deque删除和新增的时间复杂度是 O ( 1 ) O(1) O(1),而ArrayList的时间复杂度是 O ( n ) O(n) O(n)
    2. 剪枝优化:之前剪枝是在for循环外面实现的,剪枝不够彻底,会多遍历一层无用的数据。现在直接先对待遍历的元素进行排序,然后直接在for循环中进行剪枝,一下就提前将一些无用数据给剪枝了,这样剪枝更加彻底
    3. 代码逻辑优化:前面我们每次递归,都需要重新枚举所有元素的种类,现在我们每次递归都传递当前层,这样就能避免下次递归时,遍历到重复的元素了,从而有效避免了元素重复,也减少了去重的时间和空间损耗

    之前剪枝在for循环外面,会多遍历一层无用的数据,增加时间损耗:

    在这里插入图片描述

    import java.util.*;/*** @author ghp* @title 组合总和*/
    class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> ans = new ArrayList<>(10);Deque<Integer> path = new LinkedList<>();// 对待选元素进行排序(升序),这是剪枝的前提Arrays.sort(candidates);dfs(ans, path, candidates, 0, target);return ans;}private void dfs(List<List<Integer>> ans, Deque<Integer> 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();}}
    }
    

    优化后的代码,时间复杂度和前面的是一样的,但是却能够提前过滤掉许多数据,同时降低了递归的次数,不仅有效降低了时间损耗,也降低了空间损耗

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NmbigXUV-1686191441561)(D:/%E7%94%A8%E6%88%B7/ghp/Pictures/Typora/image-20230608101453910.png)]

  • 解法二:LeetCode官放提供的解法,回溯+剪枝

    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.LinkedList;
    import java.util.List;/*** @author ghp* @title 组合总和*/
    class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> ans = new ArrayList<>(10);Deque<Integer> path = new LinkedList<>();dfs(ans, candidates, target, path, 0);return ans;}public void dfs(List<List<Integer>> ans, int[] candidates, int target, Deque<Integer> 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)

相关文章:

【LeetCode热题100】打卡第16天:组合总和

文章目录 组合总和⛅前言&#x1f512;题目&#x1f511;题解 组合总和 ⛅前言 大家好&#xff0c;我是知识汲取者&#xff0c;欢迎来到我的LeetCode热题100刷题专栏&#xff01; 精选 100 道力扣&#xff08;LeetCode&#xff09;上最热门的题目&#xff0c;适合初识算法与数…...

tinkerCAD案例:1.戒子环

基本戒指 在本课中&#xff0c;您将学习使用圆柱形状制作戒指。来吧&#xff01; 说明 将圆柱体拖动到工作平面上并使其成为孔。 圆柱体应缩放以适合其制造手指。 在本例中&#xff0c;我们将使用 17mm 作为直径&#xff0c;但请根据您的需要随意调整尺寸。 将“圆柱”形状拖…...

RPC接口测试技术-Tcp 协议的接口测试

【摘要】 首先明确 Tcp 的概念&#xff0c;针对 Tcp 协议进行接口测试&#xff0c;是指基于 Tcp 协议的上层协议比如 Http &#xff0c;串口&#xff0c;网口&#xff0c; Socket 等。这些协议与 Http 测试方法类似&#xff08;具体查看接口自动化测试章节&#xff09;&#xf…...

MyBatis Plus基本用法-SpringBoot框架

依赖 使用 Mybatis Plus 框架时&#xff0c;需要添加以下依赖&#xff1a; <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>latest-version</version> </dependency…...

指针--指针变量的定义和初始化

存放变量的地址需要一种特殊类型的变量&#xff0c;这种特殊的数据类型就是指针&#xff08;Pointer&#xff09;。 具有指针类型的变量&#xff0c;称为指针变量&#xff0c;它时专门用于存储变量的地址值和变量。 其定义形式如下&#xff1a; 类型关键字 * 指针变量名&#x…...

Web基本概念

一、前言 World Wide Web的简称&#xff0c;是一个由许多互相链接的超文本组成的系统&#xff0c;通过互联网访问 &#xff08;为用户提供信息&#xff09; 静态网页 仅适用于不能经常更改内容的网页&#xff1b; 动态网页 网络编程技术创建的页面&#xff1b;通过在传统的静态…...

Niagara—— Texture Sample 与 Particle Subuv 区别

目录 一&#xff0c;Texture Sample 二&#xff0c;Particle Subuv 一&#xff0c;Texture Sample 此节点是最基本的采样节点&#xff0c;依据UV坐标来采样Texture&#xff1b; MipValueMode&#xff0c;设置采样的Mipmap Level&#xff1b; None&#xff0c;根据当前Texture…...

如何在食品行业运用IPD?

食品是我国重要的民生产业之一&#xff0c;是保障和满足人民群众不断增长消费需求的重要支撑。食品指各种供人食用或者饮用的成品和原料以及按照传统既是食品又是药品的物品&#xff0c;包括加工食品&#xff0c;半成品和未加工食品&#xff0c;不包括烟草或只作药品用的物质。…...

如何用pandas进行条件分组计算?

Pandas提供了强大的分组聚合功能&#xff0c;可以轻松进行条件分组计算和统计。本文通过一个例子&#xff0c;展示如何使用Pandas的.groupby()和.agg()方法进行条件分组计算。 准备数据 假设有这样一个字典数据: dict { 姓名: [张三&#xff0c;李四&#xff0c;王五&#x…...

tomcat如何调优,涉及哪些参数?

Tomcat是一个流行的开源Java Servlet容器&#xff0c;用于部署和管理Java Web应用程序。调优Tomcat可以提高性能、并发处理能力和稳定性。以下是一些常见的Tomcat调优参数和技巧&#xff1a; 1.调整内存参数&#xff1a; -Xms&#xff1a;指定Tomcat启动时的初始堆内存大小。 -…...

java培训机构学校教学教务选课管理平台springboot+vue

近年来&#xff0c;随着培训机构机构规模的逐渐增大&#xff0c;人工书写的方式已经不能满足如此庞大的数据。为了更好的适应信息时代的高效性&#xff0c;一个利用计算机来实现培训机构教务管理工作的系统将必然诞生。基于这一点&#xff0c;设计了一个培训机构教务管理系统&a…...

半导体(TSS)放电管的两大选购注意事项及选型小策略

固体放电管&#xff0c;是以半导体工艺制作而成的&#xff0c;因此我们也称为半导体&#xff08;TSS&#xff09;放电管&#xff0c;它常在电路中并联使用&#xff0c;具备伏安特性。 TSS放电管在电路中类似开关&#xff0c;在正常工作时不动作&#xff0c;但一般被保护电路受到…...

05-使用Vue3 + Vue CLI 实现前端模块的搭建

1、环境准备 流程:安装node得到npm,使用npm安装vue cli(脚手架),使用vue cli创建项目。 Vue CLI版本和Node版本有关,用Node V12只能下载到Vue CLI V4.X,必须用Node V18才能下载到Vue CLI V5.X IDEA支持配置多个版本的Node,类似配置多个JDK。 node.js安装 1、官网下载…...

3.1 增加多进程执行playwright

增加了多进程的方式执行测试代码&#xff0c;对代码改动比较大 1、case case目录依然是自动生成 2、config dir_collection.py新增了配置 mkdir_collections [case,log,img, ] del_collections [results,report ] del_regex temp3、data/img/log/resource/video data/im…...

关于单片机的时钟浅谈及STM32F103/F030单片机的内外时钟切换问题

绪论 本文主要讲解单片机的时钟系统的相关知识&#xff0c;并进行超频测试&#xff0c;同时介绍如何在STM32F0单片机上进行内外时钟的切换&#xff0c;在不使用外部晶振或者外部晶振不启动时自动切换内部时钟的方法。 一、杂谈 问题来源于群里的一次问答&#xff1a; 诚然&…...

centos6.10环境下安装php7.4(基于WLNMP包)

centos6系统已经被官网停止维护&#xff0c;要安装软件必须用第三方的RPM包&#xff0c;下面使用yum安装php7.4正式版&#xff0c;当前基于WLNMP提供的一键安装包来安装 1、添加epel源 yum install epel-release yum install epel-release 2、添加WLNMP一键安装包源 rpm -iv…...

Qt使用第三方库openssl进行RSA加密解密操作详解

一、openssl库的编译,可以参考文档: https://blog.csdn.net/liang19890820/article/details/51658574/ 因为我这里使用的是windows操作系统,可以直接下载exe格式的安装文件,直接安装即可,就包含了我们需要的头文件和库文件,省去了编译操作。exe安装文件下载地址: htt…...

激发数学思维:GPT-4实证研究探索挑战性数学问题

深度学习自然语言处理 原创作者&#xff1a;wkk 考虑到自然语言在许多科学和工程领域表达的数学问题的丰富性&#xff0c;使用大语言模型(LLM)来解决数学问题是一项有趣的研究工作。今天给大家介绍一篇微软研究院联合欧美高校关于如何使用GPT-4解决数学问题的研究论文。 之前的…...

如何配置IP地址

一.自动获取IP 1.dhclient 2.ifconfig 通过这个命令可以查看系统有几块网卡和网卡的IP。 如果您的Linux有多块网卡&#xff0c;那么在Linux中它会显示成eth1, eth2 依此类推 二.手动配置IP 如果您的虚拟机不能自动获取IP&#xff0c;那么只能手动配置&#xff0c;配置方法为&am…...

CentOS + Nginx 环境自动申请和部署Let‘s Encrypt免费SSL证书教程

文章目录 步骤 1&#xff1a;安装Certbot工具步骤 2&#xff1a;配置Nginx服务器步骤 3&#xff1a;生成SSL证书步骤 4&#xff1a;配置Nginx以使用SSL证书步骤 5&#xff1a;重新加载Nginx配置步骤 6&#xff1a;自动续期证书 本文介绍如何在 CentOS Nginx 环境下&#xff0c…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...