首页 > 其他分享 >力扣 904. 水果成篮 的解法

力扣 904. 水果成篮 的解法

时间:2023-07-15 23:34:53浏览次数:41  
标签:水果 right 904 max 力扣 终点 fruits 成篮 种类

分析题目

原题如下:

你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:

  • 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
  • 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。

给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。

然后我们来分析一下题目:

  1. 我们的目标是什么?对,“收集的水果的 最大 数目。”。
    翻译成人话就是,本题要求我们在限定条件下收集到最多的水果数量。

  2. 目标有了,那现在让我们来把抽象的条件具象化。

    1. 收集的水果种类最多只能有两种
    2. 不能回头重新收集,也就是:要连续进行收集
  3. 那么现在总结一下就是,题目问我们最多连续收集多少个两种种类的水果?

解题思路

现在题目能理解了,就要开始思考解题思路了。
如上所述,关键点是:“最多”“连续”和“两种

那么现在我们可以想到这样一个思路:因为要连续收集两种不同的水果,所以我们可以想到用指针来指向起点终点,通过遍历果树的同时增大指针终点,使得起点终点之间的间隔尽可能大,从而得到一个最大的结果。

看起来没有问题,所以现在就是要想具体的解决方案了:

  1. 既然要用指针指向起点和终点了,那肯定就要先决定变量了,所以用 left 指向起点,right 指向终点。
  2. 那现在问题来了,要怎么移动终点呢?很明显,用循环来遍历每颗果树,然后遍历到了哪颗果树,终点就在哪。
  3. 最后,用 max 来储存right(终点)-left(起点)的值,就是能摘到水果的最大值了!
  4. 等等,好像有哪里不对?既然有最大值,那也应该会有不是最大值的值吧?为什么这里没有出现?噢!水果的种类不止两种,是可能出现第三种甚至第四种的!
  5. 所以现在问题又来了,我们要怎么确定自己取得的值是仅限两种水果的呢?哎有了,只要出现了第三种水果了,那就放弃掉原先第一种水果不就行了?也就是让(原)第二种水果成为(现)第一种水果,(原)第三种水果成为(现)第二种水果,那就又是仅限两种水果了!
  6. 不过还有问题,那连续摘取两种水果的最大值 max 要怎么办啊?so easy~对比不就好了?只要每次遍历果树时,都把现在这两种水果所取得的最大值赋值给 n ,然后再让 n 跟 max 比大小就行了!
  7. 看起来真是完美呢,肯定能直接运行了吧!哎,什么?还有BUG?不可能吧?在哪里?哈?每次换水果种类的时候,起点要定在哪?笨哎你,直接定在之前的终点不就行了!直接就是一个顿挫,完美~
  8. 不可以的啦!直接定在终点的话,那如果原先那两个种类的水果是连续的要怎么办?就像“2,1,1,1,3”,那是不是就要把前两个“1”给扔掉了?那是不是就会漏掉几个水果了?
  9. 所以我的解决方法就是:用 z 来存储连续的水果个数,然后换种类的时候再把 z 加上去!具体实施就是在每次遍历果树的时候,顺带匹配一下当前水果的种类跟上一个水果的种类是否一样,一样的话就使得 z+=1,否则就让 z=1,也就是连续的个数就是 1。这下就是真正的完美了~

如上就是具体的解题思路了,以下是代码:

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
		# 用 a 来存储水果种类1,用 b 来存储水果种类2,然后又因为不知道第二个种类的水果什么时候才会出现,甚至不知道会不会有第二个种类的水果,所以就把 b 设为-1了,
        a,b,max=fruits[0],-1,1

		# left 是起点的意思,起点必然是0,这个不用多说了吧?然后 z 是最后水果的连续出现的个数,最少都是 1.
        left,z=0,1
        size = len(fruits)
        for right in range(1,size):
			# 如果没有出现过第二种种类的水果且这个水果跟 a 不符,就把这个水果赋值给 b(第二种水果的种类)
            if b==-1 and fruits[right]!=a:
                b=fruits[right]

			# 这里应该不用多说?就是最新出现的水果是与众不同的第三种水果的时候执行啦~
            elif fruits[right]!=a and fruits[right]!=b:
				# 这里应该也能理解?就是1. 起点=终点-连续值;2. 把最新出现的水果种类和上一个水果种类重新赋值给a,b
                left=right-z
                a=fruits[right-1]
                b=fruits[right]
            if fruits[right]==fruits[right-1]:
                z+=1
            else:
                z=1
            n=right-left+1
            if n>max:
                max=n
        return max

		# 后面好像也没什么好说的了,都在解题思路里说的很清楚了。

