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 进程࿰…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
