Leetcode面试经典150题-39.组合总数进阶:40.组合总和II
本题是扩展题,真实考过,看这个题之前先看一下39题
Leetcode面试经典150题-39.组合总数-CSDN博客
给定一个候选人编号的集合 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
其他的就不多说了,上代码,看不懂的请留言或者私信,收到第一时间解答
class Solution {/**这个题目对比第39题难度极大吧我觉得,这哪是中等难度,百分百的hard难度这个题对比39题的不同是每个位置的数只能使用一次,但是有可能有的位置的数是重复的,而重复的集合也应该被考虑这里我的解题思路是既然有重复的数,那就过滤出一个数组放数,另外一个数组放这个数出现的频率来试试这个解法*/public List<List<Integer>> combinationSum2(int[] candidates, int target) {/**先统计词频 */Map<Integer,Integer> map = new HashMap<>();for(int num : candidates) {map.put(num, map.getOrDefault(num, 0) + 1);}/**统计完词频之后把原来的数组分为两个数组,这里我想先排序,所以这里先统计出数字数组,稍后再统计词频数组 */int[] nums = new int[map.keySet().size()];int curIndex = 0;for(int num : map.keySet()) {nums[curIndex ++] = num;}/**排个序用于剪枝*/Arrays.sort(nums);/**统计词频数组 */int[] counts = new int[nums.length];for(int i = 0; i < nums.length; i++) {counts[i] = map.get(nums[i]);}return process(nums, counts, 0, target);}public List<List<Integer>> process(int[] nums, int[] counts, int curIndex, int targetLeft) {List<List<Integer>> ans = new ArrayList<>();if(targetLeft == 0) {ans.add(new ArrayList<>());return ans;}/**如果targetLeft不为0,但是我们没有数了,失败,返回空集合 */if(curIndex == nums.length) {return ans;}/**我们是按照从小到大排序的数组,如果targetLeft已经比当前数小了也没必要继续尝试了 */if(targetLeft < nums[curIndex]) {return ans;}/**其他情况正常尝试,当前数可以尝试Math.min(count[curIndex], targetLeft/nums[curIndex])次*/for(int i = 0; i <= Math.min(counts[curIndex], targetLeft/nums[curIndex]); i++) {List<List<Integer>> next = process(nums, counts, curIndex + 1, targetLeft - i * nums[curIndex]);for(List<Integer> list : next) {/**当前数加了多少个,就加入多少个到next中的集合中,因为确实是使用了这么多个 */for(int num = 0; num < i; num ++) {list.add(nums[curIndex]);}/**加入到当前数的集合 */ans.add(list);}}return ans;}
}

