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 进程࿰…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
