首页 > 其他分享 >滑动窗口系列(定长滑动窗口长度)8/31

滑动窗口系列(定长滑动窗口长度)8/31

时间:2024-08-31 13:25:02浏览次数:14  
标签:map right 窗口 nums int 31 数组 滑动 left

1.长度为K子数组中的最大和

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和:

  • 子数组的长度是 k,且
  • 子数组中的所有元素 各不相同 
题意:

在之前题目的基础上添加了一个条件:子数组中的所有元素各不相同 。

因此在这里使用哈希表记录元素出现的次数

思路:

在循环中

1.首先要判断该数字之前是否出现过? 如果出现过,就要将滑动窗口的左边界移动到该数字的下一个。

            while (map.getOrDefault(nums[right], 0) != 0) {
                map.put(nums[left], map.get(nums[left]) - 1);
                sum -= nums[left];
                left++;
            }

2.然后sum累计求和(第一步中判断了没有出现过才加的),如果滑动窗口的长度==k,此时更新一下最大值,然后移动滑动窗口的左边界并且更新一下哈希表;

            sum += nums[right];
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            if (right - left + 1 == k) {
                max = Math.max(max, sum);
                sum -= nums[left];
                map.put(nums[left], map.get(nums[left]) - 1);
                left++;
            }

3.返回最大值

代码:
 class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        long max = 0;
        int left = 0;
        int right = 0;
        long sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        while (right < nums.length) {
            while (map.getOrDefault(nums[right], 0) != 0) {
                map.put(nums[left], map.get(nums[left]) - 1);
                sum -= nums[left];
                left++;
            }
            sum += nums[right];
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            if (right - left + 1 == k) {
                max = Math.max(max, sum);
                sum -= nums[left];
                map.put(nums[left], map.get(nums[left]) - 1);
                left++;
            }
            right++;
        }
        return max;
    }
}

2.爱生气的书店老板(有点绕)

题意:

有一个书店,开了n分钟,每一分钟会进x个人,用数组customers表示;这老板脾气有点大,每一分钟可能会生气,用数组grumpy表示;如果生气的话,顾客就会不满意;但是老板有一个秘诀,会抑制生气,只能抑制minutes分钟;求n分钟最多满意的顾客有多少人?

输入:customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出:16
解释:书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
思路:

1.首先假设不会抑制情绪,那么顾客数为最少的,人数记为basic;

   for(int i=0;i<customers.length;i++){
            if(grumpy[i]==0)basic+=customers[i];
        }

2.选择在何时抑制情绪,这里可以使用滑动窗口的思路;

   2.1 遍历数组,如果该分钟老板是生气的,那么顾客数就要在basic的基础上增加

   2.2 然后要判断滑动窗口的长度,如果==minutes,那么就要更新最大值,并且更新滑动窗口的边           界    

        while(right<customers.length){
            if(grumpy[right]==1)basic+=customers[right];
            if(right-left+1==minutes){
                max=Math.max(max,basic);
                if(grumpy[left]==1)basic-=customers[left];
                left++;
            }
            right++;
        }
代码:
class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int left=0;
        int right=0;
        int max=Integer.MIN_VALUE;
        int basic=0;
        for(int i=0;i<customers.length;i++){
            if(grumpy[i]==0)basic+=customers[i];
        }
        while(right<customers.length){
            if(grumpy[right]==1)basic+=customers[right];
            if(right-left+1==minutes){
                max=Math.max(max,basic);
                if(grumpy[left]==1)basic-=customers[left];
                left++;
            }
            right++;
        }
        return max;
    }
}

3.子串出现的最大次数()

题意:

给你一个字符串 s ,请你返回满足以下条件且出现次数最大的 任意 子串的出现次数:

  • 子串中不同字母的数目必须小于等于 maxLetters 。
  • 子串的长度必须大于等于 minSize 且小于等于 maxSize 。
输入:s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
输出:2
解释:子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求:2 个不同的字母,长度为 3 (在 minSize 和 maxSize 范围内)。
思路:只需要看minSize就可以,因为长度为maxSize的字符串一定是覆盖长度为minSIze的字符串的;eg:bcdabcdabcdabc minSize=3 maxSize=4 abcd会出现3次,abcd出现abc一定出现;

因此这道题就变成了,滑动窗口长度为minSize,寻找不同字母的数量要<=maxLetters的字符串。这个字符串可能有多个,返回一个数量最多的。

代码:
class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        int left=0;
        int right=0;
        int count=0;
        int max=0;
        Map<Character,Integer> map1=new HashMap<>();//记录滑动窗口中出现字母的次数
        Map<String,Integer> map2=new HashMap<>();//记录符合字符串出现的次数
        while(right<s.length()){
            char ch=s.charAt(right);
            if(map1.getOrDefault(ch,0)==0)count++;
            map1.put(ch,map1.getOrDefault(ch,0)+1);
            if(right-left+1==minSize){
                if(count<=maxLetters){
                    String str=s.substring(left,right+1);
                    map2.put(str,map2.getOrDefault(str,0)+1);
                    max=Math.max(max,map2.get(str));
                }
                map1.put(s.charAt(left),map1.get(s.charAt(left))-1);
                if(map1.get(s.charAt(left))==0)count--;
                left++;
            }
            right++;
        }
        return max;
    }
}

4.最小交换次数来组合所有的1 II

题意:

交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。

环形 数组是一个数组,可以认为 第一个 元素和 最后一个 元素 相邻 。

给你一个 二进制环形 数组 nums ,返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。

思路:

要组合所有的1,我们可以将滑动窗口的长度设置为1的个数;

如果滑动窗口中0的个数为0:就不需要交换,交换次数为0;

如果滑动窗口中0的个数为1:就需要将1和这个0交换,交换次数为1;

因此,0的个数就是需要交换的个数;

因此只需要使用滑动窗口判断里面0的个数即可。并且更新最小值;

注意:是循环数组

left和right的增加都需要对size取余

代码:
class Solution {
    public int minSwaps(int[] nums) {
        //计算窗口的长度(数组中1的个数就是窗口的长度)
        int windowSize=0;
        for(int num:nums)if(num==1)windowSize++;

        int left=0;
        int right=0;
        int res=Integer.MAX_VALUE;
        int count=0;
        int index=0;
        while(index<windowSize+nums.length-1){
            if(nums[right]==0)count++;
            if(right-left+1==windowSize||right+nums.length-left+1==windowSize){
                res=Math.min(res,count);
                if(nums[left]==0)count--;
                
                left=(left+1)%nums.length;
            }
            right=(right+1)%nums.length;
            index++;
        }
        return res==Integer.MAX_VALUE?0:res;
    }
}

标签:map,right,窗口,nums,int,31,数组,滑动,left
From: https://blog.csdn.net/2301_78191305/article/details/141740061

相关文章

  • 滑动窗口系列(定长滑动窗口长度) 8/30
    1.所有数对中数位差之和()题意:给定一个nums数组,计算中所有整数数对中数位差的个数之和;数位差:某一位上的数字不一样就记作数位差。eg:1222;十位上不一样,数位差为1思路:首先计算出一个数字有多少位(题目中给出所有数字的位数都相同这个条件)然后统计每一位上0-9的个数......
  • 2024/08/31 每日一题
    LeetCode3127构造相同颜色的正方形方法1:模拟classSolution{publicbooleancanMakeSquare(char[][]grid){for(inti=0;i<2;i++){for(intj=0;j<2;j++){intcnt=0;//统计黑色数量cnt+=......
  • VBA语言専攻简介0831
    VBA语言専攻简介0831在当今世界,几乎没有任何工作是没有计算机的。有些工作需要定期重复相同的过程,最好将它们自动化。一旦任务自动化,只需单击一个按钮即可运行。VBA是实现自动化工作的最为简单的方式,它不需要其他工具,因为它已经与MicrosoftOffice软件集成。VBA是VisualBasicfor......
  • Linux学习(15)-网络编程:滑动窗口、拥塞控制、udp
    本节学习内容1.滑动窗口(1.滑动窗口的作用2.如果如果接收端填充的接收窗口为0,发送端接下来怎么处理3.糊涂窗口综合征4.tcp中nagle算法是什么)2.拥塞控制3.udp协议特点及编程流程本节可能会用到的指令ifconfig查看自己的ip地址ping+ip地址验证通信是否连接netstat-natp显......
  • 谷歌浏览器如何设置允许弹出窗口
    在谷歌浏览器中设置允许窗口弹出,可以方便我们及时收到重要的信息提示。很多用户在使用谷歌浏览器进行网页活动时,偶尔会出现没有弹窗提醒的情况,这样会影响我们的使用进程。下面就给大家分享一下谷歌浏览器设置允许弹出窗口的操作步骤,希望帮助大家解决问题。谷歌浏览器设置允许......
  • 【STM32】IWDG独立看门狗与WWDG窗口看门狗
    本篇博客重点在于标准库函数的理解与使用,搭建一个框架便于快速开发目录WDG简介IWDGIWDG特性独立看门狗时钟键寄存器超时时间 IWDG代码WWDGWWDG特性窗口看门狗时钟超时时间WWDG时序WWDG代码 IWDG和WWDG对比 WDG简介WDG(Watchdog)看门狗,可以监控程序的运......
  • 信息学奥赛一本通1314:【例3.6】过河卒(Noip2002)
    【题目描述】棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上的某一点有一个对方的马(如C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点,如图3-1中的C点和P1,……,P8,卒不能通过对方马的控制点。棋盘用坐标表示,A点(0,0)、B点(n,......
  • 3D高斯渲染 (1)手动窗口可视化
       ##Copyright(C)2023,Inria#GRAPHDECOresearchgroup,https://team.inria.fr/graphdeco#Allrightsreserved.##Thissoftwareisfreefornon-commercial,researchandevaluationuse#underthetermsoftheLICENSE.mdfile.##Forinquirie......
  • 解决方案 | IrfanView如何滑动滚轮图像缩放?
    这是个bug,已经很多人反映了。目前没有比较好的解决方法,还是使用ctrl+滚轮最好。如果需要设置滚轮放大的话,按照下图即可,但是带来一个bug,你无法通过方向键或者菜单的箭头浏览下一张图片。综上所述,你有3个选择,1接受使用ctrl+滚轮进行放大2设置--关闭”显示所有支持的文件/缩略图......
  • 单调队列--滑动窗口最大值(leetcode23)
    目录一、单调队列介绍二、题目应用1.题目描述2.解题碎碎念3.代码示例三、扩展1.与优先队列区别2.单调队列其他题目一、单调队列介绍单调队列是一种特殊的队列数据结构,它能够在常数时间内找到队列中的最值。单调队列可以用来解决一些与最值相关的问题,例如滑动窗口最......