算法2:滑动窗口(上)

文章目录

  • 长度最小子数组
  • 无重复字符的最长子串
  • [最大连续 1 的个数III](https://leetcode.cn/problems/max-consecutive-ones-iii/description/)
  • 将x减到0的最小操作数

长度最小子数组

在这里插入图片描述

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int len = INT_MAX;int right = 0, left = 0;int sum = 0;while(left <= right && right < nums.size()){sum += nums[right++];//进窗口while(sum >= target) //判断{len = min(len, right - left);sum -= nums[left++]; // 出窗口}}return len == INT_MAX ? 0 : len;}
};

无重复字符的最长子串

在这里插入图片描述

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.size();int left = 0, right = 0;int hash[127] = {0};int res = 0;while (right < n) {hash[s[right]]++; // 进窗口,右端滑动if (hash[s[right]] > 1) {while (hash[s[left]] != hash[s[right]])hash[s[left++]]--;hash[s[left++]]--;} else {res = max(res, right - left + 1);}right++;}return res;}
};

int max(int a, int b)
{return a > b ? a : b;
}
int lengthOfLongestSubstring(char * s){int n = strlen(s);int left = 0, right = 0, res = 0;int hash[127] = {0};while(right < n){hash[s[right]]++;while(hash[s[right]] > 1)hash[s[left++]]--;res = max(res,right - left + 1);right++;}return res;
} 

解析:
在这里插入图片描述


最大连续 1 的个数III

在这里插入图片描述

在这里插入图片描述

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int res = 0,zero = 0;for(int left = 0,right = 0; right < nums.size();right++){if(nums[right] == 0)    zero++;//进窗口while(zero > k){if(nums[left++] == 0) zero--;}    res = max(res,right - left + 1);}return res;}
};
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0, right = 0;int zero = 0, res = 0;while (right < nums.size()) {// 进窗口while (right < nums.size() && nums[right])right++;// 判断if (right < nums.size() && ++zero <= k) {right++;// 数据更新res = max(res, right - left);} else {// 数据更新res = max(res, right - left);// 出窗口while (left < right && nums[left])left++;k--;left++;right++;}}return res;}
};

将x减到0的最小操作数

在这里插入图片描述

正难则反

该题从正面去解,一会儿左一会儿右全凭场景所变化,编码写起来非常繁琐;此时,运用数学思维反证法来解决会不会简单些呢?该题需要求最小操作数,那也就意味着剩下的数据量是最大的,而且因为每次操作都在最左或者最右边,那也就是说剩下的数据是原数据的连续子串;OK,现在我们只需要求出一个符合的尽可能保证数据量大其sum值等于sum(nums) - x连续子串即可.

那现在将符合要求数据看成一个窗口往后滑动即可。

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = 0;for(int e : nums)   sum += e;if(x > sum) return -1;if(x == sum) return nums.size();int target = sum - x;int res = -1;for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++){tmp += nums[right];//进窗口while(tmp >= target){if(tmp == target)   res = max(res, right - left +1);//判断+记录长度tmp -= nums[left++];// 出窗口}}if(res == -1)return res;return nums.size() - res;}
};
class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = 0;for (int e : nums)sum += e;if (x > sum)return -1;//细节int target = sum - x;int res = -1;for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++) {tmp += nums[right]; // 进窗口while (tmp > target) // 判断tmp -= nums[left++]; // 出窗口if (tmp == target)res = max(res, right - left + 1); // 更新数据}if (res == -1)return res;return nums.size() - res;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue3中基于element-plus封装一个表格弹框组件,要求可以单选和多选table数据

单选&#xff1a; <template><SelectMaterialref"selectMaterialRef"check"checkbox"select"selectMaterial"></SelectMaterial><el-button type"primary" size"small" icon"el-icon-plus"…

Web API——获取DOM元素

目录 1、根据选择器来获取DOM元素 2.、根据选择器来获取DOM元素伪数组 3、根据id获取一个元素 4、通过标签类型名获取所有该标签的元素 5、通过类名获取元素 目标&#xff1a;能查找/获取DOM对象 1、根据选择器来获取DOM元素 语法&#xff1a; document.querySelector(css选择…

RedisTemplate操作Redis, 看这一篇文章就够了

文章目录 1. String 命令1.1 添加缓存1.2 设置过期时间(单独设置)1.3 获取缓存值1.4 删除key1.5 顺序递增1.6 顺序递减1.7 常用的 2. Hash命令2.1 添加缓存2.2 设置过期时间(单独设置)2.3 添加一个Map集合2.4 提取所有的小key2.5 提取所有的value值2.6 根据key提取value值2.7 获…

C语言-牛客-实现四舍五入

欢迎来到Harper.Lee的学习小世界&#xff01; 博主主页传送门&#xff1a;Harper.Lee的博客主页 想要一起进步的uu欢迎来后台找我哦&#xff01; 本篇博客总结C语言刷题的相关笔记~~~~ #牛客–实现四舍五入 题目描述&#xff1a;随机输入浮点数&#xff0c;输出四舍五入后的整数…

vue中数据已经改变了,但是table里面内容没更新渲染!

解决方案&#xff1a; 给table或者el-table标签上添加一个动态key值&#xff0c;只要数据发生改变&#xff0c;key值变动一下即可 标签上&#xff1a; :key“timeStamp” 初始data&#xff1a;timeStamp:0, 更新数据&#xff1a;this.timeStamp 这样每次更新数据&#xff…

【B站 heima】小兔鲜Vue3 项目学习笔记Day03

文章目录 Home1.Home整体结构搭建和分类实现2. banner轮播图功能3. Home 面板组件封装4.新鲜好物和人气推荐实现5. 图片懒加载指令实现6. Home- product产品列表实现7. Home-GoodsItem 组件封装 一级路由1. 整体认识和路由配置2. 面包屑导航3. 一级分类 - 轮播图的实现4. 激活状…

