投票网站源码php,朋友圈营销,自己做网站微商,网站里的个人中心下拉列表怎么做本周推荐阅读
C二分算法#xff1a;得到子序列的最少操作次数
本题的其它解法
C二分算法#xff1a;最多可以参加的会议数目 II
本文涉及的基础知识点
二分查找算法合集
题目
给你一个 events 数组#xff0c;其中 events[i] [startDayi, endDayi, valuei] #xf…本周推荐阅读
C二分算法得到子序列的最少操作次数
本题的其它解法
C二分算法最多可以参加的会议数目 II
本文涉及的基础知识点
二分查找算法合集
题目
给你一个 events 数组其中 events[i] [startDayi, endDayi, valuei] 表示第 i 个会议在 startDayi 天开始第 endDayi 天结束如果你参加这个会议你能得到价值 valuei 。同时给你一个整数 k 表示你能参加的最多会议数目。 你同一时间只能参加一个会议。如果你选择参加某个会议那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。 请你返回能得到的会议价值 最大和 。 示例 1 输入events [[1,2,4],[3,4,3],[2,3,1]], k 2 输出7 解释选择绿色的活动会议 0 和 1得到总价值和为 4 3 7 。 示例 2 输入events [[1,2,4],[3,4,3],[2,3,10]], k 2 输出10 解释参加会议 2 得到价值和为 10 。 你没法再参加别的会议了因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。 示例 3 输入events [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k 3 输出9 解释尽管会议互不重叠你只能参加 3 个会议所以选择价值最大的 3 个会议。 **参数范围 1 k events.length 1 k * events.length 106 1 startDayi endDayi 109 1 valuei 106
分析
上面的代码可以通过也好理解。就是不够简洁值转索引用了大约10行。直接先按结束时间排序然后二分查找。
变量解释
vEndIndexNumToMaxValue[i][k]j表示event[0,i][1]结束完成k个会议的最大价值。假定event[0,j)的结束时间都小于当前开始时间,event[j…)的结束时间都大于或等于当前开始时间。分两种情况
0j只能完成本任务j0参加会议j后再参加任务i注意确保vEndIndexNumToMaxValue[i][k]大于等于vEndIndexNumToMaxValue[i-1][k]否则就不递增了。递增才能进行二分查找
代码
错误代码一
class Solution { public: int maxValue(vectorvector events, const int K) { m_c events.size(); sort(events.begin(), events.end(), [](const auto v1, const auto v2) {return v1[1] v2[1]; }); vectorvector vEndIndexNumToMaxValue(m_c,vector(K 1)); int iPreIndex 0; for (int i 0 ; i m_c ; i ) { const auto v events[i]; while ((iPreIndex m_c) (events[iPreIndex][1] v[0])) { iPreIndex; } if (0 iPreIndex) { vEndIndexNumToMaxValue[i].assign(K 1, v[2]); vEndIndexNumToMaxValue[i][0] 0; continue; } for (int k 1; k K; k) { vEndIndexNumToMaxValue[i][k] max(vEndIndexNumToMaxValue[iPreIndex-1][k-1]v[2],(0i)?0:vEndIndexNumToMaxValue[i-1][k]); } } return vEndIndexNumToMaxValue.back().back(); } int m_c; };
错误原因
必须确保vEndIndexNumToMaxValuek相同时递增。 注意:
vEndIndexNumToMaxValue[i][0] 0;错误代码二
class Solution { public: int maxValue(vectorvector events, const int K) { m_c events.size(); sort(events.begin(), events.end(), [](const auto v1, const auto v2) {return v1[1] v2[1]; }); vectorvector vEndIndexNumToMaxValue(m_c,vector(K 1)); int iPreIndex 0; for (int i 0 ; i m_c ; i ) { const auto v events[i]; while ((iPreIndex m_c) (events[iPreIndex][1] v[0])) { iPreIndex; } for (int k 1; k K; k) { const int iPreMax (0 iPreIndex) ? 0 : vEndIndexNumToMaxValue[iPreIndex - 1][k - 1]; vEndIndexNumToMaxValue[i][k] max(iPreMax v[2],(0i)?0:vEndIndexNumToMaxValue[i-1][k]); } } return vEndIndexNumToMaxValue.back().back(); } int m_c; };
错误原因
开始时间并不是递增的。
正确代码
class Solution {
public:int maxValue(vectorvectorint events, const int K) {m_c events.size();sort(events.begin(), events.end(), [](const auto v1, const auto v2) {return v1[1] v2[1]; });vectorvectorint vEndIndexNumToMaxValue(m_c,vectorint(K 1));for (int i 0 ; i m_c ; i ){const auto v events[i];auto it std::lower_bound(events.begin(), events.end(), v[0], [](const auto v, int i) {return v[1] i; });const int iLowerIndex it - events.begin(); for (int k 1; k K; k){const int iPreMax (0 iLowerIndex) ? 0 : vEndIndexNumToMaxValue[iLowerIndex - 1][k - 1];vEndIndexNumToMaxValue[i][k] max(iPreMax v[2],(0i)?0:vEndIndexNumToMaxValue[i-1][k]);} } return vEndIndexNumToMaxValue.back().back();}int m_c;
};测试用例
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() { vectorvector events; int k; int res; { Solution slu; events { {53, 55, 77},{37, 56, 58} }; k 1; res slu.maxValue(events, k); Assert(res, 77); } { Solution slu; events { {1,2,4},{3,4,3},{2,3,1} }; k 2; res slu.maxValue(events, k); Assert(res, 7); } { Solution slu; events { {1,2,4},{3,4,3},{2,3,10} }; k 2; res slu.maxValue(events, k); Assert(res, 10); } { Solution slu; events { {1,1,1},{2,2,2},{3,3,3},{4,4,4} }; k 3; res slu.maxValue(events, k); Assert(res, 9); } { Solution slu; events { {21,77,43},{2,74,47},{6,59,22},{47,47,38},{13,74,57},{27,55,27},{8,15,8} }; k 4; res slu.maxValue(events, k); Assert(res, 57); }
//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
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
