【Leetcode 每日一题】40. 组合总和 II
问题背景
给定一个候选人编号的集合 c a n d i d a t e s candidates candidates 和一个目标数 t a r g e t target target,找出 c a n d i d a t e s candidates candidates 中所有可以使数字和为 t a r g e t target target 的组合。
c a n d i d a t e s candidates candidates 中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
数据约束
- 1 ≤ c a n d i d a t e s . l e n g t h ≤ 100 1 \le candidates.length \le 100 1≤candidates.length≤100
- 1 ≤ c a n d i d a t e s [ i ] ≤ 50 1 \le candidates[i] \le 50 1≤candidates[i]≤50
- 1 ≤ t a r g e t ≤ 30 1 \le target \le 30 1≤target≤30
解题过程
算是回溯的例题,由于结果不能重复,要先将数组进行排序,方便在过程中跳已经处理过的相等元素。
具体实现
递归
class Solution {public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();dfs(0, target, candidates, res, path);return res;}private void dfs(int i, int target, int[] candidates, List<List<Integer>> res, List<Integer> path) {if(target == 0) {res.add(new ArrayList(path));return;}if(i == candidates.length) {return;}int cur = candidates[i];if(target < cur) {return;}path.add(cur);dfs(i + 1, target - cur, candidates, res, path);path.remove(path.size() - 1);i++;while(i < candidates.length && candidates[i] == cur) {i++;}dfs(i, target, candidates, res, path);}
}
递推
class Solution {public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();dfs(0, target, candidates, res, path);return res;}private void dfs(int i, int target, int[] candidates, List<List<Integer>> res, List<Integer> path) {if(target == 0) {res.add(new ArrayList<>(path));return;}for (int j = i; j < candidates.length && candidates[j] <= target; j++) {if(j > i && candidates[j] == candidates[j - 1]) {continue;}path.add(candidates[j]);dfs(j + 1, target - candidates[j], candidates, res, path);path.remove(path.size() - 1);}}
}
相关文章:
【Leetcode 每日一题】40. 组合总和 II
问题背景 给定一个候选人编号的集合 c a n d i d a t e s candidates candidates 和一个目标数 t a r g e t target target,找出 c a n d i d a t e s candidates candidates 中所有可以使数字和为 t a r g e t target target 的组合。 c a n d i d a t e s c…...
python 变量范围的定义与用法
文章目录 1. 局部变量(Local Scope)示例: 2. 嵌套函数变量(Enclosing Scope)示例:说明: 3. 全局变量(Global Scope)示例:说明: 4. 内置变量&#…...

TRTC实时对话式AI解决方案,助力人机语音交互极致体验
近年来,AI热度持续攀升,无论是融资规模还是用户热度都大幅增长。2023 年,中国 AI 行业融资规模达2631亿人民币,较2022年上升51%;2024年第二季度,全球 AI 初创企业融资规模为 240 亿美金,较第一季…...

dev c++ ‘unordered_set‘ does not name a type
参考:https://blog.csdn.net/Zaczc/article/details/142531525 启用C11标准步骤 工具->编译选项 勾选编译时加入以下命令 在空白处添加:-stdc11 单击确定,启用成功...

算法每日双题精讲 —— 二分查找(寻找旋转排序数组中的最小值,点名)
🌟快来参与讨论💬,点赞👍、收藏⭐、分享📤,共创活力社区。 🌟 别再犹豫了!快来订阅我们的算法每日双题精讲专栏,一起踏上算法学习的精彩之旅吧💪 在算法的…...

