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

【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 1candidates.length100
  • 1 ≤ c a n d i d a t e s [ i ] ≤ 50 1 \le candidates[i] \le 50 1candidates[i]50
  • 1 ≤ t a r g e t ≤ 30 1 \le target \le 30 1target30

解题过程

算是回溯的例题,由于结果不能重复,要先将数组进行排序,方便在过程中跳已经处理过的相等元素。

具体实现

递归

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&#xff0c;找出 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. 局部变量&#xff08;Local Scope&#xff09;示例&#xff1a; 2. 嵌套函数变量&#xff08;Enclosing Scope&#xff09;示例&#xff1a;说明&#xff1a; 3. 全局变量&#xff08;Global Scope&#xff09;示例&#xff1a;说明&#xff1a; 4. 内置变量&#…...

TRTC实时对话式AI解决方案,助力人机语音交互极致体验

近年来&#xff0c;AI热度持续攀升&#xff0c;无论是融资规模还是用户热度都大幅增长。2023 年&#xff0c;中国 AI 行业融资规模达2631亿人民币&#xff0c;较2022年上升51%&#xff1b;2024年第二季度&#xff0c;全球 AI 初创企业融资规模为 240 亿美金&#xff0c;较第一季…...

dev c++ ‘unordered_set‘ does not name a type

参考:https://blog.csdn.net/Zaczc/article/details/142531525 启用C11标准步骤 工具->编译选项 勾选编译时加入以下命令 在空白处添加:-stdc11 单击确定&#xff0c;启用成功...

算法每日双题精讲 —— 二分查找(寻找旋转排序数组中的最小值,点名)

&#x1f31f;快来参与讨论&#x1f4ac;&#xff0c;点赞&#x1f44d;、收藏⭐、分享&#x1f4e4;&#xff0c;共创活力社区。 &#x1f31f; 别再犹豫了&#xff01;快来订阅我们的算法每日双题精讲专栏&#xff0c;一起踏上算法学习的精彩之旅吧&#x1f4aa; 在算法的…...

three.js+WebGL踩坑经验合集(4.2):为什么不在可视范围内的3D点投影到2D的结果这么不可靠

上一篇&#xff0c;笔者留下了一个问题&#xff0c;three.js内置的THREE.Vector3.project方法算出来的结果对于超出屏幕可见范围的点来说错得相当离谱。 three.jsWebGL踩坑经验合集(4.1):THREE.Line2的射线检测问题&#xff08;注意本篇说的是Line2&#xff0c;同样也不是阈值…...

Kafka运维宝典 (二)- kafka 查看kafka的运行状态、broker.id不一致导致启动失败问题、topic消息积压量告警监控脚本

Kafka运维宝典 &#xff08;二&#xff09; 文章目录 Kafka运维宝典 &#xff08;二&#xff09;一、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&#xff0c;这是亚马逊云科技在今年re:Invent发布的一个全新功能&#xff0c;将亚马逊的电商基因带到了其云计算平台&#xff0c;让我们能够通过Amazon Bedrock访问100多种流行、新兴和专…...

微信小程序中常见的 跳转方式 及其特点的表格总结(wx.navigateTo 适合需要返回上一页的场景)

文章目录 详细说明总结wx.navigateTo 的特点为什么 wx.navigateTo 最常用&#xff1f;其他跳转方式的使用频率总结 以下是微信小程序中常见的跳转方式及其特点的表格总结&#xff1a; 跳转方式API 方法特点适用场景wx.navigateTowx.navigateTo({ url: 路径 })保留当前页面&…...

【Elasticsearch】index:false

在 Elasticsearch 中&#xff0c;index 参数用于控制是否对某个字段建立索引。当设置 index: false 时&#xff0c;意味着该字段不会被编入倒排索引中&#xff0c;因此不能直接用于搜索查询。然而&#xff0c;这并不意味着该字段完全不可访问或没有其他用途。以下是关于 index:…...

新版IDEA创建数据库表

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

输入带空格的字符串,求单词个数

输入带空格的字符串&#xff0c;求单词个数 __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.希尔排序&#x1f388;3.代码实现✅3.1 直接写✨3.2 函数✨ 4.总结✅ 1.概念✅ 排序是数据处理的基本操作之一&#xff0c;每次算法竞赛都很多题目用到排序。排序算法是计算机科学中基础且常用的算法&#xff0c;排序后的数据更易于处理和查找。在计算机发展…...

Excel制作合同到期自动提醒!

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

“AI质量评估系统:智能守护,让品质无忧

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

爬虫基础之爬取某基金网站+数据分析

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

使用 Aryn DocPrep、DocParse 和 Elasticsearch 向量数据库实现高质量 RAG

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

Couchbase UI: Server

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

Web3.0时代的挑战与机遇:以开源2+1链动模式AI智能名片S2B2C商城小程序为例的深度探讨

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

langchain基础(一)

模型又可分为语言模型&#xff08;擅长文本补全&#xff0c;输入和输出都是字符串&#xff09;和聊天模型&#xff08;擅长对话&#xff0c;输入时消息列表&#xff0c;输出是一个消息&#xff09;两大类。 以调用openai的聊天模型为例&#xff0c;先安装langchain_openai库 1…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

基于江科大stm32屏幕驱动,实现OLED多级菜单(动画效果),结构体链表实现(独创源码)

引言 在嵌入式系统中&#xff0c;用户界面的设计往往直接影响到用户体验。本文将以STM32微控制器和OLED显示屏为例&#xff0c;介绍如何实现一个多级菜单系统。该系统支持用户通过按键导航菜单&#xff0c;执行相应操作&#xff0c;并提供平滑的滚动动画效果。 本文设计了一个…...

Python环境安装与虚拟环境配置详解

本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南&#xff0c;适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者&#xff0c;都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...

Linux入门课的思维导图

耗时两周&#xff0c;终于把慕课网上的Linux的基础入门课实操、总结完了&#xff01; 第一次以Blog的形式做学习记录&#xff0c;过程很有意思&#xff0c;但也很耗时。 课程时长5h&#xff0c;涉及到很多专有名词&#xff0c;要去逐个查找&#xff0c;以前接触过的概念因为时…...