LeetCode40:组合总和II
原题地址:. - 力扣(LeetCode)
题目描述
给定一个候选人编号的集合
candidates和一个目标数target,找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用 一次 。注意:解集不能包含重复的组合。
示例 1:
输入: candidates =[10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]提示:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
解题思路
从给定的候选数字数组
candidates中找出所有和为target的组合,但与之前的问题不同,这个变种允许使用候选数字数组中的数字多次,且组合中的数字不一定要连续。代码中使用了深度优先搜索(DFS)算法来解决这个问题,并进行了一些优化:
- 预处理:首先对候选数字数组进行排序,并使用
freq数组来存储每个不同数字的频率。- DFS:深度优先搜索函数
dfs用于递归地构建所有可能的组合。在
dfs方法中,我们有两个选择:
- 跳过当前数字:直接递归调用
dfs方法,尝试下一个数字。- 选择当前数字:如果当前目标
rest大于等于候选数字,则将该数字添加到sequence列表中,并递归调用dfs方法,目标减去该数字的倍数,直到超过剩余目标或超过当前数字的频率。
代码实现
class Solution {// 存储每个数字的频率List<int[]> freq = new ArrayList<>();// 存储所有有效的组合List<List<Integer>> ans = new ArrayList<>();// 存储当前的组合List<Integer> sequence = new ArrayList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {// 对候选数字数组进行排序Arrays.sort(candidates);// 计算每个数字的频率for (int num : candidates) {int size = freq.size();// 如果当前数字与前一个数字不同,或者freq为空,则添加新的频率记录if (freq.isEmpty() || num != freq.get(size - 1)[0]) {freq.add(new int[]{num, 1});} else {// 否则,增加相同数字的频率++freq.get(size - 1)[1];}}// 开始深度优先搜索dfs(0, target);// 返回所有有效的组合return ans;}public void dfs(int pos, int rest) {// 如果剩余目标为0,说明找到了一个有效的组合,添加到结果列表中if (rest == 0) {ans.add(new ArrayList<>(sequence));return;}// 如果位置超出freq数组范围,或者剩余目标小于当前数字,返回if (pos == freq.size() || rest < freq.get(pos)[0]) {return;}// 先不选择当前数字,递归搜索下一个数字dfs(pos + 1, rest);// 选择当前数字,最多选择至多等于剩余目标或当前数字频率的最小值int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);for (int i = 1; i <= most; ++i) {// 将当前数字添加到组合中sequence.add(freq.get(pos)[0]);// 递归搜索下一个数字,目标减去当前数字dfs(pos + 1, rest - i * freq.get(pos)[0]);}// 回溯,移除添加的当前数字for (int i = 1; i <= most; ++i) {sequence.remove(sequence.size() - 1);}}
}
复杂度分析
时间复杂度:最坏情况下,DFS 会尝试所有可能的组合,但由于进行了剪枝(即跳过大于剩余目标的数字),实际的时间复杂度通常要好于 O(2^n),但最坏情况下仍然是指数级别的。
空间复杂度:空间复杂度主要取决于递归栈的深度和
sequence列表的大小。最坏情况下,递归栈的深度和sequence的大小都不超过target,所以空间复杂度为 O(target)。
相关文章:
LeetCode40:组合总和II
原题地址:. - 力扣(LeetCode) 题目描述 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意ÿ…...
基于Python+Vue开发的旅游景区管理系统
项目简介 该项目是基于PythonVue开发的旅游景区管理系统(前后端分离),这是一项为大学生课程设计作业而开发的项目。该系统旨在帮助大学生学习并掌握Python编程技能,同时锻炼他们的项目设计与开发能力。通过学习基于Python的旅游景…...
嵌入式硬件杂谈(一)-推挽 开漏 高阻态 上拉电阻
引言:对于嵌入式硬件这个庞大的知识体系而言,太多离散的知识点很容易疏漏,因此对于这些容易忘记甚至不明白的知识点做成一个梳理,供大家参考以及学习,本文主要针对推挽、开漏、高阻态、上拉电阻这些知识点的学习。 目…...
在arm64架构下, Ubuntu 18.04.5 LTS 用命令安装和卸载qt4、qt5
问题:需要在 arm64下安装Qt,QT源码编译失败以后,选择在线安装! 最后安装的版本是Qt5.9.5 和QtCreator 4.5.2 。 一、ubuntu安装qt4的命令(亲测有效): sudo add-apt-repository ppa:rock-core/qt4 sudo apt updat…...
k8s笔记——核心概念
什么是K8s Kubernetes 也称为 K8s,是用于自动部署、扩缩和管理容器化应用程序的开源系统。 Kubernetes 最初是由 Google 工程师作为 Borg 项目开发和设计的,后于 2015 年捐赠给 云原生计算基金会(CNCF)。 什么是 Kubernetes 集群…...
大数据新视界 -- 大数据大厂之 Impala 性能飞跃:动态分区调整的策略与方法(上)(21 / 30)
💖💖💖亲爱的朋友们,热烈欢迎你们来到 青云交的博客!能与你们在此邂逅,我满心欢喜,深感无比荣幸。在这个瞬息万变的时代,我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...
开源模型应用落地-qwen模型小试-Qwen2.5-7B-Instruct-tool usage入门-并行调用多个tools(五)
一、前言 Qwen-Agent 是一个利用开源语言模型Qwen的工具使用、规划和记忆功能的框架。其模块化设计允许开发人员创建具有特定功能的定制代理,为各种应用程序提供了坚实的基础。同时,开发者可以利用 Qwen-Agent 的原子组件构建智能代理,以理解和响应用户查询。 本篇将介绍如何…...
蓝桥杯每日真题 - 第8天
题目:(子2023) 题目描述(14届 C&C B组A题) 解题思路: 该代码通过动态计算包含数字 "2023" 的子序列出现次数。主要思路是: 拼接序列:将1到2023的所有数字按顺序拆分…...
论云游戏的性能与性价比,ToDesk、青椒云、顺网云游戏等具体实操看这篇就够了
文章目录 一、前言二、云电脑产品基础介绍2.1 ToDesk云电脑2.1.1 ToDesk云电脑硬件参数2.1.2 ToDesk云电脑鲁大师跑分2.1.3 ToDesk云电脑收费方式2.1.4 ToDesk云电脑特色功能 2.2 青椒云2.2.1 青椒云游戏娱乐硬件配置2.2.2 青椒云云电脑鲁大师跑分2.2.3 青椒云收费方式2.2.4 青…...
Jmeter中的定时器(二)
5--JSR223 Timmer 功能特点 自定义延迟逻辑:使用脚本语言动态计算请求之间的延迟时间。灵活控制:可以根据测试数据和条件动态调整延迟时间。支持多种脚本语言:支持 Groovy、JavaScript、BeanShell 等多种脚本语言。 支持的脚本语言 Groov…...
华为HCIP-openEuler考试内容大纲:备考必看!
华为HCIP-openEuler认证考试作为ICT领域的一项重要技术认证,已经成为越来越多IT从业者追求的目标。无论你是想提升自己的技术能力,还是为了未来的职业发展,HCIP-openEuler都是一个极具价值的认证。那么,如何高效备考,顺…...
Vector 深度复制记录
有的时候数据得复制过去 有个疑问,自动分配内存吗? 不是估计有变化, 得在看看 指针作为值复制了 … … 挺好,修改原有的值 x86 的 SIM 程序 还有点问题 ; 无法直接绕过硬件错误 。。。 x86 gdb 没有问题 就是运行出现了问题,怎么解决;正常初始化没有问题…...
Go语言实现用户登录Web应用
文章目录 1. Go语言Web框架1.1 框架比较1.2 安装Gin框架 2. 实现用户登录功能2.1 创建项目目录2.2 打开项目目录2.3 创建登录Go程序2.4 创建模板页面2.4.1 登录页面2.4.2 登录成功页面2.4.3 登录失败页面 3. 测试用户登录项目3.1 运行登录主程序3.2 访问登录页面3.3 演示登录成…...
Android CarrierConfig 参数项和正则匹配逻辑
背景 在编写CarrierConfig的时候经常出现配置不生效的情况,比如运营商支持大范围的imsi,或者是测试人员写卡位数的问题等等,因此就需要模式匹配(包含但不限于正则表达式)。 基本概念: 模式匹配涉及定义一个“模式”&a…...
微信小程序中使用离线版阿里云矢量图标
前言 阿里矢量图库提供的在线链接服务仅供平台体验和调试使用,平台不承诺服务的稳定性,企业客户需下载字体包自行发布使用并做好备份。 1.下载图标 将阿里矢量图库的图标先下载下来 解压如下 2.转换格式 贴一个地址用于转换格式:Onlin…...
hive的tblproperties支持修改的属性
文章目录 一、介绍二、查看TBLPROPERTIES属性三、修改TBLPROPERTIES属性 一、介绍 TBLPROPERTIES用途:向表中添加自定义或预定义的元数据属性,并设置它们的赋值。在hive建表时,可设置TBLPROPERTIES参数修改表的元数据,也能通过AL…...
移动端开发
一、一些概念 (一)、屏幕相关 1、屏幕大小 指屏幕的对角线长度,单位是英寸(inch)。常用尺寸有:3.5寸、4.7寸、5.0寸、5.5寸、6.0寸等 备注:1英寸(inch)2.54厘米&…...
光伏行业内卷到什么程度了?
现在每个行业都在内卷,光伏行业也一样在内卷中,但是光伏行业的内卷体现在多个方面,下面给举例。 一、产能竞争激烈: 产能扩张迅速:过去几年,大量资本涌入光伏行业,企业纷纷扩产。例如…...
C# 通俗易懂的介绍基础知识(七)——栈Stack(从日常生活开始讲解)
目录 一、前言 二、栈是排列方式 三、栈的单词 四、程序中的栈 五、栈的方法 1.声明并初始化栈 2.往栈里放东西(学名:入栈) 3.从栈往外拿东西 (学名:出栈) 4.清空栈 5.遍历 Stack 6.获取Stack的长…...
学习threejs,使用第一视角控制器FirstPersonControls控制相机
👨⚕️ 主页: gis分享者 👨⚕️ 感谢各位大佬 点赞👍 收藏⭐ 留言📝 加关注✅! 👨⚕️ 收录于专栏:threejs gis工程师 文章目录 一、🍀前言1.1 ☘️第一视角控制器FirstPerson…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...
Spring AOP代理对象生成原理
代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】,这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...
在ubuntu等linux系统上申请https证书
使用 Certbot 自动申请 安装 Certbot Certbot 是 Let’s Encrypt 官方推荐的自动化工具,支持多种操作系统和服务器环境。 在 Ubuntu/Debian 上: sudo apt update sudo apt install certbot申请证书 纯手动方式(不自动配置)&…...
Oracle 19c RAC集群ADG搭建
1、将主库的pfile和passwdfile发送到备库 #主库一节点操作 scp -P1234 /tmp/pfile2025.ora bak_ip:/home/oracle sco -P1234 /oracle/app/oracle/product/19.0.0/db/dbs/orapw$ORACLE_SID bak_ip:/oracle/app/oracle/product/19.0.0/db/dbs 2、备库修改参数文件成standby相关…...
Linux Docker的简介
参考资料 30分钟Docker入门教程 ◀ 本篇博客所有图片皆来自于该视频截图阮一峰 - Docker 入门教程 目录 一. 环境配置时可能会遇到的问题二. 什么是Docker三. 虚拟机 与 Docker 的区别3.1 虚拟机3.2 Docker 四. Docker的基本架构五. Dockerfile 一. 环境配置时可能会遇到的问题…...
PostgreSQL 的扩展pg_prewarm
PostgreSQL 的扩展pg_prewarm pg_prewarm 是 PostgreSQL 提供的一个实用扩展,用于将数据预先加载到共享缓冲区或操作系统缓存中,从而提升查询性能。 一、扩展概述 核心功能 手动预热:将指定的表或索引数据加载到内存自动预热:…...
