豆包MarsCode AI 刷题——农场采摘水果问题

问题分析

本题描述了一个农场采摘水果的场景。农场的果树排成一列，用整数数组fruits表示，每个元素fruits[i]是第i棵树上的水果种类。有两个篮子，每个篮子只能装一种类型的水果，且每个篮子可以装无限量的水果。从任意一棵树开始采摘，必须从每棵树上恰好采摘一个水果，并且只能装入符合篮子中水果类型的果实，如果某棵树上的水果类型不符合篮子中的水果类型，则必须停止采摘。需要计算出最多可以采摘多少个水果。

问题详解

1.初始化：我们使用两个指针left和right来表示滑动窗口的边界，同时使用一个哈希表fruit_count来记录窗口内每种水果的数量。

2.扩展窗口：从左到右扩展窗口，将right指针向右移动，将新加入窗口的水果数量记录在fruit_count中。

3.收缩窗口：如果窗口内的水果种类超过两种，我们需要收缩窗口。通过移动left指针，从窗口左侧移除水果，直到窗口内的水果种类不超过两种。

4.更新最大长度：在每次窗口调整后，更新最大长度max_length。

5.重复：重复上述过程，直到right指针遍历完整个数组。

代码

def solution(fruits: list) -> int:

    left = 0

    max_length = 0

    fruit_count = {}

    for right in range(len(fruits)):

        # 将当前水果加入窗口

        fruit = fruits[right]

        if fruit in fruit_count:

            fruit_count[fruit] += 1

        else:

            fruit_count[fruit] = 1

        # 如果窗口内的水果种类超过两种，收缩窗口

        while len(fruit_count) > 2:

            left_fruit = fruits[left]

            fruit_count[left_fruit] -= 1

            if fruit_count[left_fruit] == 0:

                del fruit_count[left_fruit]

            left += 1

        # 更新最大长度

        max_length = max(max_length, right - left + 1)

      return max_length

if name == 'main':

    print(solution([1, 2, 1, 2]) == 4)

    print(solution([2, 0, 1, 2, 2]) == 3)

    print(solution([1, 2, 3, 2, 2, 4]) == 4)

代码详解

1.初始化

left = 0：初始化滑动窗口的左边界。

max_length = 0：用于记录最大采摘长度。

fruit_count = {}：字典用于记录窗口内每种水果的数量。

2.滑动窗口操作

外层循环for right in range(len(fruits)):通过right来扩展窗口。

每次将fruits[right]加入窗口：

如果fruit已经在fruit_count中，fruit_count[fruit] += 1增加其数量；否则，fruit_count[fruit] = 1初始化其数量为 1。

当窗口内水果种类超过两种时：

通过while len(fruit_count)> 2:来收缩窗口。

将fruits[left]从窗口中移除，fruit_count[left_fruit] -= 1减少其数量，如果数量为 0，则del fruit_count[left_fruit]从字典中删除该水果记录，然后left += 1移动左边界。

3.更新最大长度

max_length = max(max_length, right - left + 1)在每次移动right后，更新最大采摘长度。

4.主程序测试

在if name == 'main':部分，对solution函数进行了测试，分别传入了题目中给出的三组测试数据，验证函数返回值是否正确。

知识总结

这个问题涉及到了滑动窗口算法和哈希表的使用。滑动窗口算法是一种非常实用的算法，它在处理数组相关问题时，可以大大减少时间复杂度。哈希表则提供了快速查找和更新元素的能力，使得我们能够高效地管理窗口内的水果种类。

对于入门同学，不仅要关注代码的正确性，还要思考算法的效率和可读性。尝试不同的方法来解决问题，并比较它们的优劣。同时，不要忽视基础知识的学习，因为它们是解决复杂问题的基础。

工具运用

豆包MarsCode AI刷题功能提供了丰富的题目资源和智能化的指导，可以帮助用户更高效地学习。结合其他学习资源，如在线教程、视频讲解等，可以进一步丰富学习体验，提高学习效果。

相关知识

豆包MarsCode AI 刷题——农场采摘水果问题
题解：农场采摘水果问题
用AI把电商玩出花？豆包深度思考大模型将为商家带来惊喜
分享：前端开发使用的各类 AI Copilot 辅助开发
文章不存在或已删除,返回看看别的文章吧
合肥三十岗桃蹊水果农场采摘攻略
为了「水果自由」，AI 也很努力。
Flat Ads：透视中国AI出海战略，看豆包、腾讯元宝、美图相机如何占领市场先机
合肥三十岗桃蹊水果农场桑葚采摘指南
宿迁：来生态农场 体验“一站式”采摘

网址: 豆包MarsCode AI 刷题——农场采摘水果问题 https://www.huajiangbk.com/newsview2380053.html