首页 > 其他分享 >滑动窗口系列(不定长滑动窗口长度) 9/2

滑动窗口系列(不定长滑动窗口长度) 9/2

时间:2024-09-02 13:24:38浏览次数:10  
标签:map right 窗口 nums int 数组 滑动 不定 left

一、将x减到0的最小操作数

给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ,返回 最小操作数 ;否则,返回 -1

输入:nums = [1,1,4,2,3], x = 5
输出:2
解释:最佳解决方案是移除后两个元素,将 x 减到 0 。
题意:

给定一个数组nums和一个整数x;每次操作的时候,移除左边和右边的元素,使得移除元素之和=x

思路:

一般从两边移除元素,有两种思路;

1.逆向思维,在数组中找到一个滑动窗口,和为sum-x,结果就为num.length-滑动窗口的长度

2.正向思维,前缀和后缀;

代码:
逆向思维:
class Solution {
    public int minOperations(int[] nums, int x) {
        int total = 0;
        for(int num:nums){
            total+=num;
        }
        if(total<x)return -1;
        int left=0;
        int right=0;
        int max=-1;
        int sum=0;
        while(right<nums.length){
            sum+=nums[right];
            while(sum>total-x){
                sum-=nums[left];
                left++;
            }
            if(sum==total-x){
                max=Math.max(max,right-left+1);   
            }
            right++;
        }
        return max==-1?-1:nums.length-max;
    }
}
正向思维:

二、最高频元素的频数(排序+滑动窗口)

元素的 频数 是该元素在一个数组中出现的次数。

给你一个整数数组 nums 和一个整数 k 。在一步操作中,你可以选择 nums 的一个下标,并将该下标对应元素的值增加 1 。

执行最多 k 次操作后,返回数组中最高频元素的 最大可能频数 

输入:nums = [1,2,4], k = 5
输出:3
解释:对第一个元素执行 3 次递增操作,对第二个元素执 2 次递增操作,此时 nums = [4,4,4] 。
4 是数组中最高频元素,频数是 3 。
思路:使用滑动窗口的思路(条件是操作数<=k)

当操作数>k之后,就要移动left;left需要移动到costK不大于k

       while(costK>k){
                costK-=nums[right]-nums[left];
                left++;
            }

如果<k,移动right;移动right的时候,需要更新costK,costK=(nums[right]-nums[right-1])*(right-left);因为所有的数字都变成了nums[right-1]了,然后一共有right-left个数字;

costK+=(long)(nums[right]-nums[right-1])*(right-left);

移动的过程中寻找最大值;

注意:costK的类型要是long,可能溢出

代码:
class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int left=0;
        int right=1;
        int res=1;
        long costK = 0;
        while(right<nums.length){
            costK+=(long)(nums[right]-nums[right-1])*(right-left);
            while(costK>k){
                costK-=nums[right]-nums[left];
                left++;
            }
            res=Math.max(res,right-left+1);
            right++;
        }
        return res;
    }
}

三、每种字符至少取K个

给你一个由字符 'a''b''c' 组成的字符串 s 和一个非负整数 k 。每分钟,你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符 至少 k 个,返回需要的 最少 分钟数;如果无法取到,则返回 -1 。

题意:

思路:逆向思维

题目中要求从左边或者右边取,将a\b\c三个字符取出最少K类,求最小的操作次数;

1.首先统计出字符串中字符的数目

2.然后减去k个,如果减去之后变为负数,返回-1

3.然后开始滑

逆向思维就是:题目中是否存在一段子串满足字符出现最多的次数为:count[0]-k,count[1]-k,count[2]-k。求出这段子串的最大长度

eg:"aabaaaacaabc" k=2 a:8 b:2 c:2 

然后a\b\c最多出现的次数可以为:6,0,0; 每次遍历到一个字符,就将出现的次数-1(还可以出现多少次),如果出现<0的情况,左边界就要改变了。

