LeetCode 2106. 摘水果

这篇具有很好参考价值的文章主要介绍了LeetCode 2106. 摘水果。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【LetMeFly】2106.摘水果

力扣题目链接:https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/

在一个无限的 x 坐标轴上,有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ,其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列 ,每个 positioni 互不相同

另给你两个整数 startPosk 。最初,你位于 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 > 0positioni-1 < positioni 均成立(下标从 0 开始计数)
  • 1 <= amounti <= 104
  • 0 <= k <= 2 * 105

方法一:滑动窗口

滑动窗口的核心思路是:使用两个指针l和r指向fruits数组,l和r之间的部分称为“窗口”。每次右指针r右移一位,左指针移动到“满足题目条件”且尽可能靠左的位置。

什么叫“满足题目条件”?“满足题目条件”是指从startPos左右移动k步内能经过l和r。

这样,右指针每次只移动一位,左指针也是在上次的位置基础上进行移动的(总计移动次数不超过数组长度),因此窗口移动的总时间复杂度是 O ( l e n ( f r u i t s ) ) O(len(fruits)) O(len(fruits))

所以,我们只需要编写一个函数:minStep,来计算从startPos处开始左右移动,经过l和r,至少需要几步。

  • 如果fruits[r]的位置小于startPos,就说明窗口完全位于起点左边,只需要从起点移动到l处即可( s t a r t P o s − f r u i t s [ l ] [ 0 ] startPos - fruits[l][0] startPosfruits[l][0]
  • 如果fruits[l]的位置大于startPos,就说明窗口完全位于起点右边,只需要从起点移动到r处即可( f r u i t s [ r ] [ 0 ] − s t a r t P o s fruits[r][0] - startPos fruits[r][0]startPos
  • 否则,说明窗口横跨起点,需要从起点移动到l再返回并移动到r,或者从起点移动到r再返回移动到l( min ⁡ ( 2 × 起点到 l + 起点到 r , 起点到 l + 2 × 起点到 r ) \min(2\times 起点到l + 起点到r, 起点到l + 2\times 起点到r) min(2×起点到l+起点到r,起点到l+2×起点到r)

对于窗口l到r,调用这个函数就能很轻松地计算出当前窗口能否在k步之内被覆盖

  • 时间复杂度 O ( l e n ( f r u i t s ) ) O(len(fruits)) O(len(fruits))
  • 空间复杂度 O ( 1 ) O(1) O(1)

AC代码

C++
class Solution {
private:
    int minStep(vector<vector<int>>& fruits, int l, int r, int startPos) {
        if (fruits[r][0] <= startPos) {  // 全在起点左边
            return startPos - fruits[l][0];
        }
        else if (fruits[l][0] >= startPos) {  // 全在起点右边
            return fruits[r][0] - startPos;
        }
        else {  // 横跨起点左右
            int leftDistance = startPos - fruits[l][0];
            int rightDistance = fruits[r][0] - startPos;
            return min(2 * leftDistance + rightDistance, leftDistance + 2 * rightDistance);
        }
    }
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        int ans = 0;
        int cnt = 0;  // 窗口中的水果总数
        int l = 0;
        for (int r = 0; r < fruits.size(); r++) {
            cnt += fruits[r][1];
            while (l <= r && minStep(fruits, l, r, startPos) > k) {
                cnt -= fruits[l][1];
                l++;
            }
            ans = max(ans, cnt);
        }
        return ans;
    }
};
Python
# from typing import List

class Solution:
    def minStep(self, fruits: List[List[int]], startPos: int, l: int, r: int) -> int:
        if fruits[r][0] <= startPos:
            return startPos - fruits[l][0]
        elif fruits[l][0] >= startPos:
            return fruits[r][0] - startPos
        else:
            leftDistance = startPos - fruits[l][0]
            rightDistance = fruits[r][0] - startPos
            return min(2 * leftDistance + rightDistance, leftDistance + 2 * rightDistance)
    
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        ans = 0
        cnt = 0
        l = 0
        r = 0
        while r < len(fruits):
            cnt += fruits[r][1]
            while l <= r and self.minStep(fruits, startPos, l, r) > k:
                cnt -= fruits[l][1]
                l += 1
            ans = max(ans, cnt)
            r += 1
        return ans

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/130482457文章来源地址https://www.toymoban.com/news/detail-436116.html

到了这里,关于LeetCode 2106. 摘水果的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 力扣题目训练(17)

    2024年2月10日第十七天编程训练,今天主要是进行一些题训练,包括简单题3道、中等题2道和困难题1道。惰性太强现在才完成,不过之后我会认真完成的。 链接: 出勤记录 难度: 简单 题目: 运行示例: 思路: 这道题就是一个简单的遍历,只需在遍历时判断是否不符合条件的

    2024年02月21日
    浏览(37)
  • 打卡力扣题目九

    #左耳听风 ARST 打卡活动重启# 目录  一、问题  二、解题方法一  三、解题方法二 四、两种方法的区别 关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share

    2024年02月14日
    浏览(37)
  • 打卡一个力扣题目

    目录 一、问题 二、解题办法一 三、解题方法二 四、对比分析 关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share: 分享一篇有观点和思考的技术文章 希望通

    2024年02月15日
    浏览(35)
  • 打卡力扣题目四

     #左耳听风 ARST 打卡活动重启#   目录 一、题目  二、解题代码  三、解题思路  关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share: 分享一篇有观点和思考

    2024年02月14日
    浏览(33)
  • 力扣题目训练(9)

    2024年2月2日第九天编程训练,今天主要是进行一些题训练,包括简单题3道、中等题2道和困难题1道。惰性太强现在才完成,不过之后我会认真完成的。 链接: Fizz Buzz 难度: 简单 题目: 运行示例: 思路: 这就是一个简单的遍历,只要按要求把特定位置进行修改即可。 代码:

    2024年02月19日
    浏览(41)
  • 打卡力扣题目三

     #左耳听风 ARST 打卡活动重启# 目录  一、题目  二、解题方法一 三、解题方法二  关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share: 分享一篇有观点和思

    2024年02月14日
    浏览(37)
  • 打卡力扣题目七

    #左耳听风 ARST 打卡活动重启# 目录  一、题目 二、解题方法一 三、解题方法二  关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share: 分享一篇有观点和思考

    2024年02月14日
    浏览(31)
  • 力扣题目训练(6)

    2024年1月30日第六天编程训练,今天主要是进行一些题训练,包括简单题3道、中等题2道和困难题1道。对于一些经典题目的掌握还是有点小问题,需要利用我们已知的性质去完成。 链接: 完全平方数 难度: 简单 题目: 运行示例: 思路: 这个题试求平方,但是不能用自带的函

    2024年02月22日
    浏览(41)
  • 打卡力扣题目六

    #左耳听风 ARST 打卡活动重启# 目录  一、问题 二、解题方法 三、解题方法二  四、两个方法的区别  关于 ARTS 的释义 —— 每周完成一个 ARTS: ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share: 分

    2024年02月15日
    浏览(35)
  • C++力扣题目77--组合

    给定两个整数  n  和  k ,返回范围  [1, n]  中所有可能的  k  个数的组合。 你可以按  任何顺序  返回答案。 示例 1: 示例 2: 提示: 1 = n = 20 1 = k = n 本题是回溯法的经典题目。 直接的解法当然是使用for循环,例如示例中k为2,很容易想到 用两个for循环,这样就可以输

    2024年01月17日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包