公司核准名称网站,做设计那个素材网站最好,个人博客页面模板,网站会员管理本文涉及的基础知识点
C算法#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 双指针 单调双向队列
题目
你有一辆货运卡车#xff0c;你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。 给你…本文涉及的基础知识点
C算法前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 双指针 单调双向队列
题目
你有一辆货运卡车你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。 给你一个箱子数组 boxes 和三个整数 portsCount, maxBoxes 和 maxWeight 其中 boxes[i] [portsi, weighti] 。 portsi 表示第 i 个箱子需要送达的码头 weightsi 是第 i 个箱子的重量。 portsCount 是码头的数目。 maxBoxes 和 maxWeight 分别是卡车每趟运输箱子数目和重量的限制。 箱子需要按照 数组顺序 运输同时每次运输需要遵循以下步骤 卡车从 boxes 队列中按顺序取出若干个箱子但不能违反 maxBoxes 和 maxWeight 限制。 对于在卡车上的箱子我们需要 按顺序 处理它们卡车会通过 一趟行程 将最前面的箱子送到目的地码头并卸货。如果卡车已经在对应的码头那么不需要 额外行程 箱子也会立马被卸货。 卡车上所有箱子都被卸货后卡车需要 一趟行程 回到仓库从箱子队列里再取出一些箱子。 卡车在将所有箱子运输并卸货后最后必须回到仓库。 请你返回将所有箱子送到相应码头的 最少行程 次数。 示例 1 输入boxes [[1,1],[2,1],[1,1]], portsCount 2, maxBoxes 3, maxWeight 3 输出4 解释最优策略如下
卡车将所有箱子装上车到达码头 1 然后去码头 2 然后再回到码头 1 最后回到仓库总共需要 4 趟行程。 所以总行程数为 4 。 注意到第一个和第三个箱子不能同时被卸货因为箱子需要按顺序处理也就是第二个箱子需要先被送到码头 2 然后才能处理第三个箱子。 示例 2 输入boxes [[1,2],[3,3],[3,1],[3,1],[2,4]], portsCount 3, maxBoxes 3, maxWeight 6 输出6 解释最优策略如下卡车首先运输第一个箱子到达码头 1 然后回到仓库总共 2 趟行程。卡车运输第二、第三、第四个箱子到达码头 3 然后回到仓库总共 2 趟行程。卡车运输第五个箱子到达码头 2 回到仓库总共 2 趟行程。 总行程数为 2 2 2 6 。 示例 3 输入boxes [[1,4],[1,2],[2,1],[2,1],[3,2],[3,4]], portsCount 3, maxBoxes 6, maxWeight 7 输出6 解释最优策略如下卡车运输第一和第二个箱子到达码头 1 然后回到仓库总共 2 趟行程。卡车运输第三和第四个箱子到达码头 2 然后回到仓库总共 2 趟行程。卡车运输第五和第六个箱子到达码头 3 然后回到仓库总共 2 趟行程。 总行程数为 2 2 2 6 。 示例 4 输入boxes [[2,4],[2,5],[3,1],[3,2],[3,7],[3,1],[4,4],[1,3],[5,2]], portsCount 5, maxBoxes 5, maxWeight 7 输出14 解释最优策略如下卡车运输第一个箱子到达码头 2 然后回到仓库总共 2 趟行程。卡车运输第二个箱子到达码头 2 然后回到仓库总共 2 趟行程。卡车运输第三和第四个箱子到达码头 3 然后回到仓库总共 2 趟行程。卡车运输第五个箱子到达码头 3 然后回到仓库总共 2 趟行程。卡车运输第六和第七个箱子到达码头 3 然后去码头 4 然后回到仓库总共 3 趟行程。卡车运输第八和第九个箱子到达码头 1 然后去码头 5 然后回到仓库总共 3 趟行程。 总行程数为 2 2 2 2 3 3 14 。
提示 1 boxes.length 105 1 portsCount, maxBoxes, maxWeight 105 1 portsi portsCount 1 weightsi maxWeight
可理解行强的解法
如果有多种运输的boxs[0,i)的方式只需要保留行程最少的方式且只需要记录最小行程此值用m_vRet[i]记录。分成两步第一步运输box[0,j)第二步运输[j,i)。一次可以运输完成可以看成第一步是box[0,0)。枚举i,j的时间复杂度都是O(n)总时间复杂度是O(n*n)。
利用前缀和计算[j,i)的箱子总重量
vWeightSum[i]记录了boxs[0,i)的重中立vWeightSum[i]-vWeightSum[j]。
利用前缀和计算[i,j)需要单独下车的次数
vDownSum[i]记录[0,i)需要单独下车的次数。vDown[j]-vDownSum[i]。和前面的箱子不同则需要单独下车。
优化枚举
m_vRet[i] min(…,X) Xm_vRet[j]1 1 vDown[j1,i)。 11 表示返程和下第一箱子从第二个箱子起要计算要单独下。X m_vRet[j]11vDown[i] - vDown[j1] ,令 Y m_vRet[j]-vDow[j1]则XY 2 vDown[i] ,显然Y可以提前计算。每次处理完i将Y记录到setPre中。setPre对应的索引为[left,i)如果[left,i)超量或超重则left并更新setPre。
时间复杂度
枚举i时间复杂度。二分查找setPre时间复杂度O(logn)总时间复杂度O(nlogn)。
核心代码
class Solution { public: int boxDelivering(vectorvector boxes, int portsCount, int maxBoxes, int maxWeight) { m_c boxes.size(); m_vRet.resize(m_c1);//记录boxes[0,i) 需的最小行程数 vector vWeightSum { 0 };//箱子重量前缀和 for (const auto v : boxes) { vWeightSum.emplace_back(v[1] vWeightSum.back()); } vector vDownSum { 0,0 };//假定不是本车的第一个箱子卸货需要的次数 for (int i 1; i m_c; i) { vDownSum.emplace_back(vDownSum.back() (boxes[i][0] ! boxes[i-1][0])); } std::multiset setPre { 0 }; //记录可以作为前一趟的最小行程数-vDownSum[i 1] int left 0;//[left,i)是上一趟的行程 for (int i 1; i m_c; i) { // [left,i)为空不会超重也不会超量。所以无需判断是否为空 while ((i - left maxBoxes) || (vWeightSum[i] - vWeightSum[left] maxWeight)) { //如果[left,i)超重或超亮 const int tmp m_vRet[left ] - vDownSum[left1 ]; setPre.erase(setPre.find(tmp)); left; } m_vRet[i ] *setPre.begin() 2 vDownSum[i] ; if (i 1 m_c) { setPre.emplace(m_vRet[i] - vDownSum[i 1]); } } return m_vRet.back(); } int m_c; vector m_vRet; };
测试用例
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]); } }
template void Assert(const T t1, const T t2) { assert(t1 t2); }
int main() { vectorvector boxes { {1,1},{2,1},{1,1} }; int portsCount 2, maxBoxes 3, maxWeight 3; auto res Solution().boxDelivering(boxes, portsCount, maxBoxes, maxWeight); Assert(4, res); boxes { {1,2},{3,3},{3,1},{3,1},{2,4} }; portsCount 3, maxBoxes 3, maxWeight 6; res Solution().boxDelivering(boxes, portsCount, maxBoxes, maxWeight); Assert(6, res); boxes { {2,4},{2,5},{3,1},{3,2},{3,7},{3,1},{4,4},{1,3},{5,2} }; portsCount 5, maxBoxes 5, maxWeight 7; res Solution().boxDelivering(boxes, portsCount, maxBoxes, maxWeight); Assert(14, res);
//CConsole::Out(res);}
优化二单调双向队列
原理
setPre的旧值如果大于等于新值则被淘汰了。这意味着值是按升序排序的。移除值有两种原因一旧值比新值大被淘汰。从容器尾淘汰。二旧值超重或超过数量了从容器头淘汰。所以用双向队列。
代码
class Solution { public: int boxDelivering(vectorvector boxes, int portsCount, int maxBoxes, int maxWeight) { m_c boxes.size(); m_vRet.resize(m_c1);//记录boxes[0,i) 需的最小行程数 vector vWeightSum { 0 };//箱子重量前缀和 for (const auto v : boxes) { vWeightSum.emplace_back(v[1] vWeightSum.back()); } vector vDownSum { 0,0 };//假定不是本车的第一个箱子卸货需要的次数 for (int i 1; i m_c; i) { vDownSum.emplace_back(vDownSum.back() (boxes[i][0] ! boxes[i-1][0])); } std::dequepairint, int mSumJ { { 0,0} }; for (int i 1; i m_c; i) { // [left,i)为空不会超重也不会超量。所以无需判断是否为空 while (mSumJ.size() ((i - mSumJ.front().second maxBoxes) || (vWeightSum[i] - vWeightSum[mSumJ.front().second] maxWeight))) { //如果[left,i)超重或超亮 mSumJ.pop_front(); } m_vRet[i ] mSumJ.front().first 2 vDownSum[i] ; if (i 1 m_c) { continue; } const int iNew m_vRet[i] - vDownSum[i 1]; while (mSumJ.size() (mSumJ.back().first iNew)) { mSumJ.pop_back(); } mSumJ.emplace_back(iNew, i); } return m_vRet.back(); } int m_c; vector m_vRet; };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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
