【练习】滑动窗口思想

  • 🎥 个人主页:Dikz12
  • 🔥个人专栏:Java算法
  • 📕格言:那些在暗处执拗生长的花,终有一日会馥郁传香
  • 欢迎大家👍点赞✍评论⭐收藏

目录

1.长度最小的子数组

题目解析 

讲解 

 代码实现

 2.无重复字符的最长子串

题目解析 

 讲解

代码实现 

3.最大连续1的个数 III

题目解析 

讲解 

代码实现 

4.将 x 减到 0 的最小操作数

题目解析

​编辑讲解 

代码实现 

 5.水果成篮

题目解析 

讲解 

代码实现 


1.长度最小的子数组

题目解析 

讲解 

解法一: 暴力枚举出所有子数组的和. O(n^2)

 

解法二:利用“滑动窗口”优化.(利用单调性,同向双指针) O(n)

  1. left = 0,right = 0
  2. 进窗口
  3. 判断
  4.  出窗口 或者 是更新结果

当sum 小于target时,就进窗口(right++);

满足判断条件(sum大于等于target)时,此时,更新结果,出窗口,可以⼤胆舍去 left得值然后left++,right也没有回退到left位置的必要了(left++)

 代码实现

    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int sum = 0, len = Integer.MAX_VALUE;
        for (int left = 0, right = 0; right < n; right++) {
            sum += nums[right];
            // 进窗口
            while (sum >= target) {
                // 更新len
                len = Math.min(len, (right - left + 1));
                // 出窗口
                sum -= nums[left++];
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }

 2.无重复字符的最长子串

题目解析 

 讲解

解法一:暴力枚举 + 哈希表(判断字符是否重复出现)

枚举「从每⼀个位置」开始往后,⽆重复字符的⼦串可以到达什么位置。找出其中⻓度最⼤的即
可。在往后寻找⽆重复⼦串能到达的位置时,可以利⽤「哈希表」统计出字符出现的频次,来判断什么时候⼦串出现了重复元素.

解法二:使用“滑动窗口”来解决.

右端元素 ch 进⼊窗⼝的时候,使用数组模拟哈希来统计这个字符的频次:

  • 如果这个字符出现的频次超过1 ,说明窗⼝内有重复元素,那么就从左侧开始划出窗⼝,直到ch 这个元素的频次变为 1 ,然后再更新结果。
  • 如果没有超过1 ,说明当前窗⼝没有重复元素,可以直接更新结果

代码实现 

    public int lengthOfLongestSubstring(String s) {
        //转换成字符数组
        char[] ch = s.toCharArray();
        int ret =0,n = s.length();
        //利用ascii码值模拟
        int[] hash = new int[128];
        for(int left = 0,right = 0; right < n; right++) {
            hash[ch[right]]++;
            while(hash[ch[right]] > 1) { //判断
                 hash[ch[left++]]--;//出窗口
            }
            ret = Math.max(ret,right - left + 1);
        }
        return ret;

3.最大连续1的个数 III

题目解析 

讲解 

 意思就是:找出最长的子数组,且 0 的个数不能超过 k.

解法一: 暴力枚举 + 计数器(统计0出现的次数)

解法二:滑动窗口

  1. 定义left=0,right=0 ; count=0 统计0的次数;
  2.  进窗口,如果 等于 0,count++; 等于 1,不做处理
  3. 判断,当 count 大于 k,出窗口,出的时候,等于 0,count - -;等于 1,不做处理
  4. 更新结果. (不满足判断,直接更新结果;否则,先出窗口,在更新)

 

代码实现 

    public int longestOnes(int[] nums, int k) {
        int n = nums.length, count = 0, ret = 0;
        for (int left = 0, right = 0; right < n; right++) {
            if (nums[right] == 0) {
                count++;
            }
            while (count > k) { // 判断
                if (nums[left] == 0) {
                    count--;
                }
                left++; // 出窗口
            }
            ret = Math.max(ret, right - left + 1); // 更新结果
        }
        return ret;
    }

4.将 x 减到 0 的最小操作数

题目解析

讲解 

正难则反 :题⽬要求的是数组「左端+右端」两段连续的、和为 x 的最短数组. 转换成求数组内⼀段连续的、和为 sum(nums) - x 的最⻓数组.

 解法:滑动窗口. 

这是的写法就和第一题的时候就很相似了.(求等于target的最长的子数组) 

  1.  计算出 target = sum - x的值,target 小于 0,直接返回 -1;(sum为整个数组的和)
  2. 进窗口  right++(记录下当前和tmp)
  3. 判断. 当tmp大于target时,出窗口,先从tmp中舍去当前位置的值,在left++;
  4. 更新结果. 我们要的是 等于target 的子数组长度,需要加上个if条件.

代码实现 

    public int minOperations(int[] nums, int x) {
        int ret = -1,sum = 0,n = nums.length,tmp = 0;
        for(int i : nums) {
            sum += i;
        }
        int target = sum - x;
        if(target < 0) {
            return -1;
        }
        for(int left = 0,right = 0; right < n;right++) {
            //进窗口
            tmp += nums[right]; 
            //判断
            while(tmp > target) { 
              //出窗口
              tmp -= nums[left++];
            }
            if(tmp == target) {
                ret = Math.max(ret,right - left + 1);
            }
        }
        if(ret == -1) {
            return -1;
        }else{
            //ret是sum-x的长度
            return n - ret;
        }
    }

 5.水果成篮

题目解析 

 这么长的小作文,意思就是:找出一个最长的子数组的长度,子数组中不超过两种类型的水果.

讲解 

解法一:暴力枚举 + Map 容器. 

解法二:滑动窗口 .

 

指针同向移动,可以使用“滑动窗口.

  1.  初始化Map容器(也可以使用数组模拟),来统计窗⼝内⽔果的种类和数量;
  2. 初始化变量:左右指针 left = 0,right = 0,记录结果的变量 ret = 0
  3. 进窗口.将当前⽔果放⼊Map中;
  4. 判断.当前⽔果进来后,Map的⼤⼩:如果超过 2:将左侧元素滑出窗⼝,并且在Map中将该元素的value减⼀;如果这个元素的value减⼀之后变成了 0,就把该元素从哈希表中删除;
    重复上述两个过程,直到哈希表中的⼤⼩不超过 2;
  5.  更新结果

代码实现 

    public int totalFruit(int[] fruits) {
        int n = fruits.length, ret = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int left = 0, right = 0; right < n; right++) {
            int key = fruits[right];
            map.put(key, map.getOrDefault(key, 0) + 1);// 进窗口
            // 判断
            while (map.size() > 2) {
                // 出窗口
                int out = fruits[left];
                map.put(out, map.get(out) - 1);
                if (map.get(out) == 0) {
                    map.remove(out);
                }
                left++;
            }
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

 数组模拟实现:

   public int totalFruit(int[] fruits) {
        int n = fruits.length, ret = 0;
        int[] map = new int[n+1];
        // Map<Integer, Integer> map = new HashMap<>();
        for (int left = 0, right = 0,type = 0; right < n; right++) {
            int key = fruits[right];
            // map.put(key, map.getOrDefault(key, 0) + 1);// 进窗口
            if(map[key] == 0) {
                type++; //记录水果种类
            }
            map[key]++; //进窗口
            // 判断
            while (type > 2) {
                // 出窗口
                int out = fruits[left];
                map[out]--;
                // map.put(out, map.get(out) - 1);
                if (map[out] == 0) {
                    type--;
                }
                left++;
            }
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/505784.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

AI绘画教程:Midjourney使用方法与技巧从入门到精通

文章目录 一、《AI绘画教程&#xff1a;Midjourney使用方法与技巧从入门到精通》二、内容介绍三、作者介绍&#x1f324;️粉丝福利 一、《AI绘画教程&#xff1a;Midjourney使用方法与技巧从入门到精通》 一本书读懂Midjourney绘画&#xff0c;让创意更简单&#xff0c;让设计…

编曲知识12:了解弦乐 四部和声 弦乐群奏写作 编组、文件夹轨应用

认识弦乐 认识提琴 String:弦乐 Basse:倍大提琴 Cello:大提琴 Viola:中提琴 Violin:小提琴 音源介绍(一) LA Scoring Strings 简称:Lass/拉丝弦乐 Basses:倍大提琴组 Cellos:大提琴组 LASS Ensemble Patches:大齐奏 Violas:中提琴组 ViolinsⅠ:小提琴一组 Violin…

数字乡村发展蓝图:科技赋能农村实现全面振兴

目录 一、数字乡村发展蓝图的内涵与目标 二、科技赋能农村&#xff1a;数字乡村发展的动力与路径 &#xff08;一&#xff09;加强农业科技创新&#xff0c;提升农业生产效率 &#xff08;二&#xff09;推进农村电商发展&#xff0c;拓宽农民增收渠道 &#xff08;三&…

【C++】C++11的新特性

目录 一. 列表初始化1. 列表初始化的原理: initializer_list 二. 类型的声明1. auto2. decltype 三. nullptr四. 范围 for五. STL容器变化六. 类的新功能 一. 列表初始化 在 C 语言中, 就可以使用 {} 对数组或结构体进行初始化, 而 C11 扩大了 {} 的使用范围, 使其可以初始化所…

探索http-vue-loader的奥秘:原理、使用方法、在Vue开发中的应用

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

《深度学习入门之PyTorch》书籍阅读笔记

《深度学习入门之PyTorch》书籍阅读笔记 ISBN 978-7-121-32620-2 多层全连接神经网络 Pytorch基础 Tensor张量 是一个多维矩阵&#xff0c;pytorch的tensor可以和numpy的ndarray相互转换&#xff0c;但numpy的ndarray只能在CPU上运行。不同数据类型的Tensor&#xff0c;t…

2024 年高效开发的 React 生态系统

要使用 React 制作应用程序&#xff0c;需要熟悉正确的库来添加您需要的功能。例如&#xff0c;要添加某个功能&#xff08;例如身份验证或样式&#xff09;&#xff0c;您需要找到一个好的第三方库来处理它。 在这份综合指南中&#xff0c;我将向您展示我建议您在 2024 年使用…

多协议支持 API 调测客户端:Postman 的强力替代品 | 开源日报 No.210

Kong/insomnia Stars: 32.6k License: Apache-2.0 insomnia 是一个开源的、跨平台的 API 客户端&#xff0c;支持 GraphQL、REST、WebSockets、SSE 和 gRPC 协议&#xff0c;并提供云存储、本地存储和 Git 存储。 调试各种流行协议和格式的 API。使用原生 OpenAPI 编辑器设计…

计算机网络-HTTP相关知识(一)

HTTP基础 基本概念&#xff1a;HTTP是一种计算机之间交流通信的规范&#xff0c;它允许数据在两点之间传输&#xff0c;这个过程可以包括中转或接力。HTTP不仅仅包括文本&#xff0c;还可以包括图片、音频等超文本。状态码&#xff1a;HTTP状态码分为五类&#xff1a; 2xx&…

11-SpringSecurity:Session共享,菜鸟驿站java面试题

pom依赖 org.springframework.boot spring-boot-starter-web org.springframework.boot spring-boot-starter-security org.springframework.boot spring-boot-starter-data-redis org.springframework.session spring-session-data-redis org.projectlombok lombok …

蓝桥杯第十五届抱佛脚(八)并查集

蓝桥杯第十五届抱佛脚&#xff08;八&#xff09;并查集 基本概念 并查集是一种数据结构&#xff0c;用于管理一系列不交集的元素集合&#xff0c;并支持两种操作&#xff1a; 查找&#xff08;Find&#xff09;&#xff1a; 查找操作用于确定某个元素属于哪个集合&#xf…

Java基础学习: JDK动态代理

文章目录 一、什么是JDK动态代理二、JDK动态代理的特点三、JDK动态代理类如何使用四、JDK动态代理原理分析1、创建代理对象2、生成代理类 一、什么是JDK动态代理 JDK动态代理是Java提供的一种动态生成代理类和代理对象的技术。它主要利用Java的反射机制实现&#xff0c;在运行…

Lucene及概念介绍

Lucene及概念介绍 基础概念倒排索引索引合并分析查询语句的构成 基础概念 Document&#xff1a;我们一次查询或更新的载体&#xff0c;对比于实体类 Field&#xff1a;字段&#xff0c;是key-value格式的数据&#xff0c;对比实体类的字段 Item&#xff1a;一个单词&#xff0…

【计算机网络】四层负载均衡和七层负载均衡

前言 1、分层方式 首先我们知道&#xff0c;在计算机网络中&#xff0c;常用的协议分层方式&#xff1a;OSI和TCP/IP&#xff0c;以及实际生产中使用的协议划分方式。 在OSI中&#xff0c;各层的职责如下&#xff1a; 应用层&#xff1a;对软件提供接口以使程序能使用网络服…

都江堰操作系统系统架构图

都江堰操作系统设计思想源于中国传统的“天人合一&#xff0c;道法自然”哲学思想&#xff0c;内核调度系统采用事件调度&#xff0c;全球首创&#xff0c;突破单机桎梏&#xff0c;实现异构网络调度&#xff0c;开拓新赛道&#xff0c;实现换道超车。“有事就动&#xff0c;没…

Linux的中间件

我们先补充点关于awk的内容 awk的用法其实很广。 $0 表示整条记录 变量&#xff1a; NF 一行中有多少个字段&#xff08;表示字段数&#xff09; NR &#xff1a; 代表当前记录的序号&#xff0c;从1开始计数。每读取一条记录&#xff0c;NR的值就会自动增加1。&#xff08;…

Applied Spatial Statistics(一)统计推断

Applied Spatial Statistics&#xff08;一&#xff09;统计推断 1.统计推断&#xff1a;Bootstrap 置信区间 本笔记本演示了如何使用引导方法构建统计数据的置信区间。 我们还将检查 CI 的覆盖概率。 构建 Bootstrap 置信区间检查覆盖概率Bootstrap CI 相关系数 import nu…

数据挖掘入门项目二手交易车价格预测之特征工程

文章目录 目标常见的特征工程具体步骤1. 导入数据2. 删除异常值3. 特征构造3.1 为树模型构造特征3.2 为LR NN 之类的模型构造特征 4. 特征筛选过滤式包裹式嵌入式 5. 总结 本文数据集来自阿里天池&#xff1a;https://tianchi.aliyun.com/competition/entrance/231784/informat…

Debian linux版本下运行的openmediavault网盘 千兆网卡升级万兆

一、适用场景 1、使用vmware ESXi虚拟化平台运行多种不同应用服务器时&#xff0c;其中网盘服务器采用开源的openmediavault搭建&#xff1b; 2、将老专业服务器升级千兆网为万兆网&#xff1b; 3、需要转移的数据量大的企业或用户&#xff1b; 4、从服务器到服务器的数据转移…

LeetCode刷题【链表,图论,回溯】

目录 链表138. 随机链表的复制148. 排序链表146. LRU 缓存 图论200. 岛屿数量994. 腐烂的橘子207. 课程表 回溯 链表 138. 随机链表的复制 给你一个长度为 n 的链表&#xff0c;每个节点包含一个额外增加的随机指针 random &#xff0c;该指针可以指向链表中的任何节点或空节…