乐清做手机网站,网站营销的优缺点,青岛关键词优化平台,返回邢台最新规定本文涉及的基础知识点
二分查找
题目
给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。 你的任务是使用从 0 到 n - 1 的数字创建若干组#xff0c;并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外#xff0c;还必须满足以下条件…本文涉及的基础知识点
二分查找
题目
给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。 你的任务是使用从 0 到 n - 1 的数字创建若干组并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外还必须满足以下条件 每个组必须由 不同 的数字组成也就是说单个组内不能存在重复的数字。 每个组除了第一个的长度必须 严格大于 前一个组。 在满足所有条件的情况下以整数形式返回可以创建的最大组数。 示例 1 输入usageLimits [1,2,5] 输出3 解释在这个示例中我们可以使用 0 至多一次使用 1 至多 2 次使用 2 至多 5 次。 一种既能满足所有条件又能创建最多组的方式是 组 1 包含数字 [2] 。 组 2 包含数字 [1,2] 。 组 3 包含数字 [0,1,2] 。 可以证明能够创建的最大组数是 3 。 所以输出是 3 。 示例 2 输入usageLimits [2,1,2] 输出2 解释在这个示例中我们可以使用 0 至多 2 次使用 1 至多 1 次使用 2 至多 2 次。 一种既能满足所有条件又能创建最多组的方式是 组 1 包含数字 [0] 。 组 2 包含数字 [1,2] 。 可以证明能够创建的最大组数是 2 。 所以输出是 2 。 示例 3 输入usageLimits [1,1] 输出1 解释在这个示例中我们可以使用 0 和 1 至多 1 次。 一种既能满足所有条件又能创建最多组的方式是 组 1 包含数字 [0] 。 可以证明能够创建的最大组数是 1 。 所以输出是 1 。 参数范围 1 usageLimits.length 105 1 usageLimits[i] 109
分析
知识点
假定最长组数为len则各组长度一定是1,2…len。假定各组长度不是连续的缺少x那么将(x…) 都扔掉一个元素变成[x,…)。持续这个过程至到各组长度连续为至。 只关心各值的数量不关心值比如1,2,3和2,1,3完全相同。故可对数据进行排序。
二分
如果如果能创建n组则一定能创建n-1组。随着len增加一定会由能创建变成不能创建。寻找最后一个能创建的len。显然适合用左闭右开的二分。
判断能否创建len组
预处理
目标数组为{1,2…len}源数组为升序排序后的 usageLimits长度不足则在前面补0。比如目标数组{1,2,3}源数组{0,3,3}目标数组{0,1,2,3}{1,1,2,2}。
推理
我们用len数组表示目标数组len[i]的含义[0,len[i])都会有此元素。
len[i]usageLimits[i]刚好len[i] usageLimits[i]不足需要补缺len[i] usageLimits[i]多余可以用于补缺
长度为3
由于组内不能有重复元素所以超过len个元素是无效的。我们用表格分析那些情况刚好创建3组没多余的数字。
1,1,1,1,1,1可以1填2和3的空缺1,1,1,1,2可以1填2和3的空缺1,1,2,2可以1填3的空缺2,2,2可以2填3的空缺1,1,1,3可以1填2的空缺1,2,3可以不用填空缺3,3不可以1的空缺无法填
猜测
3可以填4及以上缺如1333{2},{3,4},{2,3,4},{1,2,3,4}
如何补缺
假定i1i2i2无法补i1的缺因为i2已经用于[0,i2)不能用于[0,i1)中的任何组。 i1可以补i2的缺。i1只由于[0,i1)组所以补[i2,…)的缺不会造成同一组有重复数据。
一个数不会补缺两次
假定k len[i2] -en[i1]则i1多余不会超过k usageLimits[i1]-len[i1] k usageLimits[i1] len[i1]k usageLimits[i1] len[i2] 因为usageLimits[i2]usageLimits[i1] 所以usageLimits[i2]len2 所以i2有多余和有缺矛盾。 i1多余不会超过k所以补完i2的缺就空了。 无需考虑一个数补两个缺
代码
核心代码
class Solution { public: int maxIncreasingGroups(vector usageLimits) { m_c usageLimits.size(); m_v usageLimits; sort(m_v.begin(), m_v.end()); int left 1, right m_c 1; while (right - left 1) { const int mid left (right - left) / 2; if (Can(mid)) { left mid; } else { right mid; } } return left; } bool Can(int len) { int i m_c - 1; long long llNeed 0; for (; len 0; len–,i–) { llNeed - (m_v[i] - len); if (m_v[i] len) { llNeed max(0LL, llNeed); } } for(;i 0 ; i–) { llNeed - m_v[i]; } return llNeed 0; } int m_c; vector m_v; };
测试用例
template void Assert(const T t1, const T t2) { assert(t1 t2); }
template void Assert(const vector v1, const vector v2) { if (v1.size() ! v2.size()) { assert(false); return; } for (int i 0; i v1.size(); i) { Assert(v1[i] ,v2[i]); } }
int main() { Solution slu; vector usageLimits; int res 0; usageLimits { 2,2,2 }; res slu.maxIncreasingGroups(usageLimits); Assert(res, 3); usageLimits { 1,2,5 }; res slu.maxIncreasingGroups(usageLimits); Assert(res, 3); usageLimits { 2,1,2 }; res slu.maxIncreasingGroups(usageLimits); Assert(res, 2); usageLimits { 1,1 }; res slu.maxIncreasingGroups(usageLimits); Assert(res, 1);
//CConsole::Out(res);}
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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
