当前位置: 首页 > news >正文

滑动窗口,最长子序列最好的选择 -> 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)

最近在学校上短学期课程&#xff0c;做程序设计题&#xff0c;一下子回忆起了大一学数据结构与算法的日子&#xff01; 这十天我会记录一些做题的心得&#xff0c;今天带来的是对于最长子序列长度题型的解题框架&#xff1a;滑动窗口 本质就是双指针算法&#xff1a; 通过le…...

【Python】已解决:Python安装过程中的报错问题

文章目录 一、分析问题背景二、可能出错的原因三、错误代码示例四、正确解决方法五、注意事项 已解决&#xff1a;Python安装过程中的报错问题 一、分析问题背景 在安装Python 3.9.6&#xff08;64位&#xff09;版本时&#xff0c;用户可能会遇到一个报错信息&#xff0c;提…...

C++ STL IO流介绍

目录 一&#xff1a;IO流的继承关系&#xff1a; 二&#xff1a;输入输出功能 1. 基本用法 2. 格式化输入 3.非格式化输入 4. 格式化输出 三&#xff1a;流 1. 字符流 2. 向字符流中写入数据 3. 从字符流中读出数据 4. 清空字符流 5.完整的例子 四&#xff1a;文件…...

华为浏览器,Chrome的平替,插件无缝连接

文章目录 背景插件书签 背景 不知道各位小伙伴有没有这样的痛点&#xff0c;办公电脑、家里的电脑还有手机、平板等&#xff0c;收藏了一个网址或者在手机上浏览了某个网页&#xff0c;保存起来&#xff0c;可是一换平台或者换个电脑&#xff0c;在想要浏览之前收藏的东西&…...

SpringBoot新手快速入门系列教程:前述

我自己是一个SpringBoot新手&#xff0c;花了一天时间学了SpringBoot。大家不要惊讶&#xff0c;前提是我自己已经有了10几年的编程经验精通多门语言&#xff0c;并且在人间最强兵器Chat某T的AI助手帮助下&#xff0c;才能创造一天快速学会一个框架的神话。 当然中间遇到了很多…...

C语言9 指针

目录 指针的声明与初始化 指针运算 指针的加法和减法 指针的比较 指针与数组 通过指针访问数组元素 指针与多维数组 声明指向多维数组的指针 访问多维数组元素 指针数组和数组指针 指针数组 数组指针 字符指针 字符串的定义和字符指针 直接使用字符指针初始化字…...

Floyd判圈算法——寻找重复数(C++)

287. 寻找重复数 - 力扣&#xff08;LeetCode&#xff09; 题目描述 给定一个包含 n 1 个整数的数组 nums &#xff0c;其数字都在 [1, n] 范围内&#xff08;包括 1 和 n&#xff09;&#xff0c;可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 &#xff0c;返…...

面试题目分享

学习目标&#xff1a; 从面试了解自己的不足。 学习内容&#xff1a; 1.你会什么语言&#xff1f; 我该如何回答&#xff0c;我会java&#xff0c;c&#xff0c;c等&#xff0c;在工作中我会用到合适的语言。 牛逼吹的大话 尊敬的面试官&#xff0c;我精通Java和Python&…...

Solana开发之Anchor框架

文章目录 Solana开发之Anchor框架一、什么是Anchor二、安装和使用1. 安装rust2. 安装Solana下载预构建的二进制文件 3. 使用 Anchor 版本管理器 &#xff08;avm&#xff09; 进行安装&#xff08;推荐&#xff09; 四、Anchor 核心原理Anchor 程序由三部分组成程序的 ID 从哪里…...

界面组件Kendo UI for React 2024 Q2亮点 - 生成式AI集成、设计系统增强

随着最新的2024年第二季度发布&#xff0c;Kendo UI for React为应用程序开发设定了标准&#xff0c;包括生成式AI集成、增强的设计系统功能和可访问的数据可视化。新的2024年第二季度版本为应用程序界面提供了人工智能(AI)提示&#xff0c;从设计到代码的生产力增强、可访问性…...

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&#xff08;Hadoop Distributed File System&#xff0c;Hadoop分布式文件系统&#xff09;是Hadoop项目中的一个核心组件&#xff0c;旨在以高容错、高吞吐量来处理大规模数据集。它的体系架构由以下几个主要部分组成&#xff1a;Client&#xff0c;NameNo…...

大模型之战进入新赛季,开始卷应用

