[Algorithm][滑动窗口][无重复字符的最长字串][最大连续的一个数 Ⅲ][将x减到0的最小操作数]详细讲解

本文主要是介绍[Algorithm][滑动窗口][无重复字符的最长字串][最大连续的一个数 Ⅲ][将x减到0的最小操作数]详细讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1.无重复字符的最长字串
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现
  • 2.最大连续的一个数 Ⅲ
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现
  • 3.将x减到0的最小操作数
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现


1.无重复字符的最长字串

1.题目链接

  • 无重复字符的最长字串

2.算法原理详解

  • 研究的对象依旧是⼀段连续的区间,因此继续使⽤「滑动窗⼝」思想来优化
    • 滑动窗口 + 哈希表(判断字符是否重复出现)
  • 让滑动窗⼝满⾜:窗⼝内所有元素都是不重复的
  • 做法:右端元素s[right]进⼊窗⼝的时候,哈希表统计这个字符的频次
    • 如果这个字符出现的频次超过1 ,说明窗⼝内有重复元素
      • 那么就从左侧开始划出窗⼝, 直到s[right]这个元素的频次变为1,然后再更新结果
    • 如果没有超过1,说明当前窗⼝没有重复元素,可以直接更新结果
      请添加图片描述

3.代码实现

int LengthOfLongestSubstring(string s) 
{int n = s.size(); int ret = 0;int hash[128] = { 0 }; // 利用hash查重for(int left = 0, right = 0; right < n; right++){hash[s[right]]++; // 入窗口while(hash[s[right]] > 1){hash[s[left++]]--; // 出窗口}ret = max(ret, right - left + 1); // 更新结果}return ret;
}

2.最大连续的一个数 Ⅲ

1.题目链接

  • 最大连续的一个数 Ⅲ

2.算法原理详解

  • 不要去想怎么翻转,不要把问题想的很复杂
    • 这道题的结果⽆⾮就是⼀段连续的1中间塞了k个0
  • 问题转化为:子数组内,0的个数不超过k
    • 既然是连续区间,可以考虑使⽤**「滑动窗⼝」**来解决问题
  • 做法:当right < nums.size()时,⼀直下列循环:
    • 让当前元素进⼊窗⼝
      • 1 -> 无视
      • 0 -> zero++
    • 检查0的个数是否超标
      • 如果超标,依次让左侧元素滑出窗⼝
      • 顺便更新zero的值,直到0的个数恢复正常
    • 程序到这⾥,说明窗⼝内元素是符合要求的,更新结果
    • right++,处理下⼀个元素
      请添加图片描述

3.代码实现

int LongestOnes(vector<int>& nums, int k) 
{// 问题转化为,子数组内,0的个数不超过kint ret = 0;for(int left = 0, right = 0, zero = 0; right < nums.size(); right++){if(nums[right] == 0){zero++; // 入窗口}while(zero > k){if(nums[left++] == 0){zero--;}}ret = max(ret, right - left + 1);}return ret;
}

3.将x减到0的最小操作数

1.题目链接

  • 将x减到0的最小操作数

2.算法原理详解

  • 要求是数组「左端+右端」两段连续的、和为x的最短数组
    • 可以转化成求数组内⼀段连续的、和为sum(nums) - x的最⻓数组
      • 即:将两端转化为中间连续
    • 此时,就是熟悉的**「滑动窗⼝」**问题了
  • 做法
    • 转化问题:求target = sum(nums) - x
      • 如果target < 0,问题⽆解
    • 初始化左右指针left = 0, right = 0(滑动窗⼝区间表⽰为 [ l , r ) [l, r) [l,r)
      • 左右区间是否开闭很重要,必须设定与代码⼀致
      • 记录当前滑动窗⼝内数组和的变量sum = 0
      • 记录当前满⾜条件数组的最⼤区间⻓度len = -1
    • right < nums.size()时,⼀直循环:
      • if sum < target
        • right++,直⾄sum >= target ,或right已经移到头
      • if sum > target
        • left++,直⾄sum <= target ,或left已经移到头
      • 如果经过前两步的左右移动使得sum == target
        • 维护满⾜条件数组的最⼤⻓度,并让下个元素进⼊窗⼝
          请添加图片描述

3.代码实现

int MinOperations(vector<int>& nums, int x) 
{// 将模型转化为最长子数组的和 == (sumNum - x)int sum = 0, ret = -1;int target = -x;for(auto& e : nums){target += e;}// 细节处理,当target为负数时,怎么减都减不够if(target < 0){return -1;}for(int left = 0, right = 0; right < nums.size(); right++){sum += nums[right]; // 入窗口while(sum > target) // 判断{sum -= nums[left++]; // 出窗口}if(sum == target){ret = max(ret, right - left + 1); // 更新结果}}return ret == -1 ? -1 : nums.size() - ret;
}

这篇关于[Algorithm][滑动窗口][无重复字符的最长字串][最大连续的一个数 Ⅲ][将x减到0的最小操作数]详细讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

SpringBoot改造MCP服务器的详细说明(StreamableHTTP 类型)

《SpringBoot改造MCP服务器的详细说明(StreamableHTTP类型)》本文介绍了SpringBoot如何实现MCPStreamableHTTP服务器,并且使用CherryStudio... 目录SpringBoot改造MCP服务器(StreamableHTTP)1 项目说明2 使用说明2.1

从入门到进阶讲解Python自动化Playwright实战指南

《从入门到进阶讲解Python自动化Playwright实战指南》Playwright是针对Python语言的纯自动化工具,它可以通过单个API自动执行Chromium,Firefox和WebKit... 目录Playwright 简介核心优势安装步骤观点与案例结合Playwright 核心功能从零开始学习

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

PostgreSQL中rank()窗口函数实用指南与示例

《PostgreSQL中rank()窗口函数实用指南与示例》在数据分析和数据库管理中,经常需要对数据进行排名操作,PostgreSQL提供了强大的窗口函数rank(),可以方便地对结果集中的行进行排名... 目录一、rank()函数简介二、基础示例:部门内员工薪资排名示例数据排名查询三、高级应用示例1. 每

nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析(结合应用场景)

《nginx-t、nginx-sstop和nginx-sreload命令的详细解析(结合应用场景)》本文解析Nginx的-t、-sstop、-sreload命令,分别用于配置语法检... 以下是关于 nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析,结合实际应

Spring boot整合dubbo+zookeeper的详细过程

《Springboot整合dubbo+zookeeper的详细过程》本文讲解SpringBoot整合Dubbo与Zookeeper实现API、Provider、Consumer模式,包含依赖配置、... 目录Spring boot整合dubbo+zookeeper1.创建父工程2.父工程引入依赖3.创建ap

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键(私钥)的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与