leetcode 3. 无重复字符的最长子串

代码:

//采用滑动窗口来进行解决
class Solution {
    public int lengthOfLongestSubstring(String s) {
        //字符串由英文字母、数字、符号和空格组成,通过对应的 ASCLL 码作为下标在数组中记录出现的次数
        //判断字符在字串中是否重复出现
        int[] ascll=new int[128];
        int maxLength=0;
        int length=s.length();
        int left=0;
        int right=0;
        char[] numsS=s.toCharArray();

        while (right<length){
            //将 right 指针指向的字符添加到要讨论的子串中
            ascll[numsS[right]]++;
            //判断字串中是否有重复字符
            while (ascll[numsS[right]]>1){
                //有重复字符
                //将 left 指针指向的字符从要讨论的字串中去除,再将 left 指针向右移动
                ascll[numsS[left++]]--;

            }
            //没有重复字符
            //把当前讨论的字串的长度与 maxLength 中记录的长度进行比较,记录大的值
            maxLength=Math.max(right-left+1,maxLength);
            right++;
        }

        return maxLength;
    }
}

题解:

         该题我们可以采用滑动窗口的方法来解决,对于子数组,字串的题都经常用到滑动窗口的解决方法

        题目的要求是:1.要获得最长子串的长度  2.子串中不含有重复字符

        我们首先看到题目后可以想到的暴力解法就是,去获取字符串中所有的子串,筛选出不含有重复字符的字串,获取其中最长子串的长度,而滑动窗口方法就是在这基础上进行优化

        我们以题目给出的示例 1 来进行说明,输入: s = "abcabcbb",一般遇到输入为字符串的题,通常都需要把字符串转换为字符数组,方便操作

        1.我们用 L 指针和 R 指针来遍历字符串,获取字符串的子串(L 和 R 指针之间的字符便是我们当前要讨论的子串),让 L 指针和 R 指针指向 0 下标,此时我们要讨论的子串就是 a,a 里面没有重复的字符,所以我们可以记录该子串的长度,问题来了,我们如何判断当前子串有没有重复的字符呢?我们可以定义一个数组 ascll ,ascll 数组的下标代表字符的 ASCLL 码,数组中的值就代表 ASCLL 码对应的字符在子串中的个数,所以当 R 指针指向 a 时,就将 ascll 数组中,a字符的个数加1,拼接到子串中的字符就是 R 指针指向的字符,即使出现重复,也只会是刚刚拼接的字符重复,所以我们只需要判断刚刚拼接的字符的个数是否大于1,就知道当前讨论的子串中是否出现重复字符,此时 a 字符在 ascll 数组中记录的个数为1,所以该子串不含有重复字符

a        b        c        a        b        c        b        b

L

