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

C++前缀和算法的应用:摘水果 原理源码测试用例,# 算法题,数据结构与算法,c++,算法,开发语言,leetcode,前缀和,摘水果,测试用例文章来源地址https://www.toymoban.com/news/detail-737151.html

到了这里,关于C++前缀和算法的应用:摘水果 原理源码测试用例的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++前缀和算法的应用:统计上升四元组

    C++前缀和算法的应用:统计上升四元组 C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 给你一个长度为 n 下标从 0 开始的整数数组 nums ,它包含 1 到 n 的所有数字,请你返回上升四元组的数目。 如果一个四元组 (i, j, k, l) 满足以下条件,我们称

    2024年02月06日
    浏览(40)
  • C++前缀和算法:构造乘积矩阵

    C++算法:前缀和基础 给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ,定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件,则称 p 为 grid 的 乘积矩阵 : 对于每个元素 p[i][j] ,它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。

    2024年02月08日
    浏览(46)
  • C++基础算法前缀和和差分篇

    📟作者主页:慢热的陕西人 🌴专栏链接:C++算法 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 主要讲解了前缀和和差分算法 Ⅵ .Ⅰ前缀和 ① 一维前缀和 : ​ 就是构建一个新的数组 s ,用来存储另一个数组的和前 i 个数组元素的和。用公式表达就是: S [ i ] = a [ 0 ]

    2024年02月16日
    浏览(49)
  • 【0基础学算法】前缀和 (超详细讲解+私人笔记+源码)

    目录 什么是前缀和 我们为什么要去学习前缀和 前缀和实现 如何求s[i]  S[i]的作用  模板 一维前缀和 二维前缀和 题目 第一题 第二题 哈喽大家好,很长时间忘记更新咱们的学算法系列文章了,今天我们终于迎来了我们零基础学算法的第四期内容,那就是前缀和,前缀和其实

    2024年02月05日
    浏览(61)
  • 一文带你深入了解算法笔记中的前缀与差分(附源码)

    📖作者介绍:22级树莓人(计算机专业),热爱编程<目前在c++阶段, 因为最近参加新星计划算法赛道(白佬),所以加快了脚步,果然急迫感会增加动力 ——目标Windows,MySQL,Qt,数据结构与算法,Linux,多线程,会持续分享学习成果和小项目的 📖作者主页:热爱编程的

    2023年04月12日
    浏览(62)
  • 接口测试用例生成工具介绍及应用

    目前,接口测试是开展项目测试实施过程中非常重要的环节,对于新增接口和修改接口更是需要做到应测必测,但是在实施过程中普遍存在一些问题,经分析总结如下: 1.耗时长: 接口测试整体流程较长,对每个字段都需要进行各种校验,且人工进行基础性字段验证的过程极

    2023年04月11日
    浏览(61)
  • 大数据毕设分享(含算法) 多功能 Web 应用渗透测试系统(源码+论文)

    # 0 简介 今天学长向大家介绍适合作为毕设的项目: 毕设分享 多功能 Web 应用渗透测试系统(源码+论文) 项目获取: https://gitee.com/assistant-a/project-sharing 系统简介 本项目为 多功能 Web 应用渗透测试系统 ,包含 漏洞检测、目录识别、端口扫描、指纹识别、域名探测、旁站探测

    2024年02月21日
    浏览(48)
  • 【算法思考记录】【前缀和,C++】力扣1277. 统计全为 1 的正方形子矩阵

    原题链接 题目要求我们统计在一个由0和1构成的矩阵中,所有完全由1组成的正方形子矩阵的数量。这是一道中等难度的算法题目,其关键在于高效地计算出不同大小的正方形子矩阵是否完全由1组成。 解决此问题的一个有效方法是使用 前缀和 算法。前缀和是一种预处理技术

    2024年02月03日
    浏览(38)
  • 【C++提高编程】list 容器详解(附测试用例与结果图)

    1.1 list基本概念 功能: 将数据进行链式存储 链表 (list)是一种物理存储单元上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接实现的 链表的组成:链表由一系列 结点 组成 结点的组成:一个是存储数据元素的 数据域 ,另一个是存储下一个结点地址的 指

    2024年01月19日
    浏览(50)
  • 【Unity学习笔记】New Input System 部分源码和测试用例补充

    转载请注明出处:🔗https://blog.csdn.net/weixin_44013533/article/details/135630016 作者:CSDN@|Ringleader| 主要参考: Unity官方Input System手册与API 【Unity学习笔记】Unity TestRunner使用 NewIputSystem主体内容请参见:【Unity学习笔记】第十二 · New Input System 及其系统结构 和 源码浅析 注:本文使用的

    2024年01月22日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包