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

【算法一周目】滑动窗口(1)

目录

长度最小的子数组

解题思路

代码实现

无重复字符的最大字串

解题思路

代码实现

最大连续1的个数l l l

解题思路

代码实现

将x减到0的最小操作数

解题思路

代码实现


长度最小的子数组

题目链接:209. 长度最小的子数组
题目描述:
给定一个含有 n 个正整数数组 nums 和一个正整数 target
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0

解题思路

解法一:暴力求解

枚举所有可能的子数组,计算子数组的和,检查是否大于等于 target ,找到符合题目要求的长度最小的子数组。

​
​
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int ret = INT_MAX;for (int left = 0; left < n; ++left) {int sum = 0;for (int right = left; right < n; ++right) {sum += nums[right];if (sum >= target) {ret = min(ret, right - left + 1);break;}}}return ret == INT_MAX ? 0 : ret;}
};​​

暴力解法简单粗暴,但是由于时间复杂度是 O(n ^ 2),一旦数据量比较大,必定会超时

解法二:滑动窗口

滑动窗口其实也是基于暴力解法优化而来,滑动窗口的核心就是想办法让暴力解法中的 right 指针不回退,一直往前走

我们想想这样一个问题,在暴力解法中,当left和right找到一个合法的子数组后,left++,right有必要回退到left位置吗?答案是没有必要的,当left++后left和right区间的子数组的和可能大于等于target,也可能小于target。我们可以让left一直++,并在此过程中记录区间长度,直到left和right区间的子数组的和小于target,然后再让right++,增大区间长度的和,重复上述过程,直到遍历完数组。

滑动窗口具体过程如下:

  • 1.初始化left和right指针为0。
  • 2.进窗口:计算区间的和
  • 3.判断
  • 当区间和大于等于target时,找到合法区间,更新结果出窗口:让left++,重复判断-更新结果过程,直到区间和小于target;
  • 当区间和小于target时,进窗口:让right++,计算区间和。
  • 4.重复上述过程,直到right遍历完数组

值得注意的是,更新结果这步不是固定的,有时候在判断时更新,有时候在判断完后再更新。

代码实现

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum = 0, n = nums.size(), len = INT_MAX;for(int left = 0, right = 0; right < n; right++){sum += nums[right];while(sum >= target){len = min(len, right - left + 1);sum -= nums[left++];}}return len == INT_MAX ? 0 : len;}
};

细节:由于求的是长度最小的子数组,所以len要初始化为INT_MAX,不能初始化为0。

时间复杂度:O(n)

空间复杂度:O(1)

无重复字符的最大字串

题目链接:3. 无重复字符的最长子串
题目描述
给定一个字符串 s,请你找出其中不含有重复字符的最长子串的长度

解题思路

解法一:暴力求解

​​​通过枚举从每个位置开始,向后寻找无重复字符的子串能到达的位置,记录其中最长的子串长度即可。在寻找无重复子串时,可以使用哈希表统计字符出现的频次,遇到重复字符时停止。​​​​

class Solution {
public:int lengthOfLongestSubstring(string s) {int ret = 0;  // 记录结果int n = s.length();// 枚举从不同位置开始的无重复子串for (int i = 0; i < n; i++) {int hash[128] = { 0 };  // 记录字符频次for (int j = i; j < n; j++) {hash[s[j]]++;  // 统计字符频次if (hash[s[j]] > 1)  // 出现重复,终止break;ret = max(ret, j - i + 1);  // 更新结果}}return ret;}
};

暴力求解的问题还是时间复杂度是O(n),对于处理数据量比较大的数据时会超时。

解法二:滑动窗口

使用滑动窗口,使得窗口内的字符不重复。

当窗口右端进入新字符时,更新哈希表记录字符频次:

  • 如果字符频次大于1,则窗口出现重复字符,开始从左侧收缩窗口直到字符频次变为1,更新结果
  • 如果没有超过1,说明没有重复字符,直接更新结果

代码实现

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = { 0 };  // 使用数组模拟哈希表int left = 0, right = 0, n = s.size(), len = 0;while(right < n){hash[s[right]]++;  // 将右端字符加入窗口while(hash[s[right]] > 1)  //判断hash[s[left++]]--;      //出窗⼝//更新结果len = max(len, right - left + 1); //让下⼀个元素进⼊窗⼝right++;    }return len;}
};

细节:由于s由英文字母、数字、符号和空格组成,不必真的使用unordered_map,用一个128大小的数组当作哈希表即可。

时间复杂度:O(n)

空间复杂度:O(1)

最大连续1的个数l l l

题目链接:1004. 最大连续 1 的个数 III
题目描述
给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个0,则返回数组中连续 1的最大个数。

解题思路

根据题目描述,我们可以将其转换为求一段最长的连续子区间其中0的数量不超过k个,我们用滑动窗口解决。

  • 1.初始化左右指针left和right,以及记录0个数的变量cnt。
  • 2.当right向右遍历数组时:
  • 如果当前元素是0,cnt++
  • 然后判断cnt是否大于cnt大于则让left++缩减窗口移除窗口中的0直到cnt小于等于k。
  • 3。此时窗口合法更新结果。

代码实现

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int ret = 0, cnt = 0, n = nums.size();for(int left = 0, right = 0; right < n; right++){if(nums[right] == 0) cnt++; //当前元素为0,cnt++//当cnt > k时,移除窗口中的0,直到cnt <= kwhile(cnt > k){if(nums[left] == 0)cnt--;left++;    }//更新结果ret = max(ret, right - left + 1);}return ret;}
};

时间复杂度:O(n)

空间复杂度:O(1)

将x减到0的最小操作数

题目链接:1658. 将 x 减到 0 的最小操作数

题目描述:
给你一个整数数组 nums一个整数 x每次操作时,你可以移除数组 nums 的最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,你需要修改数组以供接下来的操作使用。如果可以将 x 恰好减到 0返回最少的操作数;否则,返回 -1

解题思路

解法:滑动窗口

题目要求的是在数组左端、右端找两段连续且和为x的短数组,我们可以将其转换为在数组中找到和为 sum - x 的最长子数组,其剩余数组长度就是最小操作数,可以使用滑动窗口解决问题。

具体过程如下:

  • 1.计算数组的和 sum ,然后求出target = sum - x。这里有个小细节,若target < 0说明x > sum不可能找到题目要求的最小操作数直接返回-1
  • 2.初始化 left 和 righ t两个指针为0,再用一个变量 part_sum 记录区间长度的和。
  • 3.当 part_sum > target 时减小 part_sum,left++直到 part_sum <= target
  • 4.如果 part_sum == target更新最长子数组的长度
  • 5.right++,增大 part_sum。
  • 循环上述过程,直到 right 遍历完数组。

代码实现

class Solution {
public:int minOperations(vector<int>& nums, int x) {//1.计算数组总和int n = nums.size(), sum = 0;for(auto e : nums) sum += e;int len = -1, target = sum - x, part_sum = 0;if(target < 0) return -1;//2.使用滑动窗口求出符合条件的最大子数组和for(int left = 0, right = 0; right < n; right++){part_sum += nums[right];while(left < n && part_sum > target)part_sum -= nums[left++];if(part_sum == target)len = max(len, right - left + 1);}return len == -1 ? -1 : n - len;}
};

拜拜,下期再见😏

摸鱼ing😴✨🎞

相关文章:

【算法一周目】滑动窗口(1)

目录 长度最小的子数组 解题思路 代码实现 无重复字符的最大字串 解题思路 代码实现 最大连续1的个数l l l 解题思路 代码实现 将x减到0的最小操作数 解题思路 代码实现 长度最小的子数组 题目链接&#xff1a;209. 长度最小的子数组题目描述&#xff1a; 给定一个…...

React Native 基础

React 的核心概念 定义函数式组件 import组件 要定义一个Cat组件,第一步要使用 import 语句来引入React以及React Native的 Text 组件: import React from react; import { Text } from react-native; 定义函数作为组件 const CatApp = () => {}; 渲染Text组件...

【C++笔记】list使用详解及模拟实现

前言 各位读者朋友们大家好&#xff01;上期我们讲了vector的使用以及底层的模拟实现&#xff0c;这期我们来讲list。 目录 前言一. list的介绍及使用1.1 list的介绍1.2 list的使用1.2.1 list的构造1.2.2 list iterator的使用1.2.3 list capacity1.2.4 list element access1.…...

【机器学习】机器学习中用到的高等数学知识-7.信息论 (Information Theory)

熵 (Entropy)&#xff1a;用于评估信息的随机性&#xff0c;常用于决策树和聚类算法。交叉熵 (Cross-Entropy)&#xff1a;用于衡量两个概率分布之间的差异&#xff0c;在分类问题中常用。 信息论作为处理信息量和信息传输的数学理论&#xff0c;在机器学习中具有广泛的应用。…...

《现代制造技术与装备》是什么级别的期刊?是正规期刊吗?能评职称吗?

​问题解答 问&#xff1a;《现代制造技术与装备》是不是核心期刊&#xff1f; 答&#xff1a;不是&#xff0c;是知网收录的第二批认定学术期刊。 问&#xff1a;《现代制造技术与装备》级别&#xff1f; 答&#xff1a;省级。主管单位&#xff1a;齐鲁工业大学&#xff0…...

09 - Clickhouse的SQL操作

目录 1、Insert 1.1、标准 1.2、从表到表的插入 2、Update和Delete 2.1、删除操作 2.2、修改操作 3、查询操作 3.1、with rollup&#xff1a;从右至左去掉维度进行小计 3.2、with cube : 从右至左去掉维度进行小计&#xff0c;再从左至右去掉维度进行小计 3.3、with …...

如何解决pdf.js跨域从url动态加载pdf文档

摘要 当我们想用PDF.js从URL加载文档时&#xff0c;将会因遇到跨域问题而中断&#xff0c;且是因为会触发了PDF.js和浏览器的双重CORS block&#xff0c;这篇文章将会介绍&#xff1a;①如何禁用pdf.js的跨域&#xff1f;②如何绕过浏览器的CORS加载URL文件&#xff1f;②如何使…...

深入理解TTY体系:设备节点与驱动程序框架详解

往期内容 本专栏往期内容&#xff1a;Uart子系统 UART串口硬件介绍 interrupt子系统专栏&#xff1a; 专栏地址&#xff1a;interrupt子系统Linux 链式与层级中断控制器讲解&#xff1a;原理与驱动开发 – 末片&#xff0c;有专栏内容观看顺序 pinctrl和gpio子系统专栏&#xf…...

库的操作(MySQL)

1.创建数据库 语法&#xff1a; CREATE DATABASE [IF NOT EXISTS] db_name [create_specification [, create_specification] ...] create_specification:[DEFAULT] CHARACTER SET charset_name[DEFAULT] COLLATE collation_name说明&#xff1a; 大写的表示关键字 [ ] 是可…...

在 for 循环中,JVM可能会将 arr.length 提升到循环外部,仅计算一次。可能会将如何解释 详解

在 Java 的 for 循环中&#xff0c;JVM 有能力进行优化&#xff0c;将 arr.length 的访问提升到循环外部&#xff0c;避免每次迭代都重新计算 arr.length。这种优化主要是由于 JVM 的 即时编译器&#xff08;JIT&#xff09; 和 逃逸分析&#xff08;Escape Analysis&#xff0…...

回溯--数据在内存中的存储:整数、大小端和浮点数的深度解析

目录 引言 1. 整数在内存中的存储 1.1 原码、反码和补码 1.2 为什么使用补码&#xff1f; 1.3 示例代码&#xff1a;整数的存储 2. 大小端字节序和字节序判断 2.1 什么是大端和小端&#xff1f; 2.2 为什么会有大端和小端之分&#xff1f; 2.3 字节序的判断小程序 2.…...

第二十二章 Spring之假如让你来写AOP——Target Object(目标对象)篇

Spring源码阅读目录 第一部分——IOC篇 第一章 Spring之最熟悉的陌生人——IOC 第二章 Spring之假如让你来写IOC容器——加载资源篇 第三章 Spring之假如让你来写IOC容器——解析配置文件篇 第四章 Spring之假如让你来写IOC容器——XML配置文件篇 第五章 Spring之假如让你来写…...

探索设计模式:原型模式

设计模式之原型模式 &#x1f9d0;1. 概念&#x1f3af;2. 原型模式的作用&#x1f4e6;3. 实现1. 定义原型接口2. 定义具体的原型类3. 定义客户端4. 结果 &#x1f4f0; 4. 应用场景&#x1f50d;5. 深拷贝和浅拷贝 在面向对象编程中&#xff0c;设计模式是一种通用的解决方案…...

NLP论文速读(EMNLP 2023)|工具增强的思维链推理

论文速读|ChatCoT: Tool-Augmented Chain-of-Thought Reasoning on Chat-based Large Language Models 论文信息&#xff1a; 简介&#xff1a; 本文背景是关于大型语言模型&#xff08;LLMs&#xff09;在复杂推理任务中的表现。尽管LLMs在多种评估基准测试中取得了优异的成绩…...

JVM垃圾回收详解.②

空间分配担保 空间分配担保是为了确保在 Minor GC 之前老年代本身还有容纳新生代所有对象的剩余空间。 《深入理解 Java 虚拟机》第三章对于空间分配担保的描述如下&#xff1a; JDK 6 Update 24 之前&#xff0c;在发生 Minor GC 之前&#xff0c;虚拟机必须先检查老年代最大…...

什么是事务,事务有什么特性?

事务的四大特性&#xff08;ACID&#xff09; 原子性&#xff08;Atomicity&#xff09; 解释&#xff1a;原子性确保事务中的所有操作要么全部完成&#xff0c;要么全部不做。这意味着事务是一个不可分割的工作单元。在数据库中&#xff0c;这通常通过将事务的操作序列作为一个…...

深入解析:如何使用 PyTorch 的 SummaryWriter 进行深度学习训练数据的详细记录与可视化

深入解析&#xff1a;如何使用 PyTorch 的 SummaryWriter 进行深度学习训练数据的详细记录与可视化 为了更全面和详细地解释如何使用 PyTorch 的 SummaryWriter 进行模型训练数据的记录和可视化&#xff0c;我们可以从以下几个方面深入探讨&#xff1a; 初始化 SummaryWriter…...

企业微信中设置回调接口url以及验证 spring boot项目实现

官方文档&#xff1a; 接收消息与事件&#xff1a; 加密解密文档&#xff1a;加解密库下载与返回码 - 文档 - 企业微信开发者中心 下载java样例 加解密库下载与返回码 - 文档 - 企业微信开发者中心 将解压开的代码 ‘将文件夹&#xff1a;qq\weixin\mp\aes的代码作为工具拷…...

电脑超频是什么意思?超频的好处和坏处

嗨&#xff0c;亲爱的小伙伴&#xff01;你是否曾经听说过电脑超频&#xff1f;在电脑爱好者的圈子里&#xff0c;这个词似乎非常熟悉&#xff0c;但对很多普通用户来说&#xff0c;它可能还是一个神秘而陌生的存在。 今天&#xff0c;我将带你揭开超频的神秘面纱&#xff0c;…...

在 AMD GPU 上构建深度学习推荐模型

Deep Learning Recommendation Models on AMD GPUs — ROCm Blogs 2024 年 6 月 28 日 发布者 Phillip Dang 在这篇博客中&#xff0c;我们将演示如何在支持 ROCm 的 AMD GPU 上使用 PyTorch 构建一个简单的深度学习推荐模型 (DLRM)。 简介 DLRM 位于推荐系统和深度学习的交汇…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...