做网站需要的带宽上行还是下行,国内最大的app开发公司,南通网站建设搭建,吴江微信网站制作本文涉及知识点
状态压缩 容斥原理 组合数学 二分查找算法合集
LeetCode100267. 单面值组合的第 K 小金额
给你一个整数数组 coins 表示不同面额的硬币#xff0c;另给你一个整数 k 。 你有无限量的每种面额的硬币。但是#xff0c;你 不能 组合使用不同面额的硬币。 返回…本文涉及知识点
状态压缩 容斥原理 组合数学 二分查找算法合集
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-28。6是最小公倍数LCM bcoins {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(vectorint coins, int k) {m_coins coins; long long left 0, right 1000000000000LL;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) {vectorvectorlong long vMask; long long llRet 0;for (const auto n : m_coins) {vectorvectorlong long vMask2;for (const auto v : vMask) {vectorlong 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;}vectorint m_coins;
};测试用例
int main()
{vectorint 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(vectorint coins, int k) { const int iMaskCount 1 coins.size();vectorint v01(iMaskCount),vLCM(iMaskCount,-1);vectorint 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 1000000000000LL;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(vectorint coins, int k) { const int iMaskCount 1 coins.size(); vectorlong long vMask[2];//vMask[0] 记录 偶数个数的最小公倍数vMask[1]记录奇数个数的最小公倍数vectorlong 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 1000000000000LL;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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