相关文章:
Leetcode面试经典150题-39.组合总数进阶:40.组合总和II
本题是扩展题,真实考过,看这个题之前先看一下39题 Leetcode面试经典150题-39.组合总数-CSDN博客 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数…...
ProcessOn为什么导出有水印!!!(利用SVG转PNG)
processon-svg2png ProcessOn 一个非常好用的思维导图网站,但是为什么导出有水印!!!。 功能 支持按钮拖拽支持将流程图svg 转成 png下载支持修改自定义文字下载svg(开发中) 安装/使用方法 安装并使用…...
插入、更新与删除MySQL记录
在现代应用开发中,数据库操作是非常重要的一环。作为程序员,熟练掌握数据库的增删改功能,能够更有效地管理数据并提高开发效率。 本课程将围绕插入、更新与删除记录这三个操作展开,涵盖SQL中的常见语句:INSERT INTO、UPDATE 和 DELETE,并结合实际应用中的常见问题讨论如…...
【ARM】armv8的虚拟化深度解读
Type-1 hypervisor Type-1虚拟化也叫做Bare metal, standalone, Type1 Type2 hypervisor Type-2虚拟化也叫做hosted, Type-2 VM和vCPU(虚拟机和虚拟cpu) 在一个VM(虚拟机)中有多个vCPU,多个vCPU可能属于同一个Vritual Processor。 EL2…...
9/24作业
1. 分文件编译 分什么要分文件编译? 防止主文件过大,不好修改,简化编译流程 1) 分那些文件 头文件:所有需要提前导入的库文件,函数声明 功能函数:所有功能函数的定义 主函数:main函数&…...
Leetcode 106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7], postorder [9,15,7,20,3] 输出:[3…...
针对考研的C语言学习(定制化快速掌握重点1)
1.printf函数的几个要点 printf函数中所有的输出都是右对齐的,除非在%后面添加负号,则表示左对齐 #include<stdio.h> int main() {int num 10;int nums 100;float f 1000.2333333333;printf("%3d\n", nums);//%3d表示输出的总宽度至…...
【大数据入门 | Hive】DDL数据定义语言(数据库DataBase)
1. 数据库(DataBase) 1.1 创建数据库 语法: CREATE DATABASE [IF NOT EXISTS] database_name [COMMENT database_comment] [LOCATION hdfs_path] [WITH DBPROPERTIES (property_nameproperty_value, ...)]; 案例: (1)创建一个…...
CNVD漏洞和证书挖掘经验总结
前言 本篇文章主要是分享一下本人挖掘CVND漏洞碰到的一些问题,根据过往成功归档的漏洞和未归档的漏洞总结出的经验,也确实给审核的大佬们添了很多麻烦(主要真的没人教一下,闷着头尝试犯了好很多错误,希望各位以后交一个…...
阿里rtc旁路推流TypeScript版NODE运行
阿里云音视频服务云端录制typescript版本; 编译后可以使用 node index.js运行 package.json 版本 // npm install --save alicloud/rtc201801112.3.0 "alicloud/rtc20180111": "^2.3.0",引入 import Client, { StartCloudRecordRequest, StopCloudRecord…...
计算机书籍分享
0.简介 数据库系统概念、深入理解计算机系统、领域驱动设计、Linux高性能服务器编程 高清版本pdf 1.链接 数据库系统概念: 链接: https://pan.baidu.com/s/17zz7QFevV2Eni9qHJyLEGA 提取码: wfrx 深入理解计算机系统 链接: https://pan.baidu.com/s/19yiJG8GqHJR…...
处理ASAM-MDF格式的开源python库asammdf
asammdf是一个强大的Python库,专为处理ASAM(Association for Standardization of Automation and Measuring Systems)MDF(Measurement Data Format)文件而设计。MDF是一种用于存储测量和诊断数据的标准格式,…...
物业管理小程序开发
物业小程序的开发是一个综合性的项目,旨在提升物业管理效率和增强业主的服务体验。以下是关于物业小程序开发的一些关键方面: 一、需求分析 目标用户:识别主要用户群体,包括业主、租户、物业管理人员等。 功能需求: 物…...
【Vue】Pinia
系列文章目录 第八章 Pinia 文章目录 系列文章目录前言一、安装和配置:二、基本使用三、一个更真实的例子 前言 Pinia是Vue.js应用程序的状态管理库。它提供了一种简单,轻量级的解决方案,用于在Vue应用程序中管理和维护状态。Pinia库的特点…...
帕金森病患者的生命长度:科学管理与乐观心态是关键
在快节奏的现代生活中,健康成为了我们最宝贵的财富之一。然而,当“帕金森病”这个名词悄然进入我们的视野时,不少人心中难免会涌起一丝不安与担忧。帕金森病,作为一种常见的神经系统退行性疾病,确实给患者的日常生活带…...
详解Linux中cat命令
在 Linux 命令的世界中,cat 命令就像是一位多才多艺的艺术家,它能够将文本文件的美妙旋律编织在一起,或者单独演奏它们的每一个音符。下面,让我们以一种充满情感的方式,用 Markdown 格式来探索 cat 命令的多种用途。 …...
Mysql高级篇(中)—— SQL优化之查询截取分析
SQL优化之查询截取分析 一、慢查询日志(1)简述(2)如何开启(3)慢查询日志分析工具介绍(了解)(4)官方工具 mysqldumpslow简述如何使用 二、SHOW PROCESSLIST三、(了解&…...
企业如何制作一个官方网站?
随着实体宣传的减弱,提高线上的宣传是新式的宣传方式,那么企业搭建网站成为线上宣传的重要途径。企业如何去搭建网站呢?如何拥有一个专业的网站来展示企业文化和企业销售产品?今天我给大家带来干货:如何一步步构建自己…...
游戏开发2025年最新版——八股文面试题(unity,虚幻,cocos都适用)
1.静态合批与动态合批的原理是什么?有什么限制条件?为什么?对CPU和GPU产生的影响分别是什么? 原理:Unity运行时可以将一些物体进行合并,从而用一个描绘调用来渲染他们,就是一个drawcall批次。 限…...
如何查看线程
1、首先找到我们的电脑安装jdk的位置,这里给大家展示一下博主本人的电脑jdk路径下的jconsole位置。 2、 ok,那么找到这个jconsole程序我们直接双击打开就可以查看我们电脑的本地进程: jconsole 这里能够罗列出你系统上的 java 进程࿰…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
