日拱算法,水果成篮问题

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

image.png

题目:

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

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

你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。

你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果。

采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。

一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。

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

示例 1:
输入:fruits = [1,2,1]
输出:3
解释:可以采摘全部 3 棵树。
示例 2:
输入:fruits = [0,1,2,2]
输出:3
解释:可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。
示例 3:
输入:fruits = [1,2,3,2,2]
输出:4
解释:可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘,则只能采摘 [1,2] 这两棵树。
复制代码

题目来源:水果成篮


题解:



看完题目很懵,这题这么去问多少有点毛病吧?!说 fruits[i] 是代表 i 颗树上的种类,在题解中又看到官网说:数字相同的就代表是种类相同的水果;


这样理解的话,[1,2,1] 就是 1 一类,2 一类,尽可能地包含长的子数组,但又只有两类,所以结果是 [1,2,3],长度为 3

同样的:[0,1,2,2] 就是 [1,2,2],长度为 3 ,包含了两类,1 和 2 ;


所以,其实这道题目可以理解为求只包含两种元素的最长连续子序列;

基本思路: 滑动窗口

设两个双指针 l、r,r 不断前移,只要遇到两个篮子之外的水果品种,便更新 L、篮子中的水果品种 maxLen。


例如:[0,6,6,6,1,4,4,6]

第一种水果:0,第二种水果:6,第三种水果:1。当遇到第三种水果1时,要放弃第一种水果0,这时第二种水果6要保持从索引1开始,不是3。

如果是 [0,6,0,6,1,4,4,6],遇到第三种水果 1 时要放弃第一种水果0,这时第二种水果要保持从3开始。


记录 每一次水果品种发生变化 且 是该水果品种第一次出现时的索引;

当遇到第三种水果时,n 就是上一种水果的第一次出现的起始位置,也是左指针的位置。


JavaScript 实现:

var totalFruit = function(fruits) {
    let l = 0;
    let maxLen = 0;
    let n = 0
    let arr = [fruits[l]]
    for(let r = 0; r < fruits.length; r++){
        if(!arr.includes(fruits[r])){
            if(arr.length <= 1){
                arr[1] = fruits[r]
            }else{
                l = n
                arr[0] = fruits[r-1]
                arr[1] = fruits[r]
            }
        }
        if(fruits[r] !== fruits[n]){ n = r }
        maxLen = Math.max(maxLen,r-l+1)
    }
    return maxLen
};

image.png


小结:如果面试中遇到这题不熟悉肯定很难读懂题意,转换理解为处理 包含两种元素的最长连续子序列 就好理解多了,什么水果成篮,感觉有点把实际想问的问题复杂化了。不过算法解题中,读题真的也很关键。



相关文章
|
算法
【算法专题突破】滑动窗口 - 水果成篮(13)
【算法专题突破】滑动窗口 - 水果成篮(13)
58 0
|
11月前
|
算法 测试技术 C#
C++前缀和算法的应用:摘水果 原理源码测试用例
C++前缀和算法的应用:摘水果 原理源码测试用例
|
存储 算法 索引
【算法挨揍日记】day07——904. 水果成篮、438. 找到字符串中所有字母异位词
题目描述: 你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。 你想要尽可能多地收集水果。然而,农场的主人设定了
348 0
|
机器学习/深度学习 移动开发 算法
水果识别系统Python+TensorFlow+Django网页界面+深度学习模型+卷积网络算法
水果识别系统,使用Python作为主要开发语言,基于深度学习TensorFlow框架,搭建卷积神经网络算法。并通过对数据集进行训练,最后得到一个识别精度较高的模型。并基于Django框架,开发网页端操作平台,实现用户上传一张图片识别其名称。
230 0
|
算法 开发者
再学一道算法题:水果忍者
再学一道算法题:水果忍者
再学一道算法题:水果忍者
|
15天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
2天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。
|
1天前
|
机器学习/深度学习 算法 芯片
基于GSP工具箱的NILM算法matlab仿真
基于GSP工具箱的NILM算法Matlab仿真,利用图信号处理技术解析家庭或建筑内各电器的独立功耗。GSPBox通过图的节点、边和权重矩阵表示电气系统,实现对未知数据的有效分类。系统使用MATLAB2022a版本,通过滤波或分解技术从全局能耗信号中提取子设备的功耗信息。
|
1天前
|
机器学习/深度学习 算法 5G
基于MIMO系统的SDR-AltMin混合预编码算法matlab性能仿真
基于MIMO系统的SDR-AltMin混合预编码算法通过结合半定松弛和交替最小化技术,优化大规模MIMO系统的预编码矩阵,提高信号质量。Matlab 2022a仿真结果显示,该算法能有效提升系统性能并降低计算复杂度。核心程序包括预编码和接收矩阵的设计,以及不同信噪比下的性能评估。
10 3