最近一段时间&#xff0c;国产大模型Kimi彻底火了&#xff0c;而这波爆火&#xff0c;某种意义上也展示了一个问题&#xff0c;即大模型的落地场景可能比技术比拼&#xff0c;更重要。 国产大模型Kimi突然爆火&#xff0c;与Kimi相关的产业链甚至被冠上“Kimi概念股”之名&…...

MySQL8.4.0 LTS安装教程 【小白轻松上手2024年最新长期支持版本MySQL手把手保姆级Windows超详细图文安装教程】

MySQL8.4.0 LTS安装教程 【小白轻松上手2024年最新长期支持版本MySQL手把手保姆级Windows超详细图文安装教程】 MySQL8.4.0前言&#xff08;版本说明&#xff09;官网下载MySQL1.访问MySQL官网2. 打开MySQL官网下载页面3. 选择下载类型Select Version【MySQL版本号】Select Ope…...

Linux 例题及详解

1.&#xff08;yum&#xff09;以下描述正确的是 A.在Centos中可以使用yum install 命令安装软件包 B.在Centos中可以使用yum uninstall 命令卸载软件包 C.在Centos中可以使用yum list 查看所有可安装软件包 D.在Centos中可以使用yum show查看所有可安装软件包 选项A、C是正确…...

爆款文案管理系统设计

设计一个爆款文案管理系统&#xff0c;目标是帮助营销团队高效地创建、管理并分析吸引人的文案&#xff0c;以提升产品或服务的市场吸引力和销售转化率。以下是一些关键功能和设计考量点&#xff1a; 1. 用户友好界面 简洁直观的界面&#xff1a;确保系统界面清晰&#xff0c…...

FPGA-Verilog-Vivado-软件使用

这里写目录标题 1 软件配置2 FPGA-7000使用2.1 运行启动方式 1 软件配置 编辑器绑定为Vscode&#xff0c;粘贴VS code运行文件的目录&#xff0c;后缀参数保持不变&#xff1a; 如&#xff1a; D:/Users/xdwu/AppData/Local/Programs/Microsoft VS Code/Code.exe [file name]…...

Ambari Hive 创建函数无权限

作者&#xff1a;櫰木 1、创建udf函数 参考文档&#xff1a;https://blog.csdn.net/helloxiaozhe/article/details/102498567 如果已经编写好&#xff0c;请使用自己的。如果没有请参考以上链接进行udf函数编写。 2、创建函数遇到的问题 由于集群开启了kerberos&#xff0…...

ARM GEC6818 LCD绘图 实心圆 三角形 五角星 任意区域矩形以及旗帜

要在ARM上实现LCD绘图&#xff0c;可以按照以下步骤进行&#xff1a; 硬件初始化&#xff1a;初始化LCD控制器和相关引脚&#xff0c;配置时钟、分辨率和颜色深度等。 内存映射&#xff1a;将LCD显示区域映射到ARM的内存地址空间中&#xff0c;可以通过ARM的内存映射机制来实现…...

Sentinel-1 Level 1数据处理的详细算法定义(三)

《Sentinel-1 Level 1数据处理的详细算法定义》文档定义和描述了Sentinel-1实现的Level 1处理算法和方程&#xff0c;以便生成Level 1产品。这些算法适用于Sentinel-1的Stripmap、Interferometric Wide-swath (IW)、Extra-wide-swath (EW)和Wave模式。 今天介绍的内容如下&…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

Tauri2学习笔记

教程地址&#xff1a;https://www.bilibili.com/video/BV1Ca411N7mF?spm_id_from333.788.player.switch&vd_source707ec8983cc32e6e065d5496a7f79ee6 官方指引&#xff1a;https://tauri.app/zh-cn/start/ 目前Tauri2的教程视频不多&#xff0c;我按照Tauri1的教程来学习&…...

python基础语法Ⅰ

python基础语法Ⅰ 常量和表达式变量是什么变量的语法1.定义变量使用变量 变量的类型1.整数2.浮点数(小数)3.字符串4.布尔5.其他 动态类型特征注释注释是什么注释的语法1.行注释2.文档字符串 注释的规范 常量和表达式 我们可以把python当作一个计算器&#xff0c;来进行一些算术…...

Element-Plus:popconfirm与tooltip一起使用不生效?

你们好&#xff0c;我是金金金。 场景 我正在使用Element-plus组件库当中的el-popconfirm和el-tooltip&#xff0c;产品要求是两个需要结合一起使用&#xff0c;也就是鼠标悬浮上去有提示文字&#xff0c;并且点击之后需要出现气泡确认框 代码 <el-popconfirm title"是…...