最长不含重复字符的子字符串
今天处理一道算法题目,《剑指Offer》第48题,力扣中等题。
这道题也是面试的高频题!
题目描述
请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
示例1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
解题思路
方法1:动态规划
用f(i)表示以第i个字符为结尾的不含重复字符的最长长度,推断出三种情况:
1. 如果当前字符在之前都没出现过,那么f(i) = f(i-1) + 1;
2. 如果当前字符在之前出现过,并且两者的距离差d<=f(i-1),那么当前的最长长度即为d;
3. 如果当前字符在之前出现过,并且两者的距离差d>f(i-1),那么说明之前的这个元素已经在滑动窗口之外,我们仍然可以用f(i) = f(i-1)+1;
/*** 动态规划*设f(i)表示以第i个字符为结尾的不含重复字符的最长长度,可以得到状态转换方程:f(i)={f(i-1)+1; 第i个字符之前没出现过d; 之前出现过,但和之前出现的字符距离差d小于等于f(i-1),即d<f(i-1)f(i-1)+1; 之前出现过,且d>f(i-1)}// 以arabcacfr为例,在计算最后一个r,即f(8)的时候,出现d>f(7)的情况,可以把r追加到f(7)的后面这个思路是最通俗易懂的,但代码和时间上不是最优的* @param s* @return*/public int lengthOfLongestSubstring(String s) {if(s == null || s.length() == 0)return 0;int n = s.length();if(n == 1)return 1;int[] mem = new int[n];Map<Character, Integer> map = new HashMap<>();//初始化mem[0] = 1;map.put(s.charAt(0), 0);for(int i = 1; i < n; ++i) {char c = s.charAt(i);//之前没有出现过,则f(i) = f(i-1)+1if(!map.containsKey(c)) {map.put(c, i);mem[i] = mem[i-1] + 1;}else{//之前出现过,记录差值d,并比较差值和f(i-1)的大小int before = map.get(c);int d = i - before;if(d <= mem[i-1]) {mem[i] = d;}else {mem[i] = mem[i-1]+1;}//最后记得更新这个值map.put(c, i);}}int maxLen = 0;for(int i = 0; i < n; ++i) {maxLen = Math.max(maxLen, mem[i]);}return maxLen;}
总体来说,这种方法时间不是最优,但思路很清晰。
方法2:滑动窗口
用i,j两个指针来控制窗口的左右边界,然后用i每次递增一隔,计算以i为起点的最长无重复子串,只是这里的j不用从i的位置开始,这种做法也是力扣官方的做法,个人觉得不太好,时间复杂度不高。
/*** 滑动窗口(或者就左右指针)* @param s* @return*/public int lengthOfLongestSubstring2(String s) {//abcabcbbif(s == null || s.length() == 0)return 0;int n = s.length();if(n == 1)return 1;Set<Character> set = new HashSet<>();int i = 0;set.add(s.charAt(0));int j = 1;int maxLen = 0;while(i < n) {while(j < n) {char c = s.charAt(j);if(set.contains(c)){break;}set.add(c);j++;}maxLen = Math.max(maxLen, j-i);set.remove(s.charAt(i));i++;}return maxLen;}
方法3:左右指针
该方法是极力推荐的做法:用j遍历字符串,每次判断以j为结尾的最长无重复字符的子串长度,如果出现了重复字符,则更新左边界。只是这里,需要额外注意,更新左边界的时候,需要取上一个左边界和当前元素对应的之前值的最大值。
/*** 左右指针,j表示以第j个字符为结尾的不含重复字符的最长子串* 这里必须要注意一种情况,就是左边界需要取原左边界和当前元素在map中保存的值的最大值* 防止类似于abba这种字符串* @param s* @return*/public int lengthOfLongestSubstring3(String s) {if (s == null || s.length() == 0)return 0;int n = s.length();int i = -1;int maxLen = 0;Map<Character, Integer> map = new HashMap<>();for (int 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);maxLen = Math.max(maxLen, j - i);}return maxLen;}
相关文章:
最长不含重复字符的子字符串
今天处理一道算法题目,《剑指Offer》第48题,力扣中等题。 这道题也是面试的高频题! 题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例1: 输入: "abcabcbb" …...
git中git push origin master推送远程操作失败,报错解决方案
报错图片如下所示: 解决方案: 使用下面代码进行本地与远程仓库的链接: git remote add origin http://xxxxx///xxx(https://gitee.com/peach-fog/shopping-cart-car-warehouse.git)链接完成之后就会输出:fatal: remote origin already exists. 链接完成之后就需要使用git br…...
服务器部署流程与经验记录
服务器部署流程1.项目部署1.1 重置实例密码1.2 配置安全组规则1.3 远程连接服务器1.4 安装所需软件1.5 安装Tomcat1.6 配置宝塔安全组1.7 导入数据库和项目2. 域名注册3. 网站备案1.项目部署 1.1 重置实例密码 1.2 配置安全组规则 1.3 远程连接服务器 使用VNC远程连接&#…...
超火的情感视频短视频账号,赚钱的路子有多野?
目录 一、情感类视频内容模式 1、线上情感导师型 2、用动画传达人生哲理 3、网抑云式的野生“文案馆” 4、星座式情感账号 二、情感号变现方式 1、首先是可以接广告 2、收徒做情感号培训,知识付费 3、导流粉丝到公众号 4、通过卖号来变现 6、导流微信变现…...
Linux系列 linux 常用命令(笔记)
作者简介:一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭:低头赶路,敬事如仪 个人主页:网络豆的主页 目录 前言 一.linux 常用命令(目录文和件基本操作) 1.命令的分类…...
Cosmos 基础教程(二)-- Run a Node, API, and CLI
有很多不同的方法来运行Cosmos区块链的节点。您将探索如何使用simapp 进行此操作。 1、编译simapp Cosmos SDK存储库包含一个名为 simapp 的文件夹。在这个文件夹中,您可以找到运行Cosmos SDK模拟版本的代码,这样您就可以在不实际与链交互的情况下测试…...
C# 读写xml文件总结 [详细]
C# 读写xml文件总结C#写入xml文件1、XmlDocument2、DataSet对象里的值来生成XML文件3、利用XmlSerializer来将类的属性值转换为XML文件的元素值。示例:写入xml1、创建xml文档2 、增加节点3 、修改节点:4 、删除节点c#读取xml文件C#写入xml文件 1、XmlDo…...
【Java基础】IO流
IO流 最后一定要关闭流,防止资源泄露 字节流 一次读取1字节,8比特 FileInputStream import org.junit.jupiter.api.Test;import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException;public class CopyBytes {pub…...
Boolean,Array,Object数据类型(回顾)
Boolean数据类型范围Boolean(value)Object数据类型特点键值对数组特点类数组特点 Boolean数据类型范围 true,false 链接 Boolean(value) 定义:其他类型转布尔类型 六大假值:false,undefined,null,NaN,0…...
Python常见的数据类型
♥️作者:小刘在C站 ♥️个人主页:小刘主页 ♥️每天分享云计算网络运维课堂笔记,努力不一定有收获,但一定会有收获加油!一起努力,共赴美好人生! ♥️夕阳下,是最美的绽放࿰…...
欠缺知识点罗列
UML五种关系的特点 依赖,关联,组合,聚合,泛化。认识UML类关系——依赖、关联、聚合、组合、泛化 - 腾讯云开发者社区-腾讯云 数据结构- 生成树的定义。 每周学点大数据 | No.17最小生成树 - 腾讯云开发者社区-腾讯云 有向图。 …...
基于springboot+vue的校园社团管理系统(前后端分离)
博主主页:猫头鹰源码 博主简介:Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容:毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目介绍…...
你了解互联网APP推荐的背后逻辑么(下)?
上篇重点介绍了互联网APP在搜索交互场景下的通用逻辑,让大众对每天离不开的搜索进行了一个普遍介绍。这一篇,我们来聊聊抖音、头条等APP划一划这个动作背后,是怎么做推荐的。推荐的背后,离不开每个用户的数据,而且这个…...
总是跳转到国内版(cn.bing.com)?New Bing使用全攻略
你是否想要使用强大的(被削后大嘘)New Bing? 你是否已经获得了New Bing的使用资格? 你是否在访问www.bing.com/new时提示页面不存在? 你是否在访问www.bing.com时总是重定向到cn.bing.com而使用不了New Bing? New Bi…...
神经网络的基本骨架—nn.Module使用
一、pytorch官网中torch.nn的相关简介可以看到torch.nn中有许多模块:二、Containers模块1、MODULE(CLASS : torch.nn.Module)import torch.nn as nn import torch.nn.functional as Fclass Model(nn.Module):#nn.Module---所有神经网络模块的…...
面试官:你是怎样进行react组件代码复用的
mixin Mixin 设计模式 Mixin(混入)是一种通过扩展收集功能的方式,它本质上是将一个对象的属性拷贝到另一个对象上面去,可以拷贝多个属性到一个对象上,为了解决代码复用问题。 常用的方法:JQuery 的 exte…...
arxiv2017 | 用于分子神经网络建模的数据增强 SMILES Enumeration
论文标题:SMILES Enumeration as Data Augmentation for Neural Network Modeling of Molecules论文地址:https://arxiv.org/abs/1703.07076代码地址:https://github.com/Ebjerrum/SMILES-enumeration一、摘要摘要中明显提出:先指…...
倒计时2天!TO B人的传统节日,2023年22客户节(22DAY)
去年,2022.02.22,正月二十二星期二,在这个最多2的一天,成功举办了“首届22客户节(22DAY)”,一群To B互联网人相约杭州见证; 癸卯兔年,2023.02.22,让我们再度…...
java版工程管理系统Spring Cloud+Spring Boot+Mybatis实现工程管理系统源码
java版工程管理系统Spring CloudSpring BootMybatis实现工程管理系统 工程项目各模块及其功能点清单 一、系统管理 1、数据字典:实现对数据字典标签的增删改查操作 2、编码管理:实现对系统编码的增删改查操作 3、用户管理:管理和…...
数据结构刷题(六):142环形链表II、242有效的字母异位词、383赎金信、349两个数组的交集
1.环形链表II题目链接思路:设置快慢双指针注意:(1)是否有环(快慢双指针是否能碰面也就是相等)(2)环形入口的判断。从头结点出发一个指针,从相遇节点 也出发一个指针&…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
