首页 > 其他分享 >904. 水果成蓝

904. 水果成蓝

时间:2024-11-11 21:18:50浏览次数:3  
标签:水果 right 904 int cnt 成蓝 ++ second fruits

题目

自己第一次写的,结果超时了

class Solution
{
public:
    int totalFruit(vector<int> &fruits)
    {
        int r = 1;
        int res = 1;
        while (r < fruits.size())
        {
            int l = r - 1;
            int n = 1;  // 代表不同的种类个数
            int second = -1;
            while (n <= 2 && l >= 0)
            {
                if (fruits[l] == fruits[r] || fruits[l] == second)
                    l--;
                else
                {
                    n++;
                    if (n <= 2)
                    {
                        second = fruits[l]; // 记录第二个种类,第一个种类其实是fruits[r]

                        l--;
                    }
                }
            }
            res = max(res, r - l);
            r++;
        }
        return res;
    }
};

我的思想中为什么要让l--放在if (n <= 2)里面而不是外面?

因为我想的是让当r固定时,r最后指向的是从r往左走第一个不满足条件的位置(即不满足水果种类数不超过两种),然后计算的长度就是r-l

其实在写的时候就隐隐感觉会超时,因为l肯定不应该从r-1开始回溯,但是又想不到别的方法(其实想到了应该要用滑动窗口,但是具体的细节没想清楚,不知道如何下手)。

看了官方题解,果然是滑动窗口

img

代码如下:

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        unordered_map<int, int> cnt;

        int left = 0, ans = 0;
        for (int right = 0; right < n; ++right) {
            ++cnt[fruits[right]];
            while (cnt.size() > 2) {
                auto it = cnt.find(fruits[left]);
                --it->second;
                if (it->second == 0) {
                    cnt.erase(it);
                }
                ++left;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

这个滑动窗口维持的性质:这个窗口内的水果种类不超过两种。

标签:水果,right,904,int,cnt,成蓝,++,second,fruits
From: https://www.cnblogs.com/hisun9/p/18540603

相关文章

  • 【优选算法 — 滑动窗口】水果成篮 & 找到字符串中所有字母异位词
         水果成篮  水果成篮  题目描述  因为只有两个篮子,每个篮子装的水果种类相同,如果从0开始摘,则只能摘0和1两个种类;因为当我们在两个果篮都装有水果的情况下,如果再走到下一颗果树,果树的水果种类不是果篮中的任意一种,则停止采摘;所以就是要找......
  • Java 基于 SpringBoot+Vue 的水果在线销售系统开发(附源码,文档)
    博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w+、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌......
  • 2024.0904模拟赛反思总结
    9:00~9:25老师不发卷是在考验我们的心态吗。9:25~10:00总体看了一眼题目,\(A\)题貌似做过,\(B\)题推公式,\(C\)题简单最短路,\(D\)题构造。\(A\)题一开始我想的全部设为\(0\),算汉明距离从后往前调整\(1\),赛时写挂了,赛后发现两个字符串的汉明距离实时调整的时候写错了。10:......
  • P11236 「KTSC 2024 R1」水果游戏 题解
    很有意思的一道题。思路首先将相邻一样的数合并,每个元素变成一个二元组,表示数与出现次数。考虑什么时候不能合并。我们发现假如充分合并后,现在有连续的三个数\(x_1,x_2,x_3\),以及他们各自的出现次数\(y_1,y_2,y_3\)。如果\(x_1>x_2,x_3>x_2\)。我们想要合并这三个,必须要......
  • PHP水果销售系统-计算机毕业设计源码01845
    目 录摘要1绪论1.1研究背景1.2研究意义1.3论文结构与章节安排2 水果销售系统系统分析2.1可行性分析2.2系统流程分析2.2.1数据流程3.3.2业务流程2.3系统功能分析2.3.1功能性分析2.3.2非功能性分析2.4系统用例分析2.5本章小结3水果......
  • 保姆级教程 | 小某书爆款新赛道,水晶水果新玩法,AI带你轻松涨粉!
    这两天刷小红书,发现了一个新奇的赛道,感觉蛮不错的,满足了小红书里面大部女生的少女心。这种图片制作简单,涨粉也不难。置顶的这两张苹果和水晶橘子,很吸引观众眼球!苹果透亮透亮的,橘子看着非常可口,十分治愈。这份完整版的AI绘画全套学习资料已经上传CSDN,朋友们如果需要可......
  • 【水果识别】水果虫灾检测【含GUI Matlab源码 8966期】
    ......
  • 基于数字图像的水果边缘检测方法研究
    基于数字图像的水果边缘检测方法研究1绪论1.1课题研究的背景我国水果品种繁多,资源丰富。作为一项新兴产业,在农业和农村经济发展中的地位已经十分重要,在很多地区己成为农村经济的支柱产业。纵观 世界水果园科技的发展, 二十一世纪我国的水果园也将从传统作业转化到以现......
  • 【Linux】巧妙运用<信号量>解决<水果放取问题>(思维导图&代码演示&思路解析)
    前言大家好吖,欢迎来到YY滴Linux系列,热烈欢迎!本章主要内容面向接触过C++的老铁主要内容含:欢迎订阅YY滴C++专栏!更多干货持续更新!以下是传送门!YY的《C++》专栏YY的《C++11》专栏YY的《Linux》专栏YY的《数据结构》专栏YY的《C语言基础》专栏YY的《初学者易错点》......
  • 几十种水果蔬菜数据集下载地址汇总
    几十种水果蔬菜数据集下载地址汇总:名称【分类数据集】水果和蔬菜图像识别数据集3115张36种.7z【图片分类数据集】腰果成熟度分类数据集900张3类.zip【目标检测数据集】香蕉检测数据集3550张VOC+YOLO张.zip【目标检测】小辣椒小彩椒检测数据集2292张3类别.7z【目标检测】香蕉......