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

算法题3 — 求字符串中的最长子串

文章目录

  • 题目
  • 示例
    • 示例1
    • 示例2
    • 示例3
  • 解题
    • 解法1
    • 解法2
  • leetcode

题目

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

示例

示例1

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

示例2

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

示例3

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

解题

解法1

粗暴破解,找一个最长子串,那么我们用两个循环穷举所有子串,然后再用一个函数判断该子串中有没有重复的字符。


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;/*** @author zxn* @ClassName LongestSubstring* @Description* @createTime 2023年05月24日 20:33:00*/
public class LongestSubstring {public static void main(String[] args) {String s = "abcabcbb";int i = lengthOfLongestSubstring1(s);System.out.println("i="+i);}private static int lengthOfLongestSubstring1(String s) {int n = s.length();int len=0;for (int i = 0; i < n; i++) {for (int j = i+1; j < n; j++) {if (unique(s,i,j)){len = Math.max(len,j-i+1);}}}return len;}public static boolean unique(String s, int start, int end) {Set<Character> set = new HashSet<>();for (int i = start; i <= end; i++) {if (set.contains(s.charAt(i))){return false;}set.add(s.charAt(i));}return true;}

解法2

上边的算法中,我们假设当 i 取 0 的时候,

j 取 1,判断字符串 str[0,1) 中有没有重复的字符。

j 取 2,判断字符串 str[0,2) 中有没有重复的字符。

j 取 3,判断字符串 str[0,3) 中有没有重复的字符。

j 取 4,判断字符串 str[0,4) 中有没有重复的字符。

做了很多重复的工作,因为如果 str[0,3) 中没有重复的字符,我们不需要再判断整个字符串 str[0,4) 中有没有重复的字符,而只需要判断 str[3] 在不在 str[0,3) 中,不在的话,就表明 str[0,4) 中没有重复的字符。

如果在的话,那么 str[0,5) ,str[0,6) ,str[0,7) 一定有重复的字符,所以此时后边的 j 也不需要继续增加了。i ++ 进入下次的循环就可以了。

此外,我们的 j 也不需要取 j + 1,而只需要从当前的 j 开始就可以了。

判断一个字符在不在字符串中,我们需要可以遍历整个字符串,遍历需要的时间复杂度就是 O(n),加上最外层的 i 的循环,总体复杂度就是 O(n²)。我们可以继续优化,判断字符在不在一个字符串,我们可以将已有的字符串存到 Hash 里,这样的时间复杂度是 O(1),总的时间复杂度就变成了 O(n)。

当 j 指向的 字符 存在于前边的子串中,此时 i 向前移到 b ,此时子串中仍然含有字符,还得继续移动,所以这里其实可以优化。我们可以一步到位,直接移动到子串的位置的下一位!


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;/*** @author zxn* @ClassName LongestSubstring* @Description* @createTime 2023年05月24日 20:33:00*/
public class LongestSubstring {public static void main(String[] args) {String s = "abcabcbb";int i = lengthOfLongestSubstring2(s);System.out.println("i="+i);}private static int lengthOfLongestSubstring2(String s) {int n = s.length();int len = 0;Map<Character, Integer> map = new HashMap<>();for (int i = 0, j = 0; j < n; j++) {if (map.containsKey(s.charAt(j))) {i = Math.max(i, map.get(s.charAt(j)));}map.put(s.charAt(j), j + 1);len = Math.max(len, j - i + 1);}return len;}
}

leetcode

leetcode地址

相关文章:

算法题3 — 求字符串中的最长子串

文章目录 题目示例示例1示例2示例3 解题解法1解法2 leetcode 题目 给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。 示例 示例1 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”&#xff0c;所以其长度为 3。 示例…...

【FreeRTOS】——中断优先级设置中断相关寄存器临界段代码保护调度器挂起与恢复

目录 前言&#xff1a; 一、中断优先级设置 二、中断相关寄存器&#xff08;STM32-Cortex M3&#xff09; 三、临界段代码保护 四、任务调度器的挂起和恢复 总结&#xff1a; 前言&#xff1a; 博客笔记根据正点原子视频教程编辑&#xff0c;仅供学习交流使用&#xff0…...

1.2 什么是eBPF?(下)

四,eBPF的优势 4.1 eBPF程序的动态加载 eBPF程序可以动态地加载到内核中,或从内核中删除。这个要与内核模块的加载与卸载区分开来。这里顺便讨论下eBPF程序与内核模块的区别,如下: 而Linux内核模块是面向内核API编程的,可以直接运行在内核当中。eBPF程序是面向BPF体系结构…...

掌握哪些测试技术才能说自己已经学成了?

一、过硬的基础能力 其实所有的测试大佬都是从底层基础开始的&#xff0c;随着时间&#xff0c;经验的积累慢慢变成大佬。要想稳扎稳打在测试行业深耕&#xff0c;成为测试大牛&#xff0c;首当其冲的肯定就是拥有过硬的基础&#xff0c;所有的基础都是根基&#xff0c;后期所…...

什么是C语言?

C语言是一种高级编程语言&#xff0c;于1972年由Dennis Ritchie在贝尔实验室开发出来。它是一种通用的、结构化的编程语言&#xff0c;被广泛用于系统软件、嵌入式系统、游戏开发以及科学计算等领域。 C语言的设计目标是提供一种简洁、高效、可移植的编程语言&#xff0c;以便…...

SAP-物料主数据-质量管理视图字段解析

过账到质检库存&#xff1a;要勾选&#xff0c;否则收货后库存不进入质检库存HU检验&#xff1a;收货到启用HU管理的库位时产生检验批&#xff0c;例如某个成品物料是收货到C002库位&#xff0c;该库位启用了HU管理&#xff0c;那么此处要勾选。但是如果勾选了&#xff0c;却收…...

TOP RPA·脱普×实在丨日用品企业脱普签约实在智能,构建全域数据智能运营系统

近日&#xff0c;实在智能与脱普日用化学品&#xff08;中国&#xff09;有限公司&#xff08;简称“脱普企业”&#xff09;在脱普企业上海总部举行“全域数据智能运营”项目启动会&#xff0c;双方领导及项目组关键成员共同参会&#xff0c;就项目目标、实施进程、沟通机制等…...

【Android】Handler(四)Looper的相关知识点

Handler 机制是 Android 多线程间通信的一种常见方式。每个 Handler 对象由一个 Looper 和一个 MessageQueue 组成&#xff0c;用于将 Message 对象处理到指定的线程中。通过创建 Handler 实例&#xff0c;在子线程中创建 Message 对象并通过sendMessage()方法发送给 Handler&a…...

Redis缓存雪崩及解决办法

缓存雪崩 1.缓存雪崩是指在同- -时段大量的缓存key同时失效或者Redis服务宕机&#xff0c;导致大量请求到 达数据库&#xff0c;带来巨大压力。 2.解决方案: ◆给不同的Key的TTL添加随机值 ◆利用Redis集群提高服务的可用性 ◆给缓存业务添加降级限流策略 降级可做为系统的保底…...

Maven私服仓库配置-Nexus详解

目录 一、什么是Maven私服&#xff1f;二、Maven 私服优势三、Maven 私服搭建四、Sonatype Nexus介绍五、Nexus仓库属性和分类六、Nexus仓库配置以及创建仓库七、Nexus配置用户角色八、Maven SNAPSHOT(快照)九、项目当中配置Nexus上传依赖十、项目当中配置Nexus下载依赖十一、测…...

Systrace系列10 —— Binder 和锁竞争解读

本文主要是对 Systrace 中的 Binder 和锁信息进行简单介绍,简单介绍了 Binder 的情况,介绍了 Systrace 中 Binder 通信的表现形式,以及 Binder 信息查看,SystemServer 锁竞争分析等。 Binder 概述 Android 的大部分进程间通信都使用 Binder,这里对 Binder 不做过多的解释…...

React Hooks中使用useState异步回调获取不到最新值的问题

ReactHook中useState异步回调获取不到最新值及解决⽅案 预先了解 setState 的两种传参⽅式 1、直接传⼊新值 setState(options); 列如&#xff1a; const [state, setState] useState(0); setState(state 1); 2、传⼊回调函数 setState(callBack); 例如&#xff1a; …...

JavaScript 高级 (完结)

目录 深浅拷贝 浅拷贝 深拷贝 递归实现深拷贝 js库lodash里面cloneDeep内部实现了深拷贝 JSON序列化 异常处理 throw 抛异常 try /catch 捕获异常 debugg 处理this this指向 普通函数 箭头函数 改变this call() apply() bind() call apply bind 总结 性能优化…...

【P30】JMeter 事务控制器(Transaction Controller)

文章目录 一、事务控制器&#xff08;Transaction Controller&#xff09;参数说明二、测试计划设计2.2.1、勾选 Generate parent sample2.2.1、勾选 Include duration of timer and pre-post processors in generated sample 一、事务控制器&#xff08;Transaction Controlle…...

【MySQL】MySQL的事务原理和实现?

文章目录 MySQL事务的底层实现原理一、事务的目的可靠性和并发处理 二、实现事务功能的三个技术2.1 redo log 与 undo log介绍2.1.1 redo log2.1.2undo log 2.2 mysql锁技术2.2.1 mysql锁技术 2.3 MVCC基础 三、事务的实现3.1 原子性的实现3.1.1 undo log 的生成3.1.2 根据undo…...

S7-300Smart1200的ISO on TCP通信

1、西门子PLC的通信资源 1.1 S7-1200 的PROFINET 通信口 S7-1200 CPU 本体上集成了一个 PROFINET 通信口,支持以太网和基于 TCP/IP 的通信标准。使用这个通信口可以实现 S7-1200 CPU 与编程设备的通信,与HMI触摸屏的通信,以及与其它 CPU 之间的通信。这个PROFINET 物理接口…...

Spark写入Hive报错Mkdir failed on :com.alibaba.jfs.JindoRequestPath

1. 报错内容 23/05/31 14:32:13 INFO [Driver] FsStats: cmdmkdirs, srcoss://sync-to-bi.[马赛克].aliyuncs.com/tmp/hive, dstnull, size0, parameterFsPermission:rwx-wx-wx, time-in-ms32, version3.5.0 23/05/31 14:32:13 ERROR [Driver] ApplicationMaster: User class …...

分布式id解决方法--雪花算法

uuid&#xff0c;jdk自带&#xff0c;但是数据库性能差&#xff0c;32位呀。 mysql数据库主键越短越好&#xff0c;Btree产生节点分裂&#xff0c;大大降低数据库性能&#xff0c;所以uuid不建议。 redis的自增&#xff0c;但是要配置维护redis集群&#xff0c;就为了一个id&a…...

5年经验之谈:月薪3000到30000,测试工程师的变“行”记

自我介绍下&#xff0c;我是一名转IT测试人&#xff0c;我的专业是化学&#xff0c;去化工厂实习才发现这专业的坑人之处&#xff0c;化学试剂害人不浅&#xff0c;有毒&#xff0c;易燃易爆&#xff0c;实验室经常用丙酮&#xff0c;甲醇&#xff0c;四氯化碳&#xff0c;接触…...

PMP考试都是什么题?

PMP新版大纲加入了ACP敏捷管理的内容&#xff0c;说是敏捷混合题型占到了 50%&#xff0c;但是这次318的考试&#xff0c;敏捷题占了大半&#xff0c;都说敏捷和情景快要占到80%-90%。 所以有友友说开了四个小时盲盒&#xff0c;题目读不懂&#xff0c;或者觉得4个选项都不对或…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...