标签:水果,right,904,max,力扣,终点,fruits,成篮,种类
From: https://www.cnblogs.com/aduiduidui/p/17557228.html

相关文章

  • 刷力扣高频SQL50题(基础)总结
    此随笔仅总结个人刷SQL题时,突然不会使用的某函数或某方法,大佬勿看勿喷regexp'正则表达式'一般用于邮箱校验例题:查找拥有有效邮箱的用户select*fromuserswheremailregexp'^[a-zA-Z]+[a-zA-Z0-9_\\./\\-]*@leetcode\\.com$'窗口函数窗口函数讲解函数+over(pa......
  • 力扣---931. 下降路径最小和
    给你一个 nxn 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)......
  • 力扣-旋转链表
    1.问题描述给定一个链表,旋转链表,将链表每个节点向右移动k个位置,其中k是非负数。示例1:输入:1->2->3->4->5->NULL,k=2输出:4->5->1->2->3->NULL解释:向右旋转1步:5->1->2->3->4->NULL向右旋转2步:4->5->1->2->3->NULL 示例2:输入:0->1-&g......
  • 力扣---1911. 最大子序列交替和
    一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。比方说,数组 [4,2,5,3] 的交替和为 (4+5)-(2+3)=4 。给你一个数组 nums ,请你返回 nums 中任意子序列的 最大交替和 (子序列的下标 重新 从0开始......
  • 力扣231、326 2的幂,3的幂
    示例1:输入:n=1输出:true解释:20=1示例2:输入:n=16输出:true解释:24=16示例3:输入:n=3输出:false示例4:输入:n=4输出:true示例5:输入:n=5输出:false思考:考虑到是找二的幂,那就是换成二进制,令n与n-1相与,如果是0说明是2的幂,如果不是,就要返回False。classS......
  • 不忘初心 Windows10 22H2 19045.3155 x64 无更新 纯净 深度精简 2023.7.9
    注意此版不能更新补丁,支持人脸和指纹,此为深度精简版体积小、精简的比较多,适合软件不多的朋友使用,可以安装商店、以及其他UWP程序,可以登录微软账号。如有第三方软件打不开,请自行安装资源包里的微软常用运行库,为了保证稳定初心的系统全部都是离线精简和优化,非二次封装。系统纯净、流......
  • 最完美WIN10_Pro_22H2.19045.3155软件选装纯净版VIP50.7
    【系统简介】=============================================================1.本次更新母盘来自UUP_WIN10_PRO_22H2.19045.3155。进一步精简优化调整。2.只为呈现最好的作品,手工精简优化部分较多。3.OS版本号为19045.3155。个别要求高的就下MSDN吧,里面啥功能都有。4.集成《DrvCeo......
  • 查字符类型转换date类型值时报错“ORA-00904: "GET_INTERNAL_VALUE": invalid identif
    问题描述:查字符类型转换date类型值时报错“ORA-00904:"GET_INTERNAL_VALUE":invalididentifier”,如下所示:数据库:oracle11.2.0.41、异常重现SYS@orcl>selectget_internal_value('DF2304290000748902')fromdual;selectget_internal_value('DF2304290000748902......
  • 力扣11. 盛最多水的容器
    题目:给定一个长度为n的整数数组 height 。有 n 条垂线,第i条线的两个端点是 (i,0) 和 (i,height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明:你不能倾斜容器。 示例1: 输入:[1,8,6,2,5,4,8,......
  • 力扣605. 种花问题
    题目:假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。给你一个整数数组 flowerbed表示花坛,由若干0和1组成,其中0表示没种植花,1表示种植了花。另有一个数 n,能否在不打破种植规则的情况下种入 n 朵......