算法 —— 滑动窗口
目录
长度最小的子数组
无重复字符的最长子串
最大连续1的个数
将x减到0的最小操作数
找到字符串中所有字母异位词
最小覆盖子串
长度最小的子数组
sum比target小就进窗口,sum比target大就出窗口,由于数组是正数,所以相加会使sum变大,相减会使sum变小,至于为什么可以这样做,这其实是在暴力枚举的基础上进行了优化,例如2,3,1,2相加等于8已经超过target,这样就不需要继续加后面的4,3,因为此时已经满足条件,我们要做的是在满足要求的基础上使len尽量小。
代码实现如下:
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum = 0, len = INT_MAX, n = nums.size();for (int right = 0, left = 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;}
};
无重复字符的最长子串
利用哈希表记录字符个数,注意本题字符包括数字,字母及空格,意味着我们要开一个128大小的数组。代码实现如下:
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = { 0 }; // 使用数组来模拟哈希表int n = s.size(), len = 0;for (int left = 0, right = 0; right < n;right++){hash[s[right]]++; // 进窗口while (hash[s[right]] == 2) // 判断{hash[s[left++]]--; // 出窗口}len = max(len, right - left + 1); // 更新结果}return len;}
};
最大连续1的个数
和上题类似,通过滑动窗口,调节0的个数,最关键的在于将题目意思转换为找不超过k个0的子数组,如果超过k就出窗口,未超过就进窗口,代码实现如下:
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int zero = 0, len = 0; // 计数器for (int left = 0, right = 0; right < nums.size(); right++){if (nums[right] == 0) // 进窗口zero++; // 计数while (zero > k) // 判断{if (nums[left] == 0)zero--;left++; // 出窗口}len = max(len, right - left + 1);}return len;}
};
将x减到0的最小操作数
本题思想为正难则反,如果题目正向思考困难,可以从另外一方面思考,例如本题要找最短长度,且元素可能在左右端口出现,另外最短长度数组元素之和刚好为x,这个代码实现起来过于麻烦,可以想找一个最长长度的子数组,使他元素之和刚好为sum - x,这样又转化为滑动窗口问题。
注意:len不能设置为0,因为有可能整个数组都是构成x的元素,最终判断是否存在时不能用len == 0 这个判断式来判断数组是否存在子数组可以将x减到0,应当设置为-1。另外,该题只有在sum2 == target时才能更新结果,否则不更新。代码如下:
class Solution {
public:int minOperations(vector<int>& nums, int x) {// 记算整个数组的和int sum1 = 0, n = nums.size();for (auto e : nums){sum1 += e;}// 找出最长子数组的和 sum1 - xint target = sum1 - x, len = -1, sum2 = 0;// 处理细节问题if (target < 0)return -1;// 滑动窗口解决问题for (int left = 0, right = 0; right < n; right++){sum2 += nums[right]; // 进窗口while (sum2 > target) // 判断sum2 -= nums[left++]; // 出窗口if (sum2 == target)len = max(len, right - left + 1); // 更新结果}if (len == -1)return len;elsereturn n - len;}
};
找到字符串中所有字母异位词
在更新结果时不需要遍历两个哈希表,通过count计数器来判断hash2里的有效个数是否和m相等即可,代码实现如下:
class Solution {
public:vector<int> findAnagrams(string s, string p) {int hash1[26] = { 0 }, hash2[26] = { 0 }, n = s.size(), m = p.size();// 统计 p 的每个字符出现的次数for (auto e : p)hash1[e - 'a']++;vector<int> ret;// 统计 s 的每个字符出现的次数for (int left = 0, right = 0,count = 0; right < n; right++){char in = s[right];if (++hash2[in - 'a'] <= hash1[in - 'a']) // 进窗口 + 维护 countcount++;if (right - left + 1 > m) // 判断{char out = s[left++];if (hash2[out - 'a']-- <= hash1[out - 'a']) // 出窗口 + 维护 countcount--;}// 更新结果if (count == m)ret.push_back(left);}return ret;}
};
最小覆盖子串
class Solution {
public:string minWindow(string s, string t) {int hash1[128] = { 0 }, hash2[128] = { 0 };int hash1_kinds = 0;for (auto e : t)if (hash1[e]++ == 0) hash1_kinds++; // 记录子串字母种类int begin = -1, minlen = INT_MAX;for (int left = 0, right = 0,count = 0;right < s.size();right++){char in = s[right];if (++hash2[in] == hash1[in])count++; // 进窗口while (count == hash1_kinds) // 判断条件{char out = s[left];if (right - left + 1 < minlen) // 更新结果{begin = left; minlen = min(right - left + 1, minlen);}if (hash2[out]-- == hash1[out])count--; // 出窗口left++;}}if (begin == -1)return "";elsereturn s.substr(begin, minlen);}
};
相关文章:
算法 —— 滑动窗口
目录 长度最小的子数组 无重复字符的最长子串 最大连续1的个数 将x减到0的最小操作数 找到字符串中所有字母异位词 最小覆盖子串 长度最小的子数组 sum比target小就进窗口,sum比target大就出窗口,由于数组是正数,所以相加会使sum变大&…...
【设计模式】工厂模式(定义 | 特点 | Demo入门讲解)
文章目录 定义简单工厂模式案例 | 代码Phone顶层接口设计Meizu品牌类Xiaomi品牌类PhoneFactory工厂类Customer 消费者类 工厂方法模式案例 | 代码PhoneFactory工厂类 Java高级特性---工厂模式与反射的高阶玩法方案:反射工厂模式 总结 其实工厂模式就是用一个代理类帮…...
Linux之计划和日志
计划任务 计划任务概念解析 在Linux操作系统中,除了用户即时执行的命令操作以外,还可以配置在指定的时间、指定的日期执行预先计划好的系统管理任务(如定期备份、定期采集监测数据)。通过安装at和crontabs这两个系统服务实现一次性、周期性计划任务的功能,并分别通过at、…...
C++ 多态篇
文章目录 1. 多态的概念和实现1.1 概念1.2 实现1.2.1 协变1.2.2 析构函数1.2.3 子类虚函数不加virtual 2. C11 final和override3.1 final3.2 override 3. 函数重载、重写与隐藏4. 多态的原理5. 抽象类6.单继承和多继承的虚表6.1 单继承6.2 多继承 7. 菱形继承的虚表(了解)7.1 菱…...
【LVGL-SquareLine Studio】
LVGL-SquareLine Studio ■ SquareLine Studio-官网下载地址■ SquareLine Studio-参考博客■ SquareLine Studio-安装■ SquareLine Studio-汉化■ SquareLine Studio-■ SquareLine Studio-■ SquareLine Studio-■ SquareLine Studio-■ SquareLine Studio- ■ SquareLine S…...
mysqli 与mysql 区别和联系, 举例说明
mysqli是一种PHP的扩展,用于与MySQL数据库进行交互。它提供了一套面向对象的接口,可以更方便地操作数据库。MySQL是一种关系型数据库管理系统,用于存储和管理数据。 区别: mysqli是MySQL的扩展,而不是单独的数据库管…...
【SpringCloud应用框架】Nacos安装和服务提供者注册
第二章 Spring Cloud Alibaba Nacos之Nacos安装和服务提供者注册 文章目录 Nacos介绍为何使用Nacos?一、Nacos下载和安装1. 下载2. 安装Linux/Unix/MacWindows 二、Nacos服务提供者注册1. Nacos代替Eureka2. Nacos服务注册中心3. 引入Nacos Discovery进行服务注册/发…...
英语学习交流小程序的设计
管理员账户功能包括:系统首页,个人中心,用户管理,每日打卡管理,备忘录管理,学习计划管理,学习资源管理,论坛交流 微信端账号功能包括:系统首页,学习资源&…...
实现Java多线程中的线程间通信
实现Java多线程中的线程间通信 大家好,我是微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 1. 线程间通信的基本概念 在线程编程中,线程间通信是指多个线程之间通过共享内存或消息传递的方式进行交…...
C++模板元编程(一)——可变参数模板
这个系列主要记录C模板元编程的常用语法 文章目录 引言语法应用函数模板可变参数的打印可变参数的最小/最大函数 类模板 参考文献 引言 在C11之前,函数模板和类模板只支持含有固定数量的模板参数。C11增强了模板功能,允许模板定义中包含任意个(包括0个)…...
kafka中
Kafka RocketMQ概述 RabbitMQ概述 ActiveMQ概述 ZeroMQ概述 MQ对比选型 适用场景-从公司基础建设力量角度出发 适用场景-从业务场景出发 Kafka配置介绍 运行Kafka 安装ELAK 配置EFAK EFAK界面 KAFKA常用术语 Kafka常用指令 Kafka中消息读取 单播消息 group.id 相同 多播消息 g…...
Android 获取当前电池状态
在 API 级别 23 上获取充电状态 要在 API 级别 23 上获取电池的当前状态,只需使用电池管理器系统服务: BatteryManager batteryManager (BatteryManager) getSystemService(BATTERY_SERVICE); boolean isCharging batteryManager.isCharging();使用 S…...
【JVM 的内存模型】
1. JVM内存模型 下图为JVM内存结构模型: 两种执行方式: 解释执行:JVM是由C语言编写的,其中有C解释器,负责先将Java语言解释翻译为C语言。缺点是经过一次JVM翻译,速度慢一点。JIT执行:JIT编译器…...
【雷丰阳-谷粒商城 】【分布式高级篇-微服务架构篇】【17】认证服务01—短信/邮件/异常/MD5
持续学习&持续更新中… 守破离 【雷丰阳-谷粒商城 】【分布式高级篇-微服务架构篇】【17】认证服务01 环境搭建验证码倒计时短信服务邮件服务验证码短信形式:邮件形式: 异常机制MD5参考 环境搭建 C:\Windows\System32\drivers\etc\hosts 192.168.…...
geom buffer制作
1. auto buffer_geom line_string->buffer(15);//buffer //这个是x和y各扩大段15个单位 auto buffer_geom line_string->buffer(15);//buffer //这个是x和y各扩大段15米 获取buffer坐标 auto boundary buffer_geom->getBoundary(); auto boundary_coords boun…...
微软正在放弃React
最近,微软Edge团队撰写了一篇文章,介绍了微软团队如何努力提升Edge浏览器的性能。但在文中,微软对React提出了批评,并宣布他们将不再在Edge浏览器的开发中使用React。 我将详细解析他们的整篇文章内容,探讨这一决定对…...
U盘非安全退出后的格式化危机与高效恢复策略
在数字化时代,U盘作为数据存储与传输的重要工具,其数据安全备受关注。然而,一个常见的操作失误——U盘没有安全退出便直接拔出,随后再插入时却遭遇“需要格式化”的提示,这不仅让用户措手不及,更可能意味着…...
安卓虚拟位置修改
随着安卓系统的不断更新,确保软件和应用与最新系统版本的兼容性变得日益重要。本文档旨在指导用户如何在安卓14/15系统上使用特定的功能。 2. 系统兼容性更新 2.1 支持安卓14/15:更新了对安卓14/15版本的支持,确保了软件的兼容性。 2.2 路…...
大数据面试题之Presto[Trino](5)
目录 Presto的扩展性如何? Presto如何与Hadoop生态系统集成? Presto是否可以连接到NoSQL数据库? 如何使用Presto查询Kafka中的数据? Presto与Spark SQL相比有何优势和劣势? Presto如何与云服务集成࿱…...
对编程开发人员在今年的一些建议
一、今年的大环境 这几天身体不太好,又不断看到地狱级的就业问题。所以有些想法想和大家分享一下,并提出自己的一些想法和建议。今年的大环境不好,做为非专业人士,咱们也不分析,以免贻笑大方。但针对大环境下的计算机…...
VSCode设置好看清晰的字体!中文用鸿蒙,英文用Jetbrains Mono
一、中文字体——HarmonyOS Sans SC 1、下载字体 官网地址:https://developer.huawei.com/consumer/cn/design/resource/ 直接下载:https://communityfile-drcn.op.dbankcloud.cn/FileServer/getFile/cmtyPub/011/111/111/0000000000011111111.20230517…...
SpringBoot新手快速入门系列教程四:创建第一个SringBoot的API
首先我们用IDEA新建一个项目,请将这些关键位置按照我的设置设置一下 接下来我将要带着你一步一步创建一个Get请求和Post请求,通过客户端请求的参数,以json格式返回该参数{“message”:"Hello"} 1,先在IDE左上角把这里改为文件模式…...
第1集《修习止观坐禅法要》
《修习止观坐禅法要》诸位法师,诸位学员,阿弥院佛! 我们今天能够暂时放下世间的尘劳,大家在一起研究佛法的课程,这件事情在我们的生命当中是非常的稀有难得。 基本上,我们佛法的修习目的是追求身心的安乐…...
markdown变量引用
格式 变量定义通常是路径或网络链接 变量测试...
如何使用echart做K线图
使用ECharts制作K线图需要先引入ECharts的库文件,然后通过调用相应的API来配置和渲染K线图。以下是一个简单的示例代码: // 引入ECharts库文件 <script src"https://cdn.jsdelivr.net/npm/echarts5.0.0/dist/echarts.min.js"></scri…...
Spring Boot应用使用GraalVM本地编译相关配置
1. 介绍 Java应用程序可以通过Graalvm Native Image提前编译生成与本地机器相关的可执行文件。与在JVM执行java程序相比,Native Image占用内存更小和启动速度更快。 从spring boot3开始支持GraalVM Native Image,因此要使用此特性,需要把sp…...
代码的坏味道——长函数
前言:一个函数应该尽量做一件事情,如果非要做多个事情,要做函数提取,每次迭代应该考虑到是否有重复代码或者可以优化的代码。 长函数:长函数的产生: 逻辑是平铺直叙的需求迭代没有考虑优化,一次…...
【机器学习】基于密度的聚类算法:DBSCAN详解
🌈个人主页: 鑫宝Code 🔥热门专栏: 闲话杂谈| 炫酷HTML | JavaScript基础 💫个人格言: "如无必要,勿增实体" 文章目录 基于密度的聚类算法:DBSCAN详解引言DBSCAN的基本概念点的分类聚类过…...
Qt 网络编程 网络信息获取操作
学习目标:网络信息获取操作 前置环境 运行环境:qt creator 4.12 学习内容 一、Qt 网络编程基础 Qt 直接提供了网络编程模块,包括基于 TCP/IP 的客户端和服务器相关类,如 QTcpSocket/QTcpServer 和 QUdpSocket,以及实现 HTTP、FTP 等协议的高级类,如 QNetworkRe…...
linux中的进程以及进程管理
程序和进程的区别和联系 程序(Program): 程序是一组指令的集合,通常存储在磁盘或其他存储设备上,是一种静态的概念。程序本身并没有运行,它只是一个可执行的文件或脚本,包含了一系列的指令和数…...
pyecharts可视化案例大全(11~20)
pyecharts可视化案例大全(11~20) 十一、设置动画效果十二、直方图带视觉组件十三、设置渐变色(线性渐变)十四、设置渐变色(径向渐变)十五、设置分割线十六、设置分隔区域十七、面积图十八、堆叠面积图十九、自定义线样式二十、折线图平滑处理十一、设置动画效果 在图表加载前…...
Docker在人工智能领域的应用与实战
摘要 人工智能(AI)技术的快速发展带来了对高效开发和部署工具的需求。Docker作为一个创新的容器化平台,为AI领域提供了强大的支持。本文详细介绍了Docker在AI模型开发、训练、部署以及服务器集群管理等方面的应用,并探讨了其在数…...
python基础篇(8):异常处理
在Python编程中,异常是程序运行时发生的错误,它会中断程序的正常执行流程。异常处理机制使得程序能够捕获这些错误,并进行适当的处理,从而避免程序崩溃。 1 错误类型 代码的错误一般会有语法错误和异常错误两种,语法错…...
FortiClient 用IPsec VPN 远程拨号到FortiGate说明文档
说明:本文档针对IPsec VPN 中的Remote VPN 进行说明,即远程用户使用PC中的FortiClient软件,通过VPN拨号的方式连接到公司总部FortiGate设备,访问公司内部服务器。在配置之前需要统一VPN策略和参数,如模式… 说明&#…...
Git-Unity项目版本管理
目录 准备GitHub新建项目并添加ssh密钥Unity文件夹 本文记录如何用git对unity 项目进行版本管理,并可传至GitHub远端。 准备 名称版本windows11Unity2202.3.9.f1gitN.A.githubN.A. GitHub新建项目并添加ssh密钥 GitHub新建一个repositorywindows11 生成ssh-key&…...
每日一题~ leetcode 402 (贪心+单调栈)
click me! 这个贪心的推导在leetcode上已经很明确了。 click me! 删除k个数,可以先考虑删除一个数。这也是一种常见的思路。(如果进行同样的操作多次,可以先只 考虑一次操作如何实现,或者他的影响。完成这一次操作后,…...
设计模式之模版方法
模版方法介绍 模版方法(Template Method)模式是一种行为型设计模式,它定义了一个操作(模板方法)的基本组合与控制流程,将一些步骤(抽象方法)推迟到子类中,使得子类可以在…...
docker部署redis/mongodb/
一、redis 创建/root/redis/conf/redis.conf 全部执行命令如下 docker run -it -d --name redis -p 6379:6379 --net mynet --ip 172.18.0.9 -m 400m -v /root/redis/conf:/usr/local/etc/redis -e TXAsia/Shangehai redis redis-server /usr/local/etc/redis/redis.conf 部署…...
LeetCode 581. 最短无序连续子数组
更多题解尽在 https://sugar.matrixlab.dev/algorithm 每日更新。 组队打卡,更多解法等你一起来参与哦! LeetCode 581. 最短无序连续子数组,难度中等。 排序 解题思路:首先对数组排序,然后找出两侧顺序的数组&#x…...
数据库可视化管理工具dbeaver试用及问题处理。
本文记录了在内网离线安装数据库可视化管理工具dbeaver的过程和相关问题处理方法。 一、下载dbeaver https://dbeaver.io/download/ 笔者测试时Windows平台最新版本为:dbeaver-ce-24.1.1-x86_64-setup.exe 二、安装方法 一路“下一步”即可 三、问题处理 1、问…...
29、php实现和为S的两个数字(含源码)
题目:php 实现 和为S的两个数字 描述: 输入一个递增排序的数组和一个数字S,在数组中查找两个数, 是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。 输出描述: 对应每个测…...
Spring Boot中的全局异常处理
Spring Boot中的全局异常处理 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!今天我们将探讨如何在Spring Boot应用中实现全局异常处理,这是保证应用…...
中英双语介绍美国苹果公司(Apple Inc.)
中文版 苹果公司简介 苹果公司(Apple Inc.)是一家美国跨国科技公司,总部位于加利福尼亚州库比蒂诺。作为全球最有影响力的科技公司之一,苹果以其创新的产品和设计引领了多个科技领域的变革。以下是对苹果公司发展历史、主要产品…...
C语言牢大坠机
目录 开头程序程序的流程图《牢大坠机》结尾 开头 大家好,我叫这是我58,今天,我们要来看关于牢大坠机的一些东西。 程序 #define _CRT_SECURE_NO_WARNINGS 1 #define HIGH 66 #include <stdio.h> #include <Windows.h> int ma…...
zdppy+vue3+antd 实现表格单元格编辑功能
初步实现 <template><a-button class"editable-add-btn" style"margin-bottom: 8px" click"handleAdd">Add</a-button><a-table bordered :data-source"dataSource" :columns"columns"><templa…...
elasticsearch索引怎么设计
Primary Shard(主分片) Primary Shard(主分片)是索引数据存储的基本单位,承担着数据写入和查询的职责。以下是关于Primary Shard的一些关键点: 1. 数据分布:每个索引在创建时会被分成多个主分…...
React 中 useState 和 useReducer 的联系和区别
文章目录 使用场景使用 useState使用 useReducer 联系区别用法状态更新逻辑适用场景可读性和可维护性 使用场景 使用 useState 状态逻辑简单。只涉及少量的状态更新。需要快速和简单的状态管理。 使用 useReducer 状态逻辑复杂。涉及多个子状态或多种状态更新逻辑。需要更好…...
Linux 定时任务详解:全面掌握 cron 和 at 命令
Linux 定时任务详解:全面掌握 cron 和 at 命令 Linux 系统中定时任务的管理对于运维和开发人员来说都是至关重要的。通过定时任务,可以在特定时间自动执行脚本或命令,提高系统自动化程度。本文将详细介绍 Linux 中常用的定时任务管理工具 cr…...
力扣考研经典题 反转链表
核心思想 头插法: 不断的将cur指针所指向的节点放到头节点之前,然后头节点指向cur节点,因为最后返回的是head.next 。 解题思路 1.如果头节点是空的,或者是只有一个节点,只需要返回head节点即可。 if (head null …...
opencv 设置超时时间
经常爬视频数据,然后用opencv做成图片 因此设置超时时间很重要 cap.set(cv2.CAP_PROP_FPS, timeout_ms) for idx, row in data.iterrows(): if idx < 400: continue try: # 打开视频文件 timeout_ms 5000 cap cv2.VideoCapture(row[PLAY_URL]) cap.set(cv2.C…...