水果篮一般装几种水果_one step closer水果篮子

水果篮一般装几种水果_one step closer水果篮子904.水果成篮题目描述题目链接:904水果成蓝你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组fruits表示,其中fruits[i]是第i棵树上的水果种类。你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:你只有两个篮子,并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘,你必须从每棵树(包括开始采摘的树)上恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

904. 水果成篮

题目描述

题目链接:904水果成蓝
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:
你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。

解题思路

树由整数数组fruits表示,其中水果[i]是第i棵树产生的水果类型。 你想收集尽可能多的水果。但是,所有者有一些严格的规则,您必须遵守: 你只有两个篮子,每个篮子只能装一种水果。每篮水果的数量没有限制。 从您选择的任何一棵树开始,您必须在向右移动时从每棵树(包括起始树)中恰好摘下一个水果,摘下的水果必须放在你的一个篮子里。 一旦你到了一棵树上,树上的果实没法放入你的篮子(两个篮子已经满了),你必须停下来。 给定整数数组水果,返回可以拾取的最大水果数。 本题,其实就是选只有两个元素的最长连续子序列,比如1,2,3,2,2最长就是2,3,2,2(只包括2或者3,而且是最长的)。

代码演示–暴力解法

def totalFruit(fruits):
    """ :type fruits: List[int] :rtype: int """
    res = 0
    num = []

    for i in range(len(fruits)):
       j = i
        while (len(set(num)) <= 2 and j < len(fruits)):
            num.append(fruits[j])
            j += 1

        if(len(set(num)) <= 2 ):
            res = max(res, len(num))
        elif(len(set(num)) == 3):
            res = max(res,len(num) - 1)


        del num[:]

    return res



# fruits = [1,2,1]
# fruits = [0,1,2,2]
# fruits = [1,2,3,2,2]
# fruits = [3,3,3,1,2,1,1,2,3,3,4]
fruits =   [1,1]
r = totalFruit(fruits)
print(r)

超时间限制,呜呜呜

代码演示–滑动窗口

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        if(len(fruits) == 1 or len(fruits) == 2):
            return len(fruits)
        
        # 记录当前篮子里的水果
        basket1 = -1
        basket2 = -1
        sum = 0
        # 记录当前的水果和当前水果的起始位置
        curfruit = -1
        curfruitloc = 0
        subsum = 0

        # 当前篮子起始位置
        index = 0

        for i in range(len(fruits)):
            if(fruits[i] == basket1 or fruits[i] == basket2):
                if(fruits[i] != curfruit):
                    curfruit = fruits[i]
                    curfruitloc = i
            else:
                index = curfruitloc
                curfruitloc = i
                if(basket1 == curfruit):
                    basket2 = fruits[i]
                    curfruit = basket2
                else:
                    basket1 = fruits[i]
                    curfruit = basket1
            subsum = i - index + 1
            sum = sum if sum > subsum else subsum
        return sum

在这里插入图片描述

参考

链接:https://leetcode-cn.com/problems/fruit-into-baskets

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/193273.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号