无重复字符的最长子串
2018-06-17 20:50:10来源:未知 阅读 ()
给定一个字符串,找出不含有重复字符的 最长子串 的长度。
示例:
给定 "abcabcbb"
,没有重复字符的最长子串是 "abc"
,那么长度就是3。
给定 "bbbbb"
,最长的子串就是 "b"
,长度是1。
给定 "pwwkew"
,最长子串是 "wke"
,长度是3。请注意答案必须是一个子串,"pwke"
是 子序列 而不是子串。
思路:首先其只要求返回最长子串长度,这比返回第一个最长子串应该简单把。
很容易想到,遍历字符串s,用一个中转字符串p作为储存当前没出现重复的字串,
然后,当访问到s字符串的某个字符时,利用string的find算法查找其是否在p出现,
不在p出现,即可把该字符加入p字符串;
当其p出现,就把p中从开头到该字符串出现的位置的字符全部删除,然后把该字符加入p
例如p为abc,当访问到s的第四个字符a时,就把p中a删除,把a加入该字符,
操作后p=bca,然后比较p字符串长度与res的大小,把大的值赋给res即可。
代码:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res=0;
int cur=0;
string p="";
for(unsigned int i=0;i<s.size();i++)
{
if(p.find(s[i],0)==-1)
p+=s[i];
else
{
if(p.size()>res)
res=p.size();
int pos=p.find(s[i],0);
p=p.erase(0,pos+1);
p+=s[i];
}
}
if(p.size()>res)
res=p.size();
return res;
}
};
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:OpenGL平面阴影
下一篇:C++默认成员函数
- STL之set 2020-04-28
- Z 字形变换 2020-04-14
- 最长回文子串 2020-04-13
- 翻转字符串里面的单词 2020-04-10
- 无重复字符的最长子串 2020-04-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash