温州外贸公司网站建设公司排名,百度seo营销推广多少钱,wordpress 主域名,织梦模板网站源码2023-05-04每日一题
一、题目编号
2106. 摘水果二、题目链接
点击跳转到题目位置
三、题目描述
在一个无限的 x 坐标轴上#xff0c;有许多水果分布在其中某些位置。给你一个二维整数数组 fruits #xff0c;其中 fruits[i] [positioni, amounti] 表示共有 amounti 个水…2023-05-04每日一题
一、题目编号
2106. 摘水果二、题目链接
点击跳转到题目位置
三、题目描述
在一个无限的 x 坐标轴上有许多水果分布在其中某些位置。给你一个二维整数数组 fruits 其中 fruits[i] [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列 每个 positioni 互不相同 。
另给你两个整数 startPos 和 k 。最初你位于 startPos 。从任何位置你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置都会摘掉全部的水果水果也将从该位置消失不会再生。
返回你可以摘到水果的 最大总数 。
四、解题代码
class Solution {
public:int maxTotalFruits(vectorvectorint fruits, int startPos, int k) {int n fruits.size();long long sum[400010];memset(sum, 0, sizeof(sum));for(int i 0; i n; i){sum[fruits[i][0]] fruits[i][1]; }for(int i 1; i 200000; i){sum[i] sum[i-1];}if(startPos 0){return sum[min(200000, k)];}long long max0 0;for(int i 0; i k; i){if(i startPos){max0 max(max0 ,sum[max(startPos, startPos - 2 * i k)]);} else if(i startPos){max0 max(max0, sum[max(startPos, startPos - 2 * i k )] - sum[startPos - i - 1]);}if(startPos i 200000){if(max(k - 2 * i, 0) startPos){max0 max(sum[startPos i], max0);} else{max0 max(max0, sum[startPos i] - sum[startPos - max(k - 2 * i, 0) - 1]); }}}return max0;}
};五、解题思路
(1) 首先我们思考能走多少步设步数为i。我们很容易可以根据题目来知晓这个步数为0 ~ k。
(2) 那我们将问题转化成我们该如何规划这i步使得摘到的水果最多。我们根据贪心的原理可以很容易知晓我们应该尽可能的利用上我们的步数。那么我们的问题就转化成一开始是往右走还是一开始往左走。
(3) 这样我们可以根据往左走或者往右走的步数规划出一个窗口。计算出该窗口中水果的数目只要取水果数目最大的窗口即为最终的答案。
(4) 最后我们只需要用前缀和来求出遍历到的每一个窗口中水果的数目即可。
