• 数组07-滑动窗口、HashMap


    LeetCode——904. 水果成篮

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

    示例 4:

    输入:fruits = [3,3,3,1,2,1,1,2,3,3,4]
    输出:5
    解释:可以采摘 [1,2,1,1,2] 这五棵树。

    提示:

    • 1 <= fruits.length <= 105

    • 0 <= fruits[i] < fruits.length

    分析:

    1.题意可知,结果是找到只包含两种水果类别的最大长度子数组。算法用滑动窗口

    2.当种类大于2的时候,是新一轮迭代的开始。怎么判断窗口左边界是需要考虑的地方.如下两种情况:

    • [1,1,1,1,2,2,2,2,2,1,1,1,3]

    • [1,1,1,2,2,2,2,3]

    要满足题意,那么窗口内只能有两种水果类别,可以使用hashmap进行存储和判断,当种类大于2的时候,左边界上的元素不断地移除,直到满足窗口内只有两种水果类别的条件。

    class Solution {
        public int totalFruit(int[] fruits) {
            HashMap map = new HashMap<>();
            int l = 0;
            int res = 0;
            for (int r = 0; r < fruits.length; r++) {
                map.put(fruits[r], map.getOrDefault(fruits[r], 0) + 1);
                while (map.size() > 2){
                    map.put(fruits[l], map.get(fruits[l]) - 1);
                    if (map.get(fruits[l]) == 0) {
                        map.remove(fruits[l]);
                    }
                    l++;
                }
                res = Math.max(res, r - l + 1);
            }
            return res;
        }
    }
  • 相关阅读:
    小语种翻译软件,谷歌api接口批量翻译软件
    柔性数组详解
    流体的压力
    USB3.0 host xHCI驱动
    Java的一些内容
    Python之进程Process
    Suquel Pro连接最新版本Mysql
    目标检测论文解读复现之十一:基于特征融合与注意力的遥感图像小目标检测
    ffmpeg MP4转YUV格式保存
    浏览器:重绘(repaint)与回流/重排(reflow)
  • 原文地址:https://blog.csdn.net/Elaine2391/article/details/133352770