滑动窗口,最长子序列最好的选择 -> O(N)
最近在学校上短学期课程,做程序设计题,一下子回忆起了大一学数据结构与算法的日子!
这十天我会记录一些做题的心得,今天带来的是对于最长子序列长度题型的解题框架:滑动窗口
本质就是双指针算法:
通过left和right指针构建一个左闭右开的窗口window:(left, right]
首先,通过right指针向右expand窗口
窗口满足题设条件的话就一直expand,直到条件被打破。
此时窗口不满足题设条件,需要通过left指针向右shrink窗口,直到再次满足题设条件。
题目变化,变的就是如何maintain这个窗口而已。
k

int fun(int* A, int N,int S) {
// sliding window// The window we maintain is like [left, right)int left = 0, right = 0;int windowSum = 0;int Max = 0;while(right < N) {// right expandingwindowSum += A[right++];Max = windowSum <= S && right - left > Max ? right - left : Max;// shrinkingwhile(left <= right && windowSum > S) {windowSum -= A[left++];}}return Max;
}

int fun(int* A, int N,int S) {
// sliding window// The window we maintain is like [left, right)int left = 0, right = 0;int Max = 0;// maintain the local minimum and local maximumint winMin = A[0];int winMax = A[0];while(right < N) {// right expandingif(A[right] > winMax) {winMax = A[right];}else if(A[right] < winMin) {winMin = A[right];}right++;Max = winMax - winMin <= S && right - left > Max ? right - left : Max;// shrinkingwhile(left <= right && winMax - winMin > S) {
// Don't forget to initialize the local value before setting.left++;winMin = A[left];winMax = A[right];
// set the maximum and minimum in the new windowfor(int i = left; i < right; i++) {if(A[i] > winMax) {winMax = A[i];}else if(A[i] < winMin) {winMin = A[i];}}}}return Max;
}
相关文章:
滑动窗口,最长子序列最好的选择 -> O(N)
最近在学校上短学期课程,做程序设计题,一下子回忆起了大一学数据结构与算法的日子! 这十天我会记录一些做题的心得,今天带来的是对于最长子序列长度题型的解题框架:滑动窗口 本质就是双指针算法: 通过le…...
【Python】已解决:Python安装过程中的报错问题
文章目录 一、分析问题背景二、可能出错的原因三、错误代码示例四、正确解决方法五、注意事项 已解决:Python安装过程中的报错问题 一、分析问题背景 在安装Python 3.9.6(64位)版本时,用户可能会遇到一个报错信息,提…...
C++ STL IO流介绍
目录 一:IO流的继承关系: 二:输入输出功能 1. 基本用法 2. 格式化输入 3.非格式化输入 4. 格式化输出 三:流 1. 字符流 2. 向字符流中写入数据 3. 从字符流中读出数据 4. 清空字符流 5.完整的例子 四:文件…...
华为浏览器,Chrome的平替,插件无缝连接
文章目录 背景插件书签 背景 不知道各位小伙伴有没有这样的痛点,办公电脑、家里的电脑还有手机、平板等,收藏了一个网址或者在手机上浏览了某个网页,保存起来,可是一换平台或者换个电脑,在想要浏览之前收藏的东西&…...
SpringBoot新手快速入门系列教程:前述
我自己是一个SpringBoot新手,花了一天时间学了SpringBoot。大家不要惊讶,前提是我自己已经有了10几年的编程经验精通多门语言,并且在人间最强兵器Chat某T的AI助手帮助下,才能创造一天快速学会一个框架的神话。 当然中间遇到了很多…...
C语言9 指针
目录 指针的声明与初始化 指针运算 指针的加法和减法 指针的比较 指针与数组 通过指针访问数组元素 指针与多维数组 声明指向多维数组的指针 访问多维数组元素 指针数组和数组指针 指针数组 数组指针 字符指针 字符串的定义和字符指针 直接使用字符指针初始化字…...
Floyd判圈算法——寻找重复数(C++)
287. 寻找重复数 - 力扣(LeetCode) 题目描述 给定一个包含 n 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ,返…...
面试题目分享
学习目标: 从面试了解自己的不足。 学习内容: 1.你会什么语言? 我该如何回答,我会java,c,c等,在工作中我会用到合适的语言。 牛逼吹的大话 尊敬的面试官,我精通Java和Python&…...
Solana开发之Anchor框架
文章目录 Solana开发之Anchor框架一、什么是Anchor二、安装和使用1. 安装rust2. 安装Solana下载预构建的二进制文件 3. 使用 Anchor 版本管理器 (avm) 进行安装(推荐) 四、Anchor 核心原理Anchor 程序由三部分组成程序的 ID 从哪里…...
界面组件Kendo UI for React 2024 Q2亮点 - 生成式AI集成、设计系统增强
随着最新的2024年第二季度发布,Kendo UI for React为应用程序开发设定了标准,包括生成式AI集成、增强的设计系统功能和可访问的数据可视化。新的2024年第二季度版本为应用程序界面提供了人工智能(AI)提示,从设计到代码的生产力增强、可访问性…...
python输出/sys/class/power_supply/BAT0/电池各项内容
读取 /sys/class/power_supply/BAT0/ 目录下的所有相关文件,并输出其内容: import os# 定义电池信息文件的路径 battery_path = "/sys/class/power_supply/BAT0/"# 读取文件内容的函数 def read_battery_info(file_name):try:with open(os.path.join(battery_path…...
HDFS体系架构文件写入/下载流程
HDFS体系架构 HDFS(Hadoop Distributed File System,Hadoop分布式文件系统)是Hadoop项目中的一个核心组件,旨在以高容错、高吞吐量来处理大规模数据集。它的体系架构由以下几个主要部分组成:Client,NameNo…...
大模型之战进入新赛季,开始卷应用
最近一段时间,国产大模型Kimi彻底火了,而这波爆火,某种意义上也展示了一个问题,即大模型的落地场景可能比技术比拼,更重要。 国产大模型Kimi突然爆火,与Kimi相关的产业链甚至被冠上“Kimi概念股”之名&…...
MySQL8.4.0 LTS安装教程 【小白轻松上手2024年最新长期支持版本MySQL手把手保姆级Windows超详细图文安装教程】
MySQL8.4.0 LTS安装教程 【小白轻松上手2024年最新长期支持版本MySQL手把手保姆级Windows超详细图文安装教程】 MySQL8.4.0前言(版本说明)官网下载MySQL1.访问MySQL官网2. 打开MySQL官网下载页面3. 选择下载类型Select Version【MySQL版本号】Select Ope…...
Linux 例题及详解
1.(yum)以下描述正确的是 A.在Centos中可以使用yum install 命令安装软件包 B.在Centos中可以使用yum uninstall 命令卸载软件包 C.在Centos中可以使用yum list 查看所有可安装软件包 D.在Centos中可以使用yum show查看所有可安装软件包 选项A、C是正确…...
爆款文案管理系统设计
设计一个爆款文案管理系统,目标是帮助营销团队高效地创建、管理并分析吸引人的文案,以提升产品或服务的市场吸引力和销售转化率。以下是一些关键功能和设计考量点: 1. 用户友好界面 简洁直观的界面:确保系统界面清晰,…...
FPGA-Verilog-Vivado-软件使用
这里写目录标题 1 软件配置2 FPGA-7000使用2.1 运行启动方式 1 软件配置 编辑器绑定为Vscode,粘贴VS code运行文件的目录,后缀参数保持不变: 如: D:/Users/xdwu/AppData/Local/Programs/Microsoft VS Code/Code.exe [file name]…...
Ambari Hive 创建函数无权限
作者:櫰木 1、创建udf函数 参考文档:https://blog.csdn.net/helloxiaozhe/article/details/102498567 如果已经编写好,请使用自己的。如果没有请参考以上链接进行udf函数编写。 2、创建函数遇到的问题 由于集群开启了kerberos࿰…...
ARM GEC6818 LCD绘图 实心圆 三角形 五角星 任意区域矩形以及旗帜
要在ARM上实现LCD绘图,可以按照以下步骤进行: 硬件初始化:初始化LCD控制器和相关引脚,配置时钟、分辨率和颜色深度等。 内存映射:将LCD显示区域映射到ARM的内存地址空间中,可以通过ARM的内存映射机制来实现…...
Sentinel-1 Level 1数据处理的详细算法定义(三)
《Sentinel-1 Level 1数据处理的详细算法定义》文档定义和描述了Sentinel-1实现的Level 1处理算法和方程,以便生成Level 1产品。这些算法适用于Sentinel-1的Stripmap、Interferometric Wide-swath (IW)、Extra-wide-swath (EW)和Wave模式。 今天介绍的内容如下&…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...
倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...
海云安高敏捷信创白盒SCAP入选《中国网络安全细分领域产品名录》
近日,嘶吼安全产业研究院发布《中国网络安全细分领域产品名录》,海云安高敏捷信创白盒(SCAP)成功入选软件供应链安全领域产品名录。 在数字化转型加速的今天,网络安全已成为企业生存与发展的核心基石,为了解…...
