【状态压缩 容斥原理 组合数学】100267. 单面值组合的第 K 小金额
本文涉及知识点
状态压缩 容斥原理 组合数学
二分查找算法合集
LeetCode100267. 单面值组合的第 K 小金额
给你一个整数数组 coins 表示不同面额的硬币,另给你一个整数 k 。
你有无限量的每种面额的硬币。但是,你 不能 组合使用不同面额的硬币。
返回使用这些硬币能制造的 第 kth 小 金额。
示例 1:
输入: coins = [3,6,9], k = 3
输出: 9
解释:给定的硬币可以制造以下金额:
3元硬币产生3的倍数:3, 6, 9, 12, 15等。
6元硬币产生6的倍数:6, 12, 18, 24等。
9元硬币产生9的倍数:9, 18, 27, 36等。
所有硬币合起来可以产生:3, 6, 9, 12, 15等。
示例 2:
输入:coins = [5,2], k = 7
输出:12
解释:给定的硬币可以制造以下金额:
5元硬币产生5的倍数:5, 10, 15, 20等。
2元硬币产生2的倍数:2, 4, 6, 8, 10, 12等。
所有硬币合起来可以产生:2, 4, 5, 6, 8, 10, 12, 14, 15等。
提示:
1 <= coins.length <= 15
1 <= coins[i] <= 25
1 <= k <= 2 * 109
coins 包含两两不同的整数。
容斥原理:小于等于mid的金额数量
如果不考虑重复 ∑ i : n − 1 m i d / c o i n s [ i ] \sum_{i:}^{n-1}mid/coins[i] ∑i:n−1mid/coins[i] 考虑重复则很复杂。
以mid 12为例子,f(x) 表示用面值x的金币能过组成小于等于mid的金额数量:
a , coins = {2,3}
面值2的倍数:2,4,6,8,10,12 f(2)=6,其中重复2个。
面值3的倍数:3,6,9,12 f(3) = 4 ,重复2个。
总数量:f(2)+f(3)-f(6) = 6-4-2=8。6是最小公倍数LCM
b,coins = {2,3,5}
面值5的倍数:5,10 = 2 ,其中重复一个。
新增加的数:
f(5) - f(LCM(5,2))-f(LCM(3,5))
如果一个数 同时10和15的倍数,则减重复了,要加回来:
及:
f(5) - f(LCM(5,2))-f(LCM(3,5)) + f(LCM(2,3,5))
注意: C++有系统函数 lcm
二分
令 cnt(mid) 是小于等于mid的金额数。如果cnt(mid) < k,则mid一定不是解。我们要求第个一 cnt(mid)>=k 。 故用左开右闭空间。
单调性证明
mid1 > mid2 ,如果cnt(mid1)>=k 成立,则cnt(mid2)>=k 成立, 因为(mid1,mid2]中的数,要么让返回值+1,要么让返回值不变。同理: cnt(mid2)>=k 不成立,则cnt(mid1)>=k,也不成立。
代码
核心代码
class Solution {
public:long long findKthSmallest(vector<int>& coins, int k) {m_coins = coins; long long left = 0, right = 1'000'000'000'000LL;while (right - left > 1) {const auto mid = left + (right - left) / 2;if (Count(mid) >= k) {right = mid;}else{left = mid;}}return right;}long long Count(long long mid) {vector<vector<long long>> vMask; long long llRet = 0;for (const auto& n : m_coins) {vector<vector<long long>> vMask2;for (const auto& v : vMask) {vector<long long> v2;for (const auto& llMask : v) {const long long tmp = lcm(llMask, n);if (tmp <= mid) {v2.emplace_back(tmp);} }vMask2.emplace_back(v2);}vMask2.emplace_back();vMask2.back().emplace_back(n);for (int i = 1; i < vMask2.size(); i++) {vMask2[i].insert(vMask2[i].end(), vMask[i - 1].begin(), vMask[i - 1].end());} vMask2.swap(vMask);}for (int i = 0; i < vMask.size(); i++) {for (const auto& iMask : vMask[vMask.size() - 1 - i]) {llRet += (1 & i) ? -mid / iMask : mid / iMask;}}return llRet;}vector<int> m_coins;
};
测试用例
int main()
{vector<int> nums = { 3,6,9 };int k;{Solution sln;nums = { 2,3,5,7,11,13,17,19,23,25,20,18 }, k = 1000000000;auto res = sln.findKthSmallest(nums, k);Assert(9LL, res);}{Solution sln;nums = { 3,6,9 }, k = 3;auto res = sln.findKthSmallest(nums, k);Assert(9LL, res);}}
用状态压缩优化代码量(通过前置状态计算后置状态)
class Solution {
public:long long findKthSmallest(vector<int>& coins, int k) { const int iMaskCount = 1 << coins.size();vector<int> v01(iMaskCount),vLCM(iMaskCount,-1);vector<int> vMask[2];//vMask[0] 记录 偶数个数的最小公倍数,vMask[1]记录奇数个数的最小公倍数v01[0] = 0;vLCM[0] = 1;for (int iMask = 0; iMask < iMaskCount; iMask++) {for (int j = 0; j < coins.size(); j++) {if (!((1 << j) & iMask)) {const int iNewMask = (1 << j) | iMask;if (-1 != vLCM[iNewMask]) { continue; }v01[iNewMask] = v01[iMask] ^ 1;vLCM[iNewMask] = lcm(vLCM[iMask], coins[j]);vMask[v01[iNewMask]].emplace_back(vLCM[iNewMask]); }}}long long left = 0, right = 1'000'000'000'000LL;while (right - left > 1) {const auto mid = left + (right - left) / 2;long long cnt = 0;for (const auto& ll : vMask[0]) {cnt -= mid / ll;}for (const auto& ll : vMask[1]) {cnt += mid / ll;}if (cnt >= k) {right = mid;}else{left = mid;}}return right;}
};
用状态压缩优化代码量(计算后置状态)
class Solution {
public:long long findKthSmallest(vector<int>& coins, int k) { const int iMaskCount = 1 << coins.size(); vector<long long> vMask[2];//vMask[0] 记录 偶数个数的最小公倍数,vMask[1]记录奇数个数的最小公倍数vector<long long> v01(iMaskCount), vLCM(iMaskCount, -1);{ v01[0] = 0;vLCM[0] = 1;for (int i = 0; i < coins.size(); i++) {vLCM[1 << i] = coins[i];}for (int iNewMask = 1; iNewMask < iMaskCount; iNewMask++) {const int iMask = (iNewMask - 1) & iNewMask;v01[iNewMask] = v01[iMask] ^ 1;vLCM[iNewMask] = lcm(vLCM[iMask], vLCM[iNewMask - iMask]);vMask[v01[iNewMask]].emplace_back(vLCM[iNewMask]);}}long long left = 0, right = 1'000'000'000'000LL;while (right - left > 1) {const auto mid = left + (right - left) / 2;long long cnt = 0;for (const auto& ll : vMask[0]) {cnt -= mid / ll;}for (const auto& ll : vMask[1]) {cnt += mid / ll;}if (cnt >= k) {right = mid;}else{left = mid;}}return right;}
};
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话 |
---|
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。
相关文章:

【状态压缩 容斥原理 组合数学】100267. 单面值组合的第 K 小金额
本文涉及知识点 状态压缩 容斥原理 组合数学 二分查找算法合集 LeetCode100267. 单面值组合的第 K 小金额 给你一个整数数组 coins 表示不同面额的硬币,另给你一个整数 k 。 你有无限量的每种面额的硬币。但是,你 不能 组合使用不同面额的硬币。 返回…...

.net框架和c#程序设计第三次测试
目录 一、测试要求 二、实现效果 三、实现代码 一、测试要求 二、实现效果 数据库中的内容: 使用数据库中的账号登录: 若不是数据库中的内容: 三、实现代码 login.aspx文件: <% Page Language"C#" AutoEventW…...

架构师系列-搜索引擎ElasticSearch(五)- 索引设计
索引创建后,要非常谨慎,创建不好后面会出现各种问题。 索引设计的重要性 索引创建后,索引分片只能通过_split和_shrink 接口对其进行成倍的增加和缩减。 ES的数据是通过_routing分配到各个分片上的,所以本质上不推荐区改变索引的…...
kafka ----修改log4j、jmx、jvm参数等
1、修改log4j 日志路径 在kafka-run-class.sh文件中修改如下配置,将 LOG_DIR变量指定为自己想要存储的路径 # Log directory to use if [ "x$LOG_DIR" "x" ]; thenLOG_DIR"$base_dir/logs" fi2、修改jmx参数 在kafka-run-class.s…...

Python 全栈 Web 应用模板:成熟架构,急速开发 | 开源日报 No.223
tiangolo/full-stack-fastapi-template Stars: 15.6k License: MIT full-stack-fastapi-template 是一个现代化的全栈 Web 应用模板。 使用 FastAPI 构建 Python 后端 API。使用 SQLModel 进行 Python SQL 数据库交互(ORM)。Pydantic 用于数据验证和设…...

STM32之DHT11温湿度传感器
目录 一 DHT11温湿度传感器简介 1.1 传感器特点 1.2 传感器特性 1.3 传感器引脚说明 二 测量原理及方法 2.1 典型应用电路 2.2 单线制串行简介 2.2.1 串行接口 (单线双向) 2.2.2 数据示例 2.3 通信时序 三 单片机简介 3.1 STM32F103C8T6最小系统板 四 接线说明 …...
paddle ocr
paddle安装教程,git clone xxxgit https://blog.csdn.net/Castlehe/article/details/117356343 只有paddle 1.x 的教程:https://github.com/PaddlePaddle/PaddleOCR/blob/static/doc/doc_en/quickstart_en.md 报错是因为安装的是paddle 2.x而教程只给了…...

Xcode 15.0 新 #Preview 预览让 SwiftUI 界面调试更加悠然自得
概览 从 Xcode 15 开始,苹果推出了新的 #Preview 宏预览机制,它无论从语法还是灵活性上都远远超过之前的预览方式。#Preview 不但可以实时预览 SwiftUI 视图,而且对 UIKit 的界面预览也是信手拈来。 想学习新 #Preview 预览的一些超实用调试…...

【VS2019】x64 Native Tools Command Prompt for Vs 2019使用conda命令进入环境
【VS2019】x64 Native Tools Command Prompt for Vs 2019使用conda命令进入环境 安装完VS2019后,打开终端x64 Native Tools Command Prompt for Vs 2019,直接运行conda会出现‘conda’ 不是内部或外部命令,也不是可运行的程序 原因分析&am…...

网络篇09 | 运输层 udp
网络篇09 | 运输层 udp 01 简介UDP 是面向报文的 02 报文协议 01 简介 UDP 只在 IP 的数据报服务之上增加了一些功能:复用和分用、差错检测 UDP 的主要特点:无连接。发送数据之前不需要建立连接。 使用尽最大努力交付。即不保证可靠交付。 面向报文。…...

vim相关指令
vim的各种模式及其转换关系图 vim 默认处于命令模式!!! 模式之间转换的指令 除【命令模式】之外,其它模式要切换到【命令模式】,只需要无脑 ESC 即可!!! [ 命令模式 ] 切换至 [ 插…...

STM32常见调试工具介绍
STM32的常见调试工具主要包括ST-LINK、USB转TTL、USB转485以及USB转CAN。这些工具在嵌入式系统开发、调试以及通信中发挥着重要的作用。 1.ST-LINK: ST-LINK是STMicroelectronics公司专为其STM32系列微控制器开发的调试和编程工具。既能仿真也能将编译好的程序下载…...

简历上写熟悉Linux下常用命令?直接寄
大家写简历技术栈时,都觉得越多越好,其中一条,熟悉Linux下常用命令?其实开发中Linux不是必备考点,除了运维,真正用的多的仅仅cd ls mkdir等,但当面试官问到上面命令时,是不是就傻眼了…...
【设计模式】4、prototype 原型模式
四、prototype 原型模式 https://refactoringguru.cn/design-patterns/prototype 如果希望 复制对象, 可使用 “prototype 模式” 如果 “待复制的对象” 是 interface 而不是 class, 或者如果 class 有 private 变量时. 无法知道 "待复制的对象"的细节, 则需要其…...

ES6 关于Class类的继承 extends(2024-04-10)
1、简介 类Class 可以通过extends关键字实现继承,让子类继承父类的属性和方法。extends 的写法比 ES5 的原型链继承,要清晰和方便很多。 class Foo {constructor(x, y) {this.x x;this.y y;console.log(父类构造函数)}toString() {return ( this.x …...

边缘计算【智能+安全检测】系列教程--使用OpenCV+GStreamer实现真正的硬解码,完全消除马赛克
通过现有博客的GST_URL = "rtspsrc location=rtsp://admin:abcd1234@192.168.1.64:554/h264/ch01/main/av_stream latency=150 ! rtph264depay ! avdec_h264 ! videorate ! videoconvert ! appsink sync=false" GStreamer的解码方式解码,大多情况应该存在上图马赛克…...
Anaconda在Ubuntu下的安装与简单使用
一、参考资料 ubuntu16.04下安装&配置anacondatensorflow新手教程 二、安装Anaconda 下载 Miniconda镜像1 or Miniconda镜像2 # 下载 wget Miniconda3-py39_4.10.3-Linux-x86_64.sh# 安装 bash Miniconda3-py39_4.10.3-Linux-x86_64.sh一路yes 安装过程中的选项 Do you …...

网络编程【InetAddress , TCP 、UDP 、HTTP 案例】
day38上 网络编程 InetAddress 理解:表示主机类 一个域名 对应 多个IP地址 public static void main(String[] args) throws UnknownHostException {//获取本机的IP地址 // InetAddress localHost InetAddress.getLocalHost(); // System.out.println(localHos…...

软考中级工程师网络技术第二节网络体系结构
OSPF将路由器连接的物理网络划分为以下4种类型,以太网属于(25),X.25分组交换网属于(非广播多址网络NBMA)。 A 点对点网络 B 广播多址网络 C 点到多点网络 D 非广播多址网络 试题答案 正确答案: …...

Mac 软件清单
~自留备用~ Macbook用了几年之后, 512G的内置硬盘有些紧张了, 这几天总是提示空间不足, 就重装了下系统, 重装之后竟然不记得有些软件的名字和下载链接, 特此记录 Office 办公套件 直接从微软官网下载Office 安装包https://officecdnmac.microsoft.com/pr/C1297A47-86C4-4C1F…...

Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...

Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...

stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...
土建施工员考试:建筑施工技术重点知识有哪些?
《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目,核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容,附学习方向和应试技巧: 一、施工组织与进度管理 核心目标: 规…...

在Zenodo下载文件 用到googlecolab googledrive
方法:Figshare/Zenodo上的数据/文件下载不下来?尝试利用Google Colab :https://zhuanlan.zhihu.com/p/1898503078782674027 参考: 通过Colab&谷歌云下载Figshare数据,超级实用!!࿰…...
OpenGL-什么是软OpenGL/软渲染/软光栅?
软OpenGL(Software OpenGL)或者软渲染指完全通过CPU模拟实现的OpenGL渲染方式(包括几何处理、光栅化、着色等),不依赖GPU硬件加速。这种模式通常性能较低,但兼容性极强,常用于不支持硬件加速…...