力扣904 水果成篮--滑动窗口+哈希表

这篇具有很好参考价值的文章主要介绍了力扣904 水果成篮--滑动窗口+哈希表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

点击跳转力扣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

思路:

该题的意思是找出数组中两种水果所包含的最大数量,我们可以用一个哈希表来存储水果种类跟水果数量,当水果种类大于2时,移除一些'水果'

class Solution {
public:
    int totalFruit(vector<int> &fruits) {

        // 窗口长度、起始指针、当前果树种类计数
        int wl = 0, i = 0, cnt = 0, len = fruits.size();
        // 果篮
        unordered_map<int, int> basket;//哈希表

        // 终止指针遍历数组,
        for (int j = 0; j < len; ++j) {
            // 遇到果篮里没有的种类,窗口数量+1,水果总数+1
            if (basket[fruits[j]] == 0)cnt++;
            basket[fruits[j]]++;
            while (cnt > 2) {
                basket[fruits[i]]--;
                // 果篮数大于2,则向右移动初始指针,缩小滑动窗口,更新水果总数,保证种类为2的情况下,窗口最大化.
                if (basket[fruits[i]] == 0)cnt--;
                i++;
            }
            wl = max(wl, j - i + 1);
        }
        return wl;
    }
};


总结:

unordered_map函数,我简单一点理解就是哈希表,详细可以参考https://blog.csdn.net/hk2291976/article/details/51037095

补充:

这里补充一个知识点----滑动窗口:就是不断的调节子序列的起始位置和终止位置,从而得出结果.

实现滑动窗口的框架是定死的,用left,right来刻画窗口,窗口区间为[left, right),注意为半开半闭。框架如下:

void slidwindow(vector<int> nums)
{
    int left = 0, right = 0;
    while(right < nums.size())
    {
        ...//扩大右边界并更新窗口状态
        right++;
        while(需要收缩)//窗口到达什么状态需要收缩
        {
            ...//缩小左边界并更新窗口状态
            left++;
        }
    }
}

//以上框架来自力扣题解:凯巴尔我的超人


以力扣209为例:209. 长度最小的子数组 - 力扣(LeetCode)

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度如果不存在符合条件的子数组,返回 0 。

示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:

输入:target = 4, nums = [1,4,4]
输出:1

示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

思路:

在本题中实现滑动窗口,主要确定如下三点:

  • 窗口内是什么?
  • 如何移动窗口的起始位置?
  • 如何移动窗口的结束位置?

窗口就是 满足其和 ≥ s 的长度最小的连续子数组。

窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。

窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。

解题的关键在于 窗口的起始位置如何移动,如图所示:

力扣904 水果成篮--滑动窗口+哈希表,leetcode,散列表,算法

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)
            }
        }
        // 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

以上解题思路来自<<代码随想录>>,有相关疑惑,可以去b站看up的讲解视频.下面讲一下我自己的思路,我个人认为更好理解这个代码思想.

我的思路是先算出数组的前缀和,当前缀和大于目标数时,减去数组左边的数,一直减到前缀和小于目标数,更新左指针,一旦前缀和小于目标数,则加上左指针所在的数,重复此操作,不断更新ans,直到该区间内为目标数的最小序列.

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n=nums.size();
        int s=0,left=0,ans=n+1;
        for(int i=0;i<n;i++){
            s=s+nums[i];
            if(s>=target){
                while(left<=i){
                    s=s-nums[left];
                    if(s>=target){
                        left++;
                    }else{
                        s=s+nums[left];
                        ans=min(ans,i-left+1);
                        break;
                    }
                }
            }
        }
        if(ans!=n+1) return ans;
        else return 0;

    }
};

总结

滑动窗口的重要性是确定起始指针跟终止指针的位置,用一个for循环解决两个for循环的问题(类似于双指针)文章来源地址https://www.toymoban.com/news/detail-826930.html

到了这里,关于力扣904 水果成篮--滑动窗口+哈希表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法挨揍日记】day07——904. 水果成篮、438. 找到字符串中所有字母异位词

    904. 水果成篮 你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组  fruits  表示,其中  fruits[i]  是第  i  棵树上的水果  种类  。 你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果: 你只有  两个

    2024年02月07日
    浏览(39)
  • 【LeetCode:30. 串联所有单词的子串 | 滑动窗口 + 哈希表】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年01月21日
    浏览(63)
  • leetcode(力扣) 76. 最小覆盖子串 (滑动窗口,超详细问答版解析)

    给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保证它是

    2024年02月08日
    浏览(51)
  • 【双指针】滑动窗口经典例题 力扣

    无重复的最长子串LC3 中等 题目链接 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 代码: 找到字符串中所有子母异位词LC438 中等 题目链接 给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序

    2024年02月07日
    浏览(44)
  • 力扣刷题-队列-滑动窗口最大值

    给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 进阶: 在线性时间复杂度内解决此题? 参考:https://www.programmercarl.com/0239.%E6%BB%91%E5%8A

    2024年02月06日
    浏览(50)
  • 力扣热门100题之滑动窗口最大值【困难】

    给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1: 输入:nums = [1,3,-1,-3,5,3,6,7], k = 3 输出:[3,3,5,5,6,7] 解释: 滑动窗口的位置

    2024年02月16日
    浏览(43)
  • 【map】【滑动窗口】【优先队列】LeetCode480滑动窗口中位数

    动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本 C++算法:滑动窗口总结 map 优先队列 中位数是有序序列最中间的那个数。如果序列的长度是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。 例如: [2,3,4],中位数是 3 [2,3],中位数是 (2 + 3) / 2 =

    2024年02月03日
    浏览(42)
  • rust踩雷笔记(2)——一道hard带来的思考[哈希表、字符串、滑动窗口]

    今天被一道hard恶心坏了,算法不难,用C++几分钟的事。用rust主要还是缺乏对语言的熟练度,记录一下,主要的坑在下面这个操作: 对String取其中某个位置的char。 可能你会有疑问:这不是直接nth()取就行了么。没错,我看有些题解也是这样做的,但是那样会在某些字符长度很

    2024年02月12日
    浏览(35)
  • 力扣日记10.30-【栈与队列篇】滑动窗口最大值

    日期:2023.10.30 参考:代码随想录、力扣 题目描述 难度:困难 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1: 示例 2:

    2024年02月06日
    浏览(46)
  • leetcode—滑动窗口

    给定一个字符串  s  ,请你找出其中不含有重复字符的  最长子串  的长度。 示例 1: 滑动窗口 使用两个指针 表示字符串中某个子串的左右边界【i, right】 在每一步的操作中,将左指针i 向右移动一位,表示开始枚举下一个字符作为起始位置,然后不断的向右移动右指针(

    2024年01月17日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包