日拱算法,水果成篮问题

简介: 你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 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


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



目录
打赏
0
0
0
0
2
分享
相关文章
【算法专题突破】滑动窗口 - 水果成篮(13)
【算法专题突破】滑动窗口 - 水果成篮(13)
147 0
【算法挨揍日记】day07——904. 水果成篮、438. 找到字符串中所有字母异位词
题目描述: 你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。 你想要尽可能多地收集水果。然而,农场的主人设定了
378 0
水果识别系统Python+TensorFlow+Django网页界面+深度学习模型+卷积网络算法
水果识别系统,使用Python作为主要开发语言,基于深度学习TensorFlow框架,搭建卷积神经网络算法。并通过对数据集进行训练,最后得到一个识别精度较高的模型。并基于Django框架,开发网页端操作平台,实现用户上传一张图片识别其名称。
382 0
基于WOA鲸鱼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB 2022a/2024b实现,采用WOA优化的BiLSTM算法进行序列预测。核心代码包含完整中文注释与操作视频,展示从参数优化到模型训练、预测的全流程。BiLSTM通过前向与后向LSTM结合,有效捕捉序列前后文信息,解决传统RNN梯度消失问题。WOA优化超参数(如学习率、隐藏层神经元数),提升模型性能,避免局部最优解。附有运行效果图预览,最终输出预测值与实际值对比,RMSE评估精度。适合研究时序数据分析与深度学习优化的开发者参考。
基于GA遗传优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本内容包含基于BiLSTM与遗传算法(GA)的算法介绍及实现。算法通过MATLAB2022a/2024b运行,核心为优化BiLSTM超参数(如学习率、神经元数量),提升预测性能。LSTM解决传统RNN梯度问题,捕捉长期依赖;BiLSTM双向处理序列,融合前文后文信息,适合全局信息任务。附完整代码(含注释)、操作视频及无水印运行效果预览,适用于股票预测等场景,精度优于单向LSTM。
基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB2022a/2024b开发,结合粒子群优化(PSO)算法与双向长短期记忆网络(BiLSTM),用于优化序列预测任务中的模型参数。核心代码包含详细中文注释及操作视频,涵盖遗传算法优化过程、BiLSTM网络构建、训练及预测分析。通过PSO优化BiLSTM的超参数(如学习率、隐藏层神经元数等),显著提升模型捕捉长期依赖关系和上下文信息的能力,适用于气象、交通流量等场景。附有运行效果图预览,展示适应度值、RMSE变化及预测结果对比,验证方法有效性。
基于遗传算法的256QAM星座图的最优概率整形matlab仿真,对比优化前后整形星座图和误码率
本内容展示了基于GA(遗传算法)优化的256QAM概率星座整形(PCS)技术的研究与实现。通过Matlab仿真,分析了优化前后星座图和误码率(BER)的变化。256QAM采用非均匀概率分布(Maxwell-Boltzman分布)降低外圈星座点出现频率,减小平均功率并增加最小欧氏距离,从而提升传输性能。GA算法以BER为适应度函数,搜索最优整形参数v,显著降低误码率。核心程序实现了GA优化过程,包括种群初始化、选择、交叉、变异等步骤,并绘制了优化曲线。此研究有助于提高频谱效率和传输灵活性,适用于不同信道环境。
45 10
基于遗传优化ELM网络的时间序列预测算法matlab仿真
本项目实现了一种基于遗传算法优化的极限学习机(GA-ELM)网络时间序列预测方法。通过对比传统ELM与GA-ELM,验证了参数优化对非线性时间序列预测精度的提升效果。核心程序利用MATLAB 2022A完成,采用遗传算法全局搜索最优权重与偏置,结合ELM快速训练特性,显著提高模型稳定性与准确性。实验结果展示了GA-ELM在复杂数据中的优越表现,误差明显降低。此方法适用于金融、气象等领域的时间序列预测任务。

热门文章

最新文章

相关实验场景

更多
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等