首页 > 其他分享 >3.无重复字符的最长字串--中等

3.无重复字符的最长字串--中等

时间:2023-05-11 20:56:23浏览次数:45  
标签:子串 字符 -- 重复 字串 字符串 最长 指针

题目描述

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

示例1:

  输入: s = "abcabcbb"

  输出: 3 

  解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例2:

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

示例 3:

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

 

思路

滑动窗口:

  我们先用一个例子考虑如何在较优的时间复杂度内通过本题。我们不妨以示例一中的字符串abcabcbb为例,找出从每一个字符开始的,不包含重复字符的最长子串,那么其中最长的那个字符串即为答案。对于示例一中的字符串,我们列举出这些结果,其中括号中表示选中的字符以及最长的字符串:

  • 以(a)bcabcbb开始的最长字符串为(abc)abcbb
  • 以a(b)cabcbb开始的最长字符串为a(bca)bcbb
  • 以ab(c)abcbb开始的最长字符串为ab(cab)cbb;
  • 以abc(a)bcbb 开始的最长字符串为abc(abc)bb;
  • 以abca(b)cbb开始的最长字符串为abca(bc)bb;
  • 以abcab(c)bb开始的最长字符串为abcab(cb)b;
  • 以abcabc(b)b开始的最长字符串为abcabc(b)b;
  • 以abcabcb(b) 开始的最长字符串为abcabcb(b)。

  由上述例子我们可以看到,如果我们依次递增地枚举子串的起始位置,那么子串的结束位置也是递增的!这里的原因在于,假设我们选择字符串中的第k 个字符作为起始位置,并且得到了不包含重复字符的最长子串的结束位置为rk。那么当我们选择第k+1个字符作为起始位置时,首先从k+1到rk的字符显然是不重复的,并且由于少了原本的第k 个字符,我们可以尝试继续增大rk,直到右侧出现了重复字符为止。这样一来,我们就可以使用「滑动窗口」来解决这个问题了:

  • 我们使用两个指针表示字符串中的某个子串(或窗口)的左右边界,其中左指针代表着上文中「枚举子串的起始位置」,而右指针即为上文中的rk
  • 在每一步的操作中,我们会将左指针向右移动一格,表示 我们开始枚举下一个字符作为起始位置,然后我们可以不断地向右移动右指针,但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后,这个子串就对应着以左指针开始的,不包含重复字符的最长子串。我们记录下这个子串的长度;
  • 在枚举结束后,我们找到的最长的子串的长度即为答案。

判断重复字符:

  在上面的流程中,我们还需要使用一种数据结构来判断 是否有重复的字符,常用的数据结构为哈希集合(即 C++ 中的 std::unordered_set)。在左指针向右移动的时候,我们从哈希集合中移除一个字符,在右指针向右移动的时候,我们往哈希集合中添加一个字符。

  至此。该题完美被解决。

代码:

#include <iostream>
#include <string>
#include <unordered_set>
using namespace  std;
int func(string s){ unordered_set<char> uns; int index = 0; // 滑动窗口的右索引,起始下标为0 int max_length = 0; // 目前找到了最大不重复字串长度 int n = s.size(); for(int i=0; i<n; i++){ // i就是滑动窗口的左索引 if(i != 0){ uns.erase((s[i-1])); // 把此次遍历起始索引的前一位从当前哈希表中删除 } while(index < n){ if(uns.count(s[index]) != 0) // 遇到重复的字符就跳出循环 break; uns.insert(s[index]); index++; } max_length = max(max_length, index-i); } return max_length; }

 

标签:子串,字符,--,重复,字串,字符串,最长,指针
From: https://www.cnblogs.com/sunjuil/p/17392199.html

相关文章

  • 索引
    在宏基因组学的量化分析中,需要对测序数据进行拼接和比对等处理,以了解基因组中代表微生物种群结构的基因序列。而索引则是这一过程中十分重要的一步。索引是将特定的序列信息提取出来,存储成为容易查找和访问的形式。在宏基因组分析中,索引可以理解为对目标基因组或数据集的细分和分......
  • 5月11日打卡
    习题4-7题目描述:定义一个Dot类,包含的age、weight等属性,以及对这些属性操作的方法。实现并设计这个类。设计思路:1.定义一个类包含私有类型age、weigh、t共有类型构造函数和输出函数。流程图: 代码部分:#include<iostream>usingnamespacestd;classDot{private:i......
  • 3853 -- 三只企鹅
    题目大意:-给定一棵n个点的树,然后有m个操作,分为修改操作和查询操作。-修改操作:金企鹅向点u空投零食,其他每个点产生快递费,快递费等于u到该点的距离。-查询操作:金企鹅想询问点u至今为止产生的快递费。------------题解:对于修改操作,每次选一个点,所有点的权值加上到该点的......
  • 使用Open3D进行PCD拟合平面的Python代码示例
    使用Open3D进行PCD拟合平面的Python代码示例 importopen3daso3dimportnumpyasnp#读取点云数据pcd=o3d.io.read_point_cloud("2023042501.pcd")#创建PCD图pcd_graph=o3d.geometry.PointCloudGraph(pcd)#选择要拟合的平面plane_cent......
  • MongoDB整理
    MongoDB一、数据库(database)①什么是数据库?存储数据的仓库②为什么要有数据库?数据持久化③数据库能做什么?存储数据,可以通过网络访问④数据库的分类按照关系型分类:1、关系型数据库(MySQL、Oracle等)2、非关系型数据库(MongoDB、Redis)区别:关系型是创建表格,非关系型......
  • PyQt5入门
    要使用pyqt5需要先导入对应的包pipinstallPyQt5pipinstallPyQt5-tools然后编写我们的第一个程序fromPyQt5.QtWidgetsimport*fromPyQt5.QtGuiimport*fromPyQt5.QtCoreimport*importsysclassMyWindow(QWidget):def__init__(self):super().__i......
  • 每日总结 5.11
    <!doctypehtml><html><head><metacharset="UTF-8"><scripttype='text/javascript'>if(document.createElement("input").webkitSpeech===undefined){ale......
  • 1016. 子串能表示从 1 到 N 数字的二进制串
    题目链接:1016.子串能表示从1到N数字的二进制串方法:思维解题思路 由题目可知,字符串\(s\)的最大长度为\(1000\),那么其最多能表示的不同的二进制数不超过\(1000\)个。因此当\(n>1000\)时,直接返回\(false\);否则遍历\([1,n]\)判断是否符合题意。代码classSolu......
  • 转录组
    转录组是指一个生物体内所有基因在特定时期和特定组织或细胞类型中表达出的所有信使RNA(mRNA)的集合。换句话说,转录组是一个生物体内所有基因的转录产物总和。转录组分析一般通过测量mRNA的水平来实现,通常使用高通量测序技术如RNA-Seq,以了解哪些基因在特定条件下被激活或抑制,并......
  • Python协程asyncio
    在Python使用multiprocessing进行多线程和多进程操作 这篇文章中介绍了使用多线程的方式对一些I/O操作(文件读写、网络请求,这些操作不用等待其结束,在此期间可以做其他事情)进行加速。而本篇文章介绍的协程可以理解成“微线程”,不开辟其他线程,只在一个线程中执行,并且执行函数时......