C++前缀和算法的应用:摘水果 原理源码测试用例

简介: C++前缀和算法的应用:摘水果 原理源码测试用例

本文涉及的基础知识点

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,假定x1<x2。则不移动x1,水果不会少。

分四种情况:

一,左移到底。

二,先左移,后右移。

三,右移到底。

四,先右移,再左移。

一是四的特殊请,三是二的特殊情况。

步骤

一,先获取前缀和。

二,枚举左移。右移为0或负数,忽视,因为劣于左移到底。k为0是,此条不符合。

三,枚举右移。

注意

坐标无限,但前缀和有限[0,iMaxPos]。

左移后的坐标 可能小于0
左移后的坐标 ** 可能大于iMax**
右移后的坐标 可能大于iMax
k为0时要左特殊处理。

变量解释

vNum 各坐标水果数量
vSum /vSum[i]记录[0,i)草莓的总数量
iMoveLeft 左移距离
iMoveRight 右移距离
left 移动到的最左坐标
right 移动到最右坐标

代码

核心代码

class Solution {
public:
int maxTotalFruits(vector<vector>& fruits, int startPos, int k) {
const int iMaxPos = fruits.back()[0];
vector vNum(iMaxPos + 1);
for (const auto&v : 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,right+1)的草莓
    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,right+1)的草莓
    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;
vector<vector> 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(vector<vector>& 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::map<int, 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::map<int, 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 C++17

或者 操作系统:win10 开发环境:

VS2022 C++17

相关文章
|
8天前
|
机器学习/深度学习 数据采集 自然语言处理
理解并应用机器学习算法:神经网络深度解析
【5月更文挑战第15天】本文深入解析了神经网络的基本原理和关键组成,包括神经元、层、权重、偏置及损失函数。介绍了神经网络在图像识别、NLP等领域的应用,并涵盖了从数据预处理、选择网络结构到训练与评估的实践流程。理解并掌握这些知识,有助于更好地运用神经网络解决实际问题。随着技术发展,神经网络未来潜力无限。
|
3天前
|
存储 编译器 C++
C++程序变量存储类别:深入理解与应用
C++程序变量存储类别:深入理解与应用
16 1
|
3天前
|
存储 C++
C++程序全局变量:理解与应用
C++程序全局变量:理解与应用
10 0
|
3天前
|
算法 Java
并发垃圾回收算法对于大规模服务器应用的优势
并发垃圾回收算法对于大规模服务器应用的优势
|
5天前
|
算法 搜索推荐 Java
滚雪球学Java(33):数组算法大揭秘:应用案例实战分享
【5月更文挑战第8天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
32 8
滚雪球学Java(33):数组算法大揭秘:应用案例实战分享
|
7天前
|
NoSQL 算法 Java
【redis源码学习】持久化机制,java程序员面试算法宝典pdf
【redis源码学习】持久化机制,java程序员面试算法宝典pdf
|
8天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
1天前
|
机器学习/深度学习 算法
基于BP神经网络的QPSK解调算法matlab性能仿真
该文介绍了使用MATLAB2022a实现的QPSK信号BP神经网络解调算法。QPSK调制信号在复杂信道环境下受到干扰,BP网络能适应性地补偿失真,降低误码率。核心程序涉及数据分割、网络训练及性能评估,最终通过星座图和误码率曲线展示结果。
|
1天前
|
机器学习/深度学习 算法 计算机视觉
基于yolov2深度学习网络模型的鱼眼镜头中人员检测算法matlab仿真
该内容是一个关于基于YOLOv2的鱼眼镜头人员检测算法的介绍。展示了算法运行的三张效果图,使用的是matlab2022a软件。YOLOv2模型结合鱼眼镜头畸变校正技术,对鱼眼图像中的人员进行准确检测。算法流程包括图像预处理、网络前向传播、边界框预测与分类及后处理。核心程序段加载预训练的YOLOv2检测器,遍历并处理图像,检测到的目标用矩形标注显示。
|
5天前
|
算法
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长
MATLAB 2022a仿真实现了LDPC码的性能分析,展示了不同码长对纠错能力的影响。短码长LDPC码收敛快但纠错能力有限,长码长则提供更强纠错能力但易陷入局部最优。核心代码通过循环进行误码率仿真,根据EsN0计算误比特率,并保存不同码长(12-768)的结果数据。
25 9
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长