了解面试必会算法Sliding Window 模式的前世今生

2024-01-24 04:20

本文主要是介绍了解面试必会算法Sliding Window 模式的前世今生,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

大家好,今天我们来聊一聊sliding window pattern。又是给有个机会给班花讲题的好机会,不能错过!
在这里插入图片描述

Sliding Window Pattern,中文名字叫滑动窗口模式,是一种常见的算法思想。它可以用来解决很多问题,比如:

Sliding Window Pattern 的优缺点

它具有以下优点:

  • 可以有效地解决很多问题:Sliding Window Pattern 可以用于解决很多问题,比如求最大值、最小值、平均值、子串、子序列的长度、最长公共子序列、最长上升子序列等。
  • 时间复杂度较低:Sliding Window Pattern 的一般时间复杂度为 O(n),对于一些特殊问题,时间复杂度甚至可以达到 O(1)。
  • 代码实现简单:Sliding Window Pattern 的代码实现非常简单,只需要维护一个窗口,然后在窗口滑动过程中不断地更新窗口内的值即可。

Sliding Window 算法也存在一些缺点:

  • 需要额外空间:Sliding Window Pattern 需要额外存储窗口内的元素,因此会增加空间复杂度。
  • 适用范围有限:Sliding Window Pattern 并不是所有问题都适用,只有满足特定条件的问题才能使用 Sliding Window Pattern。

怎么样?是不是依然觉得有些不理解,那么上图说话
在这里插入图片描述
L和R指针分别都指向a, R走到b,这时候将a放入HashSet,接下来放入b;因为窗口大小为3,那么R继续向➡️走,走到c,最终将c放入HashSet。
在这里插入图片描述
当然了如何白月光还是觉得这个算法不好记,我们就那个例子让她印象更加深刻吧

我们可以把数组看成一条河流,窗口就像一条船。船从左到右航行,每次经过一个元素,就把这个元素记录下来。当船航行到河流的尽头时,我们就得到了河流中最大值的滑动窗口。

伪代码实现

function sliding_window(array, window_size)# 初始化窗口window = []for i in range(window_size):window.append(array[i])# 滑动窗口for i in range(window_size, len(array)):# 更新窗口window.pop(0)window.append(array[i])# 计算窗口内的值...# 返回窗口内的值return window

在这里插入图片描述

具体用Java语言实现的例子可以参考小白理解Leetcode系列

小白水平理解面试经典题目LeetCode 594 最大和谐字符串

这篇关于了解面试必会算法Sliding Window 模式的前世今生的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Java设计模式---迭代器模式(Iterator)解读

《Java设计模式---迭代器模式(Iterator)解读》:本文主要介绍Java设计模式---迭代器模式(Iterator),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录1、迭代器(Iterator)1.1、结构1.2、常用方法1.3、本质1、解耦集合与遍历逻辑2、统一

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Redis Cluster模式配置

《RedisCluster模式配置》:本文主要介绍RedisCluster模式配置,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录分片 一、分片的本质与核心价值二、分片实现方案对比 ‌三、分片算法详解1. ‌范围分片(顺序分片)‌2. ‌哈希分片3. ‌虚

RabbitMQ工作模式中的RPC通信模式详解

《RabbitMQ工作模式中的RPC通信模式详解》在RabbitMQ中,RPC模式通过消息队列实现远程调用功能,这篇文章给大家介绍RabbitMQ工作模式之RPC通信模式,感兴趣的朋友一起看看吧... 目录RPC通信模式概述工作流程代码案例引入依赖常量类编写客户端代码编写服务端代码RPC通信模式概述在R

SQL Server身份验证模式步骤和示例代码

《SQLServer身份验证模式步骤和示例代码》SQLServer是一个广泛使用的关系数据库管理系统,通常使用两种身份验证模式:Windows身份验证和SQLServer身份验证,本文将详细介绍身份... 目录身份验证方式的概念更改身份验证方式的步骤方法一:使用SQL Server Management S

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Redis高可用-主从复制、哨兵模式与集群模式详解

《Redis高可用-主从复制、哨兵模式与集群模式详解》:本文主要介绍Redis高可用-主从复制、哨兵模式与集群模式的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录Redis高可用-主从复制、哨兵模式与集群模式概要一、主从复制(Master-Slave Repli

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

一文带你搞懂Redis Stream的6种消息处理模式

《一文带你搞懂RedisStream的6种消息处理模式》Redis5.0版本引入的Stream数据类型,为Redis生态带来了强大而灵活的消息队列功能,本文将为大家详细介绍RedisStream的6... 目录1. 简单消费模式(Simple Consumption)基本概念核心命令实现示例使用场景优缺点2