2024年5月天润融通JAVA二面15-20K

二面 1、聊项目 2、举例说明你在上家公司职级晋升的原因 3、开发者和管理者的区别&#xff0c;你怎么做管理者 4、对sass的理解&#xff0c;包括流程&#xff0c;技术选型 5、springboot如何把bean加载到ioc容器中&#xff0c;ioc容器的理解 6、一万个任务同时执行&#…

内网安全之搭建ADCS证书服务

在域控上安装ADCS服务时&#xff0c;默认会自动配置完LDAPS&#xff0c;如果不是在域控上安装ADCS服务&#xff0c;需要手动配置LDAPS 安装证书服务ADCS 打开服务器管理器——>添加角色和功能 选择“基于角色或基于功能的安装”选项&#xff0c;然后点击下一步 选择“从…

网络协议——Modbus-RTU

目录 1、简介 2、消息格式 3、Modbus寄存器种类说明 4、功能码01H 5、功能码02H 6、功能码03H 7、功能码04H 8、功能码05H 9、功能码06H 10、功能码0FH 11、功能码10H 1、简介 Modbus-RTU&#xff08;Remote Terminal Unit&#xff09;是一种串行通信协议&#xff0…

云和恩墨海外首秀在吉隆坡召开的2024中国智能科技与文化展览会

作为中马建交50周年官方重点推荐的活动之一&#xff0c;2024中国智能科技与文化展览会&#xff08;第四届&#xff09;于5月20至21日在毗邻吉隆坡双子塔的吉隆坡国际会展中心举办。本次展览会获得马来西亚科学技术创新部、马来西亚通讯部、中国驻马来西亚大使馆和马来西亚中华总…

使用Unsloth微调Llama3-Chinese-8B-Instruct中文开源大模型

使用Unsloth微调Llama3-Chinese-8B-Instruct中文开源大模型 微调Llama3-Chinese-8B-InstructLlama-3-Chinese-8B-InstructUnsloth环境设置下载预训练模型加载model、tokenizer设置LoRA训练参数准备数据集数据处理训练超参数配置开始训练模型推理保存LoRA模型加载模型保存完整模…

OpsManage基于docker的部署与使用

前言 自动化运维管理工具OpsManagerhttp://mp.weixin.qq.com/s?__bizMzk0NTQ3OTk3MQ&mid2247487736&idx1&snefef3a930b88649033f61942a77f42d2&chksmc31598b4f46211a240ffc5360ae238b27d0f495fcbe8dc18abdbd79bc25c00726f74a7312dd0&scene21#wechat_redi…

[IMX6ULL驱动开发]-Linux对中断的处理(一)

目录 中断概念的引入 ARM架构中断的流程 异常向量表 Linux系统对中断的处理 ARM对程序和中断的处理 Linux进程中断处理 中断概念的引入 如何理解中断&#xff0c;我们可以进行如下抽象。把CPU看做一个母亲&#xff0c;当它正在执行任务的时候&#xff0c;可以看为是一个母…

【css】引入背景图时候,路径写入@会报错

看报错信息 我的写法 解决办法 在前面加个~

ThreadLocal原理及使用

一、引言 在Java多线程编程中&#xff0c;ThreadLocal是一个非常有用的工具&#xff0c;它提供了一种将对象与线程关联起来的机制&#xff0c;使得每个线程都可以拥有自己独立的对象副本&#xff0c;从而避免了线程安全问题。然而&#xff0c;使用不当会导致内存泄漏问题。 二…

【VTKExamples::Texture】第六期 TextureThreshold

很高兴在雪易的CSDN遇见你 VTK技术爱好者 QQ:870202403 公众号:VTK忠粉 前言 本文分享VTK样例TextureThreshold,并解析接口vtkTexture,希望对各位小伙伴有所帮助! 感谢各位小伙伴的点赞+关注,小易会继续努力分享,一起进步! 你的点赞就是我的动力(^U^)ノ~Y…

python使用base加密解密

原理 base编码是一种加密解密措施&#xff0c;目前常用的有base16、base32和base64。其大致原理比较简单。 以base64为例&#xff0c;base64加密后共有64中字符。其加密过程是编码后将每3个字节作为一组&#xff0c;这样每组就有3*824位。将每6位作为一个单位进行编码&#xf…

MySQL主从复制+读写分离(ShardingJDBC)

MySQL主从复制读写分离 MySQL主从复制介绍二进制日志&#xff1a; MySQL的主从复制原理如下搭建主从复制准备工作主库配置从库配置 测试 读写分离案例ShardingJDBC介绍数据库环境初始工程导入读写分离配置测试1). 保存数据2). 修改数据3). 查询数据4). 删除数据 MySQL主从复制 …

vue3结合element-plus之如何优雅的使用表格

背景 表格组件的使用在后台管理系统中是非常常见的,但是如果每次使用表格我们都去一次一次地从 element-plus 官网去 复制、粘贴和修改成自己想要的表格。 这样一来也说得过去,但是如果我们静下来细想不难发现,表格的使用都是大同小异的,每次都去复制粘贴,对于有很多表格…

【日记】跟奇安信斗智斗勇,败下阵来(416 字)

正文 今天一个客户都没有&#xff0c;让我快怀疑我们银行是不是要倒闭了…… 因为内外网 u 盘不知所踪&#xff0c;所以重新制了一个。深刻体会到了奇安信有多烂。有两个 u 盘&#xff0c;奇安信似乎把主控写坏了&#xff0c;插上电脑有反应&#xff0c;但是看不见盘符&#xf…