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

(动态规划) 剑指 Offer 48. 最长不含重复字符的子字符串 ——【Leetcode每日一题】

❓剑指 Offer 48. 最长不含重复字符的子字符串

难度:中等

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

示例 1:

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

示例 2:

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

示例 3:

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

提示

  • s.length <= 40000

注意:本题与 3. 无重复字符的最长子串 相同。

💡思路:动态规划

定义 dp 数组,dp[i] 代表以字符 s[i] 为结尾的 “最长不重复子字符串” 的长度。

固定右边界 i ,设字符 s[i] 左边距离最近的相同字符为 s[j] ,即 s[j] = s[i]

  • i < 0 ,即 s[i] 左边无相同字符,则 dp[i] = dp[i−1] + 1
  • dp[i−1] < i - j,说明字符 s[i] 在子字符串 dp[i−1] 区间之外 ,则 dp[i] = dp[i−1] + 1
  • dp[i−1] ≥ i - j ,说明字符 s[j] 在子字符串 dp[i−1] 区间之中 ,则 dp[i] 的左边界由 s[j] 决定,即 dp[i] = i − j

所以 状态转移方程 为:
d p [ i ] = { d p [ i − 1 ] + 1 , i < 0 d p [ i − 1 ] + 1 , d p [ i − 1 ] < i − j i − j , d p [ i − 1 ] ≥ i − j dp[i]=\begin{cases}dp[i-1]+1&,i<0\\dp[i-1]+1&,dp[i-1]<i-j\\i-j&,dp[i-1]\geq i-j\end{cases} dp[i]= dp[i1]+1dp[i1]+1ij,i<0,dp[i1]<ij,dp[i1]ij

观察发现 dp[i] 只与 dp[i - 1] 有关,所以只需定义一个变量 curLen 记录上一个长度。

使用哈希表统计:

  • 遍历字符串 s 时,使用哈希表(记为 preIndexs )统计 各字符最后一次出现的索引位置
  • 遍历到 s[i] 时,可通过访问哈希表 preIndexs[s[i]] 获取最近上一个的相同字符的索引 pre

🍁代码:(C++、Java)

C++

class Solution {
public:int lengthOfLongestSubstring(string s) {int curLen = 0;int maxLen = 0;map<char, int> preIndexs;for(int i = 0; i < s.size(); i++){int pre = preIndexs.find(s[i]) == preIndexs.end() ? -1 : preIndexs[s[i]]; // 获取当前字符的索引curLen = curLen < i - pre ? curLen + 1 : i - pre; // dp[i - 1] -> dp[i]maxLen = max(maxLen, curLen);preIndexs[s[i]] = i;}return maxLen;}
};

Java

class Solution {public int lengthOfLongestSubstring(String s) {int curLen = 0;int maxLen = 0;Map<Character, Integer> preIndexs = new HashMap<>();for(int i = 0; i < s.length(); i++){int pre = preIndexs.getOrDefault(s.charAt(i), -1); // 获取当前字符的索引curLen = curLen < i - pre ? curLen + 1 : i - pre; // dp[i - 1] -> dp[i]maxLen = Math.max(maxLen, curLen);preIndexs.put(s.charAt(i), i);}return maxLen;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为字符串 s 的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1),字符的 ASCII 码范围为 0 ~ 127 ,哈希表 preIndexs 最多使用 O ( 128 ) = O ( 1 ) O(128)=O(1) O(128)=O(1) 大小的额外空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!

相关文章:

(动态规划) 剑指 Offer 48. 最长不含重复字符的子字符串 ——【Leetcode每日一题】

❓剑指 Offer 48. 最长不含重复字符的子字符串 难度&#xff1a;中等 请从字符串中找出一个最长的不包含重复字符的子字符串&#xff0c;计算该最长子字符串的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”&#xff0c;所以其长度为…...

【文心一言】如何申请获得体验资格,并简单使用它的强大功能

目录 一、文心一言1.1、它能做什么1.2、技术特点1.3、申请方法 二、功能体验2.1、文心一言2.2、写冒泡排序代码 测试代码2.3、画一个爱心2.4、画一个星空 三、申请和通过3.1、申请时间3.2、通过时间 文心一言&#xff0c;国内首个大型人工智能对话模型&#xff0c;发布已经快一…...

1. 卷积原理

① 卷积核不停的在原图上进行滑动&#xff0c;对应元素相乘再相加。 ② 下图为每次滑动移动1格&#xff0c;然后再利用原图与卷积核上的数值进行计算得到缩略图矩阵的数据&#xff0c;如下图右所示。 import torch import torch.nn.functional as Finput torch.tensor([[1, 2…...

pandas读取excel,再写入excel

需求是这样的&#xff0c;从一个表读取数据&#xff0c;然后每次执行创建一个新表将值写入 读取这个表 写入到这个表 分别对应的是e、h列数据&#xff0c;代码如下&#xff1a; import pandas as pd import openpyxl import datetime dfpd.read_excel(rC:\Users\admin\Deskt…...

【React学习】—React中的事件绑定(八)

【React学习】—React中的事件绑定&#xff08;八&#xff09; 一、原生JS <body><button id"btn1">按钮1</button><button id"btn2">按钮2</button><button onclick"demo()">按钮3</button><scr…...

记录在ubuntu 18.04系统上安装虚拟机的过程

- 下载ubuntu镜像 ubuntu镜像下载地址 我下载的是desktop桌面版&#xff0c;比较好操作。 - 烧录 我用的Mac&#xff0c;使用的是balenaEtcher软件进行磁盘烧录。 balenaEtcher下载地址 如果出现磁盘损坏或者无法再次使用&#xff0c;参考这里解决&#xff1a;进入 - 安…...

C/C++ 个人笔记

仅供个人复习&#xff0c; C语言IO占位符表 %d十进制整数(int)%ldlong%lldlong long%uunsigned int%o八进制整型%x十六进制整数/字符串地址%c单个字符%s字符串%ffloat&#xff0c;默认保留6位%lfdouble%e科学计数法%g根据大小自动选取f或e格式&#xff0c;去掉无效0 转义符表…...

Stm32的时钟系统以及使用SysTick滴答定时器实现延时

前言 STM32的时钟系统由多个时钟源和时钟树组成时钟源包括主时钟源&#xff08;HSE&#xff09;、内部高速时钟源&#xff08;HSI&#xff09;、内部低速时钟源&#xff08;LSI&#xff09;和外部低速时钟源&#xff08;LSE&#xff09;。时钟树由多个时钟分频器和时钟门控器组…...

重生c++系列之类与对象(中篇)

好的继上期&#xff0c;我们今天带来c类与对象系列的继续学习。 类的6个默认成员函数 如果一个类中什么成员都没有&#xff0c;简称为空类。 空类中真的什么都没有吗&#xff1f;并不是&#xff0c;任何类在什么都不写时&#xff0c;编译器会自动生成以下6个默认成员 函数。 …...

Java中synchronized基本介绍和细节讨论。使用Synchronized来解决售票超卖问题

基本介绍 线程同步机制:在多线程编程下&#xff0c;一些敏感数据不允许被多个现在在同一时刻访问&#xff0c;此时就使用同步访问机制&#xff0c;保证数据在任何同一时刻最多只有一个进程访问&#xff0c;以保证数据的完整性。&#xff08;即&#xff1a;当有一个线程在对内存…...

java内存分区

按照垃圾收集&#xff0c;将 Java 堆划分为**新生代 &#xff08;Young Generation&#xff09;和老年代&#xff08;Old Generation&#xff09;**两个区域&#xff0c; 新生代存放存活时间短的对象&#xff0c;而每次回收后存活的少量对象&#xff0c;将会逐步晋升到老年代中…...

【JavaScript】V8 引擎解析 JavaScript 的过程

V8 是由 Google 开发的 JavaScript 引擎&#xff0c;用于执行 JavaScript 代码。它被广泛应用于 Chrome 浏览器和 Node.js 等环境。V8 的解析和执行过程是一个复杂的流程&#xff0c;以下是其大致步骤&#xff1a; 词法分析&#xff08;Lexical Analysis&#xff09;&#xff1…...

Qt:界面实时响应鼠标拖动绘制

采用双缓冲实现界面实时响应鼠标的拖动绘制。 思想如下&#xff1a;首先需要两张画布pix和tempPix&#xff0c;他们都是QPixmap实例&#xff1b;pix用来保存初始界面或上一阶段以完成的绘制&#xff1b;tempPix用来作为鼠标拖动时的实时界面绘制&#xff1b;当鼠标左键按下后拖…...

Docker拉取RocketMQ及可视化界面

本文介绍Docker拉取RocketMQ及可视化界面操作步骤 Linux下安装Docker请参考&#xff1a;Linux安装Docker 文章目录 安装namesrv创建挂载目录授权相关权限拉取镜像运行容器查看运行情况 安装Broker创建挂载目录及配置文件目录授权相关权限创建配置文件运行容器查看运行情况 安装…...

花5分钟判断,你的Jmeter技能是大佬还是小白!

jmeter 这个工具既可以做接口的功能测试&#xff0c;也可以做自动化测试&#xff0c;还可以做性能测试&#xff0c;其主要用途就是用于性能测试。但是&#xff0c;有些公司和个人&#xff0c;就想用 jmeter 来做接口自动化测试。 你有没有想过呢&#xff1f; 下面我就给大家讲…...

macOS - 安装 Python 及地址

文章目录 Python 官方安装包Pip3Applications - PythonMiniconda多个python环境有多种方式安装 python,比如 Python 官方包、anaconda、miniconda、brew 等 这里记录使用 Python 官方包进行安装,和 miniconda 安装方式,以及安装后 各执行文件、安装包的地址。 明确这些地址后…...

前端组件库造轮子——Tree组件开发教程

前端组件库造轮子——Tree组件开发教程 前言 本系列旨在记录前端组件库开发经验&#xff0c;我们的组件库项目目前已在Github开源&#xff0c;下面是项目的部分组件。文章会详细介绍一些造组件库轮子的技巧并且最后会给出完整的演示demo。 文章旨在总结经验&#xff0c;开源分…...

java打war包、jar包方式,java运行war包、jar包方式

Java spring boot部署到生产环境有两种常见方式 1打jar包&#xff0c;使用了内置的tomcat服务器&#xff0c;流程简单 2打war包&#xff0c;可以放标准tomcat服务器中 jar包 1pom.xml新增 <build><plugins><plugin><groupId>org.springframework.b…...

“超级AI助手:全新提升!中文NLP训练框架,快速上手,海量训练数据,ChatGLM-v2、中文Bloom、Dolly_v2_3b助您实现更智能的应用!”

“超级AI助手&#xff1a;全新提升&#xff01;中文NLP训练框架&#xff0c;快速上手&#xff0c;海量训练数据&#xff0c;ChatGLM-v2、中文Bloom、Dolly_v2_3b助您实现更智能的应用&#xff01;” 1.简介 目标&#xff1a;基于pytorch、transformers做中文领域的nlp开箱即用…...

空时自适应处理用于机载雷达——机载阵列雷达信号环境(Matla代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...