长沙seo网站建设,深圳市公司网站建设价格,网站开发摊销,小企业官方网站制作本文涉及的基础知识点
C算法#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
在一个无限的 x 坐标轴上#xff0c;有许多水果分布在其中某些位置。给你一个二维整数数组 fruits #xff0c;其中 fruits[i] [positioni, amounti] 表示共…本文涉及的基础知识点
C算法前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
在一个无限的 x 坐标轴上有许多水果分布在其中某些位置。给你一个二维整数数组 fruits 其中 fruits[i] [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列 每个 positioni 互不相同 。 另给你两个整数 startPos 和 k 。最初你位于 startPos 。从任何位置你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置都会摘掉全部的水果水果也将从该位置消失不会再生。 返回你可以摘到水果的 最大总数 。 示例 1 输入fruits [[2,8],[6,3],[8,6]], startPos 5, k 4 输出9 解释 最佳路线为
向右移动到位置 6 摘到 3 个水果向右移动到位置 8 摘到 6 个水果 移动 3 步共摘到 3 6 9 个水果 示例 2 输入fruits [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos 5, k 4 输出14 解释 可以移动最多 k 4 步所以无法到达位置 0 和位置 10 。 最佳路线为在初始位置 5 摘到 7 个水果向左移动到位置 4 摘到 1 个水果向右移动到位置 6 摘到 2 个水果向右移动到位置 7 摘到 4 个水果 移动 1 3 4 步共摘到 7 1 2 4 14 个水果 示例 3 输入fruits [[0,3],[6,4],[8,5]], startPos 3, k 2 输出0 解释 最多可以移动 k 2 步无法到达任一有水果的地方
参数范围 1 fruits.length 105 fruits[i].length 2 0 startPos, positioni 2 * 105 对于任意 i 0 positioni-1 positioni 均成立下标从 0 开始计数 1 amounti 104 0 k 2 * 105
分析
原理
只需要左移右移一次。假定左移了两次分别移动了x1,x2,假定x1x2。则不移动x1水果不会少。 分四种情况 一左移到底。 二先左移后右移。 三右移到底。 四先右移再左移。 一是四的特殊请三是二的特殊情况。
步骤
一先获取前缀和。 二枚举左移。右移为0或负数忽视因为劣于左移到底。k为0是此条不符合。 三枚举右移。
注意
坐标无限但前缀和有限[0,iMaxPos]。
左移后的坐标可能小于0左移后的坐标** 可能大于iMax**右移后的坐标可能大于iMaxk为0时要左特殊处理。
变量解释
vNum各坐标水果数量vSum/vSum[i]记录[0,i)草莓的总数量iMoveLeft左移距离iMoveRight右移距离left移动到的最左坐标right移动到最右坐标
代码
核心代码
class Solution { public: int maxTotalFruits(vectorvector fruits, int startPos, int k) { const int iMaxPos fruits.back()[0]; vector vNum(iMaxPos 1); for (const autov : fruits) { vNum[v[0]] v[1]; } vector vSum { 0 };//vSum[i]记录[0,i)草莓的总数量 for (int i 0; i iMaxPos; i) { vSum.emplace_back(vSum.back() vNum[i]); } int iRet 0;for (int iMoveLeft 0; iMoveLeft k / 2; iMoveLeft){//先左后右const int iMoveRight k - iMoveLeft * 2;if (iMoveRight 0){continue;}const int left max(0, startPos - iMoveLeft);if (left iMaxPos){continue;}const int right min(iMaxPos, startPos iMoveRight);//可收集[left,right1)的草莓const int cur vSum[right 1] - vSum[left];iRet max(iRet, cur);}for (int iMoveRight 0; iMoveRight k / 2; iMoveRight){//先左后右const int iMoveLeft k - iMoveRight * 2;if (iMoveLeft 0){continue;}const int left max(0, startPos - iMoveLeft);if (left iMaxPos){continue;}const int right min(iMaxPos, startPos iMoveRight);//可收集[left,right1)的草莓const int cur vSum[right 1] - vSum[left];iRet max(iRet, cur);}return iRet;
}};
测试用例
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() { Solution slu; vectorvector fruits; int startPos 0; int k 0; int res;
fruits {{2, 8}, {6, 3}, {8, 6}};
startPos 5 ;
k 4 ;
res slu.maxTotalFruits(fruits, startPos, k);
Assert(9, res);fruits {{0, 9}, {4, 1}, {5, 7}, {6, 2}, {7, 4}, {10, 9}};
startPos 5;
k 4;
res slu.maxTotalFruits(fruits, startPos, k);
Assert(14, res);fruits { {0,10000} };
startPos 20000;
k 20000;
res slu.maxTotalFruits(fruits, startPos, k);
Assert(10000, res);fruits { {20000,10000} };
startPos 20000;
k 0;
res slu.maxTotalFruits(fruits, startPos, k);
Assert(10000, res);//CConsole::Out(res);}
2023年3月旧代码
class Solution { public: int maxTotalFruits(vectorvector fruits, int startPos, int k) { m_c fruits.size(); int iMaxLeftIndex std::lower_bound(fruits.begin(), fruits.end(),startPos, [](const vector v, int i) { return v[0] i; }) - fruits.begin() - 1; std::mapint, int mLeftMoveNum; for (int i iMaxLeftIndex ; (i 0) (startPos - fruits[i][0] k); i–) { const int iLeftMove startPos - fruits[i][0]; mLeftMoveNum[iLeftMove] fruits[i][1] (mLeftMoveNum.empty() ? 0 : mLeftMoveNum.rbegin()-second); } int iMinRightIndex iMaxLeftIndex 1; int iRet 0; if ((iMinRightIndex m_c) (fruits[iMinRightIndex][0] startPos)) { iRet fruits[iMinRightIndex][1]; iMinRightIndex; } std::mapint, int mRightMoveNum; for (int i iMinRightIndex; (i m_c) (fruits[i][0] - startPos k); i) { const int iRightMove fruits[i][0] - startPos; mRightMoveNum[iRightMove] fruits[i][1] (mRightMoveNum.empty() ? 0 : mRightMoveNum.rbegin()-second); } int iMaxExcludeStart 0;for (int left 0; left k / 2; left){const int right k - left * 2;int iCur 0;{auto itLeft mLeftMoveNum.upper_bound(left);if (mLeftMoveNum.begin() ! itLeft){iCur (--itLeft)-second;}}{auto itRight mRightMoveNum.upper_bound(right);if (mRightMoveNum.begin() ! itRight){iCur (--itRight)-second;}}iMaxExcludeStart max(iMaxExcludeStart, iCur);}for (int right 0; right k / 2; right){const int left k - right * 2;int iCur 0;{auto itLeft mLeftMoveNum.upper_bound(left);if (mLeftMoveNum.begin() ! itLeft){iCur (--itLeft)-second;}}{auto itRight mRightMoveNum.upper_bound(right);if (mRightMoveNum.begin() ! itRight){iCur (--itRight)-second;}}iMaxExcludeStart max(iMaxExcludeStart, iCur);}iRet iMaxExcludeStart;return iRet;}int m_c;};
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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