three.js+WebGL踩坑经验合集(4.2):为什么不在可视范围内的3D点投影到2D的结果这么不可靠
上一篇,笔者留下了一个问题,three.js内置的THREE.Vector3.project方法算出来的结果对于超出屏幕可见范围的点来说错得相当离谱。 three.jsWebGL踩坑经验合集(4.1):THREE.Line2的射线检测问题(注意本篇说的是Line2,同样也不是阈值…...
Kafka运维宝典 (二)- kafka 查看kafka的运行状态、broker.id不一致导致启动失败问题、topic消息积压量告警监控脚本
Kafka运维宝典 (二) 文章目录 Kafka运维宝典 (二)一、kafka broker.id冲突问题1. broker.id 冲突的影响2. 如何发现 broker.id 冲突3. 解决 broker.id 冲突的方法4. broker.id 配置管理5. 集群启动后确认 broker.id 唯一性6. brok…...

全球AI模型百科全书,亚马逊云科技Bedrock上的100多款AI模型
今天小李哥给大家介绍的是亚马逊云科技上的AI模型管理平台Amazon Bedrock上的Marketplace,这是亚马逊云科技在今年re:Invent发布的一个全新功能,将亚马逊的电商基因带到了其云计算平台,让我们能够通过Amazon Bedrock访问100多种流行、新兴和专…...

微信小程序中常见的 跳转方式 及其特点的表格总结(wx.navigateTo 适合需要返回上一页的场景)
文章目录 详细说明总结wx.navigateTo 的特点为什么 wx.navigateTo 最常用?其他跳转方式的使用频率总结 以下是微信小程序中常见的跳转方式及其特点的表格总结: 跳转方式API 方法特点适用场景wx.navigateTowx.navigateTo({ url: 路径 })保留当前页面&…...
【Elasticsearch】index:false
在 Elasticsearch 中,index 参数用于控制是否对某个字段建立索引。当设置 index: false 时,意味着该字段不会被编入倒排索引中,因此不能直接用于搜索查询。然而,这并不意味着该字段完全不可访问或没有其他用途。以下是关于 index:…...

新版IDEA创建数据库表
这是老版本的IDEA创建数据库表,下面可以自己勾选Not null(非空),Auto inc(自增长),Unique(唯一标识)和Primary key(主键) 这是新版的IDEA创建数据库表,Not null和Auto inc可以看得到,但Unique和Primary key…...

输入带空格的字符串,求单词个数
输入带空格的字符串,求单词个数 __ueooe_eui_sjje__ ---->3syue__jdjd____die_ ---->3shuue__dju__kk ---->3 #include <stdio.h> #include <string.h>// 自定义函数来判断字符是否为空白字符 int isSpace(char c) {return c || c \t || …...

C语言程序设计十大排序—希尔排序
文章目录 1.概念✅2.希尔排序🎈3.代码实现✅3.1 直接写✨3.2 函数✨ 4.总结✅ 1.概念✅ 排序是数据处理的基本操作之一,每次算法竞赛都很多题目用到排序。排序算法是计算机科学中基础且常用的算法,排序后的数据更易于处理和查找。在计算机发展…...

Excel制作合同到期自动提醒!
大家好,我是小鱼。 今天分享一下如何利用Excel制作合同到期提醒表,实现Excel表格自动计算合同到期日和天数,根据合同状态和到期天数自动填充颜色提醒,超实用。先看一下效果,已经到期的合同会自动被填充为红色…...

“AI质量评估系统:智能守护,让品质无忧
嘿,各位小伙伴们!今天咱们来聊聊一个在现代社会中越来越重要的角色——AI质量评估系统。你知道吗?在这个快速发展的时代,产品质量已经成为企业生存和发展的关键。而AI质量评估系统,就像是我们的智能守护神,…...

爬虫基础之爬取某基金网站+数据分析
声明: 本案例仅供学习参考使用,任何不法的活动均与本作者无关 网站:天天基金网(1234567.com.cn) --首批独立基金销售机构-- 东方财富网旗下基金平台! 本案例所需要的模块: 1.requests 2.re(内置) 3.pandas 4.pyecharts 其他均需要 pip install 模块名 爬取步骤: …...

使用 Aryn DocPrep、DocParse 和 Elasticsearch 向量数据库实现高质量 RAG
作者:来自 Elastic Hemant Malik 及 Jonathan Fritz 组织依靠自然语言查询从非结构化数据中获取见解,但要获得高质量的答案,首先要进行有效的数据准备。Aryn DocParse 和 DocPrep通过将复杂文档转换为结构化 JSON 或 markdown 来简化此过程&a…...

Couchbase UI: Server
在 Couchbase UI 中的 Server(服务器)标签页主要用于管理和监控集群中的各个节点。以下是 Server 标签页的主要内容和功能介绍: 1. 节点列表 显示集群中所有节点的列表,每个节点的详细信息包括: 节点地址࿱…...

Web3.0时代的挑战与机遇:以开源2+1链动模式AI智能名片S2B2C商城小程序为例的深度探讨
摘要:Web3.0作为互联网的下一代形态,承载着去中心化、开放性和安全性的重要愿景。然而,其高门槛、用户体验差等问题阻碍了Web3.0的主流化进程。本文旨在深入探讨Web3.0面临的挑战,并提出利用开源21链动模式、AI智能名片及S2B2C商城…...

langchain基础(一)
模型又可分为语言模型(擅长文本补全,输入和输出都是字符串)和聊天模型(擅长对话,输入时消息列表,输出是一个消息)两大类。 以调用openai的聊天模型为例,先安装langchain_openai库 1…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...

Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...