R        

        2.加长讨论的子串长度,R 指针向右移动,将 R 指针指向的 b 字符添加到要讨论的子串中,即将 b 字符在 ascll 数组中的记录数加1,此时 b 字符在 ascll 数组中的记录数为 1 ,所以该子串 ab 不含有重复字符,于是更新最大子串的长度(取当前子串长度和之前记录的最大长度较大的值

a        b        c        a        b        c        b        b

L

          R 

        3.进行重复的操作,当 R 指针指向当前位置后,将 a 字符在 ascll 数组中的记录数加1,此时 a 字符在 ascll 数组中的记录数为 2,所以当前讨论的子串 abca 中含有重复字符,代表以当前 L 指针指向的字符为首位的字符串讨论完毕,将 L 指针向右移动,讨论以下一个字符为首位的字符串

a        b        c        a        b        c        b        b

L

                              R   

        4.讨论以下一个字符为首位的字符串时涉及到一个问题,R 指针需要回到 L 指针所在的位置进行讨论吗?答案是不需要,因为 R 指针之前的数据已经证明是不含有重复字符的子串了,所以即使 R 指针回到 L 指针所在的位置,R 指针也会遍历到当前位置,所以我们直接讨论当前的 bca 子串中是否有重复字符即可,当 L 指针向右移动后,a 字符就不在要讨论的子串中了,在 ascll 数组中的记录数就减1,此时 a 字符在 ascll 数组中的记录数为 1,所以当前讨论的子串 bca 中不含有重复字符,于是更新最大子串的长度(取当前子串长度和之前记录的最大长度较大的值

a        b        c        a        b        c        b        b

          L     

                              R   

        5.后面的操作就是循环操作了,直到 R 指针到达 nums.length 的位置循环结束

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

前端对浏览器的理解

浏览器的主要构成 用户界面 &#xff0d; 包括地址栏、后退/前进按钮、书签目录等&#xff0c;也就是你所看到的除了用来显示你所请求页面的主窗口之外的其他部分。 浏览器引擎 &#xff0d; 用来查询及操作渲染引擎的接口。 渲染引擎 &#xff0d; 用来显示请求的内容&#…

深入理解同源限制:网络安全的守护者(下)

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…

我爱上这38个酷炫的数据大屏(附 Python 源码)

随着大数据的发展&#xff0c;可视化大屏在各行各业得到越来越广泛的应用。 可视化大屏不再只是电影里奇幻的画面&#xff0c;而是被实实在在地应用在政府、商业、金融、制造等各个行业的业务场景中&#xff0c;切切实实地实现着大数据的价值。 所以本着学习的态度&#xff0…

四、设置主机名和域名映射

目录 1、配置每台虚拟机主机名 2、配置每台虚拟机域名映射 1、配置每台虚拟机主机名

MATLAB实战 | S函数的设计与应用

S函数用于开发新的Simulink通用功能模块&#xff0c;是一种对模块库进行扩展的工具。S函数可以采用MATLAB语言、C、C、FORTRAN、Ada等语言编写。在S函数中使用文本方式输入公式、方程&#xff0c;非常适合复杂动态系统的数学描述&#xff0c;并且在仿真过程中可以对仿真进行更精…

ASP.NET版本WOL服务的使用

本文以WOL为例&#xff0c;演示如何通过 GPT-4 让其为 WebAPI 项目设计一个网页。其中介绍了如何让GPT4生成相关功能&#xff0c;添加动画效果&#xff0c;接口鉴权等。 1. 背景 前面我们已经完成了一个WOL服务的开发&#xff0c;并将其迁移改造为了 ASP.NET 服务并完成了部署…

02数仓平台Zookeeper

概述 ZooKeeper是一种分布式协调服务&#xff0c;用于管理大型主机集。在分布式环境中协调和管理服务是一个复杂的过程。ZooKeeper通过其简单的架构和API解决了这个问题。ZooKeeper允许开发人员专注于核心应用程序逻辑&#xff0c;而不必担心应用程序的分布式性质。 Zookeepe…

DBeaver 社区版(免费版)下载、安装、解决驱动更新出错问题

DBeaver 社区版&#xff08;免费版&#xff09; DBeaver有简洁版&#xff0c;企业版&#xff0c;旗舰版&#xff0c;社区版&#xff08;免费版&#xff09;。除了社区版&#xff0c;其他几个版本都是需要付费的&#xff0c;当然相对来说&#xff0c;功能也要更完善些&#xff…

uniApp打包的手机app如果用户没开启通知权限、引导用户开启

封装一个setPermissions.js文件 /*** 如果用户没开启通知权限、引导用户开启 */ export function setPermissions() {// #ifdef APP-PLUS if (plus.os.name Android) {var main plus.android.runtimeMainActivity();var pkName main.getPackageName();var uid main.getApp…

某公司前端笔试题(12.30)

1、对象数组去重&#xff1a; 数组去重&#xff1a; const a[{a:1,b:2},{a:2},{a:2},{a:1,c:3},{b:2,a:1}] 结果&#xff1a;[{a:1,b:2},{a:2},{a:1,c:3}] // 判断两个对象的属性值是否一致 const a [{ a: 1, b: 2 }, { a: 2 }, { a: 2 }, { a: 1, c: 3 }, { b: 2, a: 1 }] co…

elupload base64

创作灵感也许就是这会儿还没有入睡吧&#xff0c;对接百度图片OCR功能&#xff0c;需要将图片转为BASE64上传调用百度的接口api&#xff0c;进行研究实现。页面如下&#xff0c;点击后选择图片文件后不是直接上传&#xff0c;而是获取图片的bytes数据&#xff01; <el-uploa…

2012-2021年银行数字化转型程度数据(根据年报词频计算)

2012-2021年银行数字化转型程度&#xff08;根据年报词频计算&#xff09; 1、时间&#xff1a;2012-2021年 2、指标&#xff1a;银行名称、年份、数字化转型程度 3、范围&#xff1a;52家银行&#xff08;上海银行、中信银行、中国银行、交通银行、光大银行、兰州银行、兴业…

国标GBT 27930关键点梳理

1、充电总流程 整个充电过程包括六个阶段:物理连接完成、低压辅助上电、充电握手阶段、充电参数配置阶段、充电阶段和充电结束阶段。 在各个阶段,充电机和 BMS 如果在规定的时间内没有收到对方报文或没有收到正确报文,即判定为超时(超时指在规定时间内没有收到对方的完整数据包…

每日一练2023.12.2——正整数A+B【PTA】

题目链接&#xff1a;L1-025 正整数AB 题目要求&#xff1a; 题的目标很简单&#xff0c;就是求两个正整数A和B的和&#xff0c;其中A和B都在区间[1,1000]。稍微有点麻烦的是&#xff0c;输入并不保证是两个正整数。 输入格式&#xff1a; 输入在一行给出A和B&#xff0c;…

webGIS使用JS,高德API完成简单的智慧校园项目基础

代码实现 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-width, i…

MySQL5.7安装与配置:自动化一键安装配置

介绍 本文介绍了一个自动化安装MySQL的Shell脚本。该脚本可以帮助用户快速安装MySQL&#xff0c;并自动进行配置和初始化。通过使用该脚本&#xff0c;用户无需手动执行繁琐的安装步骤&#xff0c;大大简化了MySQL的安装过程。 使用shell自动化安装教程 1. 复制脚本 首先&a…

wordpress路径怎么优化?wordpress伪静态怎么做?

Wordpress这个程序是动态的&#xff0c;在后台中设置链接的格式为朴素&#xff0c;就可以了&#xff0c;这样简单又方便&#xff0c;因为百度对于路径的都是一样对待的&#xff0c;静态路径和动态路径&#xff0c;都是一样的对待。 有的时候&#xff0c;有的人会认为动态路径不…

2023年中国消费金融行业研究报告

第一章 行业概况 1.1 定义 中国消费金融行业&#xff0c;作为国家金融体系的重要组成部分&#xff0c;旨在为消费者提供多样化的金融产品和服务&#xff0c;以满足其消费需求。这一行业包括银行、消费金融公司、小额贷款公司等多种金融机构&#xff0c;涵盖了包括消费贷款在内…

网上选课系统源码(Java)

JavaWebjsp网上选课系统源码 运行示意图&#xff1a;

SqlServer_分页_OFFSET_FETCH

使用SQL server分页 使用SQL server分页的时候踩了一个坑&#xff1a; 用mybatis-plus分页的时候始终报错 代码&#xff1a;Page<SystemDictCatalog> page new Page<>(data.getPage(), data.getLimit()); QueryWrapper<SystemDictCatalog> wrapper new Qu…