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

【状态压缩 容斥原理 组合数学】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:n1mid/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 表示不同面额的硬币&#xff0c;另给你一个整数 k 。 你有无限量的每种面额的硬币。但是&#xff0c;你 不能 组合使用不同面额的硬币。 返回…...

.net框架和c#程序设计第三次测试

目录 一、测试要求 二、实现效果 三、实现代码 一、测试要求 二、实现效果 数据库中的内容&#xff1a; 使用数据库中的账号登录&#xff1a; 若不是数据库中的内容&#xff1a; 三、实现代码 login.aspx文件&#xff1a; <% Page Language"C#" AutoEventW…...

架构师系列-搜索引擎ElasticSearch(五)- 索引设计

索引创建后&#xff0c;要非常谨慎&#xff0c;创建不好后面会出现各种问题。 索引设计的重要性 索引创建后&#xff0c;索引分片只能通过_split和_shrink 接口对其进行成倍的增加和缩减。 ES的数据是通过_routing分配到各个分片上的&#xff0c;所以本质上不推荐区改变索引的…...

kafka ----修改log4j、jmx、jvm参数等

1、修改log4j 日志路径 在kafka-run-class.sh文件中修改如下配置&#xff0c;将 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 数据库交互&#xff08;ORM&#xff09;。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安装教程&#xff0c;git clone xxxgit https://blog.csdn.net/Castlehe/article/details/117356343 只有paddle 1.x 的教程&#xff1a;https://github.com/PaddlePaddle/PaddleOCR/blob/static/doc/doc_en/quickstart_en.md 报错是因为安装的是paddle 2.x而教程只给了…...

Xcode 15.0 新 #Preview 预览让 SwiftUI 界面调试更加悠然自得

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

【VS2019】x64 Native Tools Command Prompt for Vs 2019使用conda命令进入环境

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

网络篇09 | 运输层 udp

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

vim相关指令

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

STM32常见调试工具介绍

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

简历上写熟悉Linux下常用命令?直接寄

大家写简历技术栈时&#xff0c;都觉得越多越好&#xff0c;其中一条&#xff0c;熟悉Linux下常用命令&#xff1f;其实开发中Linux不是必备考点&#xff0c;除了运维&#xff0c;真正用的多的仅仅cd ls mkdir等&#xff0c;但当面试官问到上面命令时&#xff0c;是不是就傻眼了…...

【设计模式】4、prototype 原型模式

四、prototype 原型模式 https://refactoringguru.cn/design-patterns/prototype 如果希望 复制对象, 可使用 “prototype 模式” 如果 “待复制的对象” 是 interface 而不是 class, 或者如果 class 有 private 变量时. 无法知道 "待复制的对象"的细节, 则需要其…...

ES6 关于Class类的继承 extends(2024-04-10)

1、简介 类Class 可以通过extends关键字实现继承&#xff0c;让子类继承父类的属性和方法。extends 的写法比 ES5 的原型链继承&#xff0c;要清晰和方便很多。 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 理解&#xff1a;表示主机类 一个域名 对应 多个IP地址 public static void main(String[] args) throws UnknownHostException {//获取本机的IP地址 // InetAddress localHost InetAddress.getLocalHost(); // System.out.println(localHos…...

软考中级工程师网络技术第二节网络体系结构

OSPF将路由器连接的物理网络划分为以下4种类型&#xff0c;以太网属于&#xff08;25&#xff09;&#xff0c;X.25分组交换网属于&#xff08;非广播多址网络NBMA&#xff09;。 A 点对点网络 B 广播多址网络 C 点到多点网络 D 非广播多址网络 试题答案 正确答案&#xff1a; …...

Mac 软件清单

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

【Leetcode每日一题】 分治 - 颜色分类(难度⭐⭐)(57)

1. 题目解析 题目链接&#xff1a;75. 颜色分类 这个问题的理解其实相当简单&#xff0c;只需看一下示例&#xff0c;基本就能明白其含义了。 2.算法原理 算法思路解析 本算法采用三指针法&#xff0c;将数组划分为三个区域&#xff0c;分别用于存放值为0、1和2的元素。通过…...

微信登录功能-保姆级教学

目录 一、使用组件 二、登录功能 2.1 步骤 2.2 首先找到网页权限 复制demo 代码 这里我们需要修改两个参数 三、前端代码 3.1 api 里weiXinApi.ts 3.2 api里的 index.ts 3.3 pinia.ts 3.4 My.vue 四、后端代码 4.1 WeiXinController 4.2 Access_Token.Java 4.3 We…...

嵌入式MCU BootLoader开发配置详细笔记教程

目录 一、BootLoader基础 二、BootLoader原理及配置 三、BootLoader程序 bootloader.h bootloader.c 四、Application1 用户程序 application1.h application1.c 五、Application2 用户程序 application2.h 六、程序运行效果 七、工程文件Demo 一、BootLoader基础 …...

Unity 中消息提醒框

Tooltip 用于ui布局 using System.Collections; using System.Collections.Generic; using UnityEngine; using TMPro; using UnityEngine.UI;[ExecuteInEditMode()] // 可以在编辑模式下运行public class Tooltip : MonoBehaviour {public TMP_Text header; // 头部文本publi…...

好数(蓝桥杯)

文章目录 好数题目描述暴力方法一暴力方法二&#xff08;超时&#xff09; 好数 题目描述 【问题描述】 一个整数如果按从低位到高位的顺序&#xff0c;奇数位&#xff08;个位、百位、万位 &#xff09;上的数字是奇数&#xff0c;偶数位&#xff08;十位、千位、十万位 …...

自动化收集Unity版本更新日志

自动化收集Unity版本更新日志 &#x1f365;功能介绍&#x1f96a;食用手册填写配置开始搜集 &#x1f368;数据展示 &#x1f365;功能介绍 &#x1f4a1;获取指定年份中所有的Unity版本更新日志。 &#x1f4a1;根据指定字符串过滤。 &#x1f4a1;.收集后自动保存成markdow…...

【CSS】CSS水平居中方案

CSS水平居中方案 1. 行内元素水平居中 设置父元素的text-align:center .box {width: 300px;height: 300px;margin: 100px auto;text-align: center;background-color: pink; }2. 块级元素水平居中 当块级元素设置了明确的宽度数值时&#xff0c;可以使用margin: 0 auto 3.…...

SQL注入sqli_labs靶场第二题

解题思路与第一题相同 ?id1 and 11 和?id1 and 12进行测试如果11页面显示正常和原页面一样&#xff0c;并且12页面报错或者页面部分数据显示不正常&#xff0c;那么可以确定此处为数字型注入。 联合查询&#xff1a; 猜解列名数量&#xff1a;3 ?id1 order by 4 判断回显…...

基于机器学习的人脸发型推荐算法研究与应用实现

1.摘要 本文主要研究内容是开发一种发型推荐系统&#xff0c;旨在识别用户的面部形状&#xff0c;并根据此形状推荐最适合的发型。首先&#xff0c;收集具有各种面部形状的用户照片&#xff0c;并标记它们的脸型&#xff0c;如长形、圆形、椭圆形、心形或方形。接着构建一个面部…...

【服务器部署篇】Linux下Nginx的安装和配置

作者介绍&#xff1a;本人笔名姑苏老陈&#xff0c;从事JAVA开发工作十多年了&#xff0c;带过刚毕业的实习生&#xff0c;也带过技术团队。最近有个朋友的表弟&#xff0c;马上要大学毕业了&#xff0c;想从事JAVA开发工作&#xff0c;但不知道从何处入手。于是&#xff0c;产…...

张家港手机网站设计/百度账号登录中心

什么是广播风暴&#xff1f;那我们先来看下官方术语&#xff1a;广播风暴(broadcast storm)简单的讲是指当广播数据充斥网络无法处理&#xff0c;并占用大量网络带宽&#xff0c;导致正常业务不能运行&#xff0c;甚至彻底瘫痪&#xff0c;这就发生了“广播风暴”。一个数据帧或…...

网站改版的步骤/沈阳网站建设公司

目录&#xff1a; 1. HDFS透明加密 2.实现原理 3.KMS ACL用户权限配置 一. HDFS透明加密 HDFS Encryption Zone 加密空间&#xff0c;即HDFS透明加密&#xff0c;是一种端到端的加密模式&#xff0c;其中加解密过程对于客户端来说是完全透明的。 数据在客户端写操作时被加…...

南宁定制网站建设/免费观看b站的广告网站平台

在二叉树中查询特点节点 题目要求&#xff1a;如果我们查询D&#xff0c;返回D的地址&#xff0c;如果我们查询H&#xff0c;返回H的地址&#xff0c;如果查询不到&#xff0c;返回空 递归方法 如果我们在根节点的左边没有找到&#xff0c;就查找右边的。 BtNode* FindVal…...

dz做电影网站/seo排名优化培训

文件上传这个我看来有两种上传方法&#xff1a;一、上传到服务器上把文件地址存入数据库中 二、直接把文件以字节数存储 第一种方式比较常见&#xff1a;可以使用文件流的形式把文件写入到服务器端。 今天主要说明第二种方法&#xff1a; 因为我做的是web项目&#xff0c;所以上…...

最好的网站模版/竞价点击软件排名

小例题&#xff1a; n 个数 目前为三个数 x%32; x%53; x%72; 1.求最小公倍数&#xff1a;M357105。 2.依照余数求各个数的基础数&#xff1a; 105/335&#xff0c;35%32&#xff1b; 105/521&#xff0c;21%51&#xff0c;即63%53&#xff1b; 105/715&#xff0c;15%71&a…...

人大网站信息化建设报告/网站维护收费标准

1、概述 过去&#xff0c;程序员通常以像素为单位设计计算机用户界面。例如&#xff1a;图片大小为8032像素。这样处理的问题在于&#xff0c;如果在一个每英寸点数&#xff08;dpi&#xff09;更高的新显示器上运行该程序&#xff0c;则用户界面会显得很小。在有些情况下&…...