代码:
class Solution {
    public int takeCharacters(String s, int k) {
        if(k==0)return 0;
        // 1.统计次数
        int[] count=new int[3];
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            count[ch-'a']++;
        }
        // 2.将map中的字母-k
        for(int i=0;i<3;i++){
            if(count[i]<k)return -1;
            count[i]-=k;
        }
        //滑动窗口正文
        int left = 0;
        int right = 0;
        int res = 0;
        while (right < s.length()) {
            char ch = s.charAt(right);
            count[ch-'a']--;
            while (count[0] < 0 ||count[1] < 0 || count[2] < 0) {
                char ch1 = s.charAt(left);
                count[ch1-'a']++;
                left++;
            }
            res = Math.max(res, right - left + 1);
            right++;
        }
        return s.length() - res;
    }
}
四、找出最长等值子数组

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

如果子数组中所有元素都相等,则认为子数组是一个 等值子数组 。注意,空数组是 等值子数组 。

从 nums 中删除最多 k 个元素后,返回可能的最长等值子数组的长度。

题意: 

给定一个数组nums,求子数组中删除k个元素后,所有元素都相等,返回相同元素的最大个数。

思路:

滑动窗口左边界改变的的条件是:但滑动窗口中频率不是最大的数字的总和>k,就要移动左边界,直到总和<k;

            while (right-left+1-maxFreq > k) {
                int leftNum = nums.get(left);
                map.put(leftNum, map.get(leftNum) - 1);
                left++;
            }

每次更新map哈希表的时候,顺便获取到哈希表中出现频率最多的数字。

            int num = nums.get(right);
            map.put(num, map.getOrDefault(num, 0) + 1);
            maxFreq=Math.max(maxFreq,map.get(num));
代码:
class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int right = 0;
        int maxFreq = 0;
        int res = 1;
        while (right < nums.size()) {
            //遍历元素 将num统计到map中
            int num = nums.get(right);
            map.put(num, map.getOrDefault(num, 0) + 1);
            maxFreq=Math.max(maxFreq,map.get(num));
            //当滑动窗口中其他数字的次数>k时
            while (right-left+1-maxFreq > k) {
                int leftNum = nums.get(left);
                map.put(leftNum, map.get(leftNum) - 1);
                left++;
            }
            res=Math.max(right-left+1,res);
            right++;
        }
        return maxFreq;
    }
}

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

相关文章

  • C++中不定参数函数的实现方法
    目录一.前言二.代码解析1.模板方式第一种写法第二种写法2.va_list方式三.其他一.前言C++中实现不定参数函数可以采用多种方法,这篇文章讨论不定参数模板和va_list。二.代码解析1.模板方式C++中采用模板来实现不定参数列表,可以有多种编码的方法,这里提供两种方法。......
  • 深入理解Flink窗口
    引言我们已经了解了Flink中事件时间和水位线的概念,那它们有什么具体应用呢?当然是做基于时间的处理计算了。其中最常见的场景,就是窗口聚合计算。在流处理中,我们往往需要面对的是连续不断、无休无止的无界流,不可能等到所有所有数据都到齐了才开始处理。所以聚合计算其实只......
  • 【每日一题】LeetCode 1343.大小为K且平均值大于等于阈值的子数组数目(数组、滑动窗口)
    【每日一题】LeetCode1343.大小为K且平均值大于等于阈值的子数组数目(数组、滑动窗口)题目描述给定一个整数数组arr和两个整数k和threshold,要求找出数组中长度为k且平均值大于等于threshold的子数组的数量。输入格式arr:一个整数数组。k:子数组的长度。thres......
  • 滑动窗口系列(定长滑动窗口长度)8/31
    1.长度为K子数组中的最大和给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和:子数组的长度是 k,且子数组中的所有元素 各不相同 题意:在之前题目的基础上添加了一个条件:子数组中的所有元素各不相同。因此在这里使......
  • 滑动窗口系列(定长滑动窗口长度) 8/30
    1.所有数对中数位差之和()题意:给定一个nums数组,计算中所有整数数对中数位差的个数之和;数位差:某一位上的数字不一样就记作数位差。eg:1222;十位上不一样,数位差为1思路:首先计算出一个数字有多少位(题目中给出所有数字的位数都相同这个条件)然后统计每一位上0-9的个数......
  • 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)看门狗,可以监控程序的运......
  • 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设置--关闭”显示所有支持的文件/缩略图......