LeetCode 3_Longest Substring Without Repeating Characters
LeetCode 3_Longest Substring Without Repeating Characters
题目描写叙述:
Given a string, find the length of the longest substring
without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the
length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
也就是寻找字符串中的不含反复元素的最长子串的长度。
首先非常easy想到的是暴力法:外两层循环在字符串中不断的扫描子串,内两层循环用来推断子串是否是有反复字符。
显然这样的方法时间复杂度有点高为O(n^4)。基本上不能够被接受。
在上面的方法中。推断子串是否有反复的过程中能够不用用两层循环来扫描。能够使用哈希表的方法推断。代码例如以下:
<span style="font-size:18px;">class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int i,j;
int maxLength = 0;
int hash[256];
int n = s.size();
for(i = 0; i < n; ++i)
{
memset(hash,0,sizeof(hash));
hash[s[i]] = 1;
for(j=i+1; j<n; ++j)
{
if(hash[s[j]] == 0)
hash[s[j]] = 1;
else
break;
}
if(j-i > maxLength)
maxLength = j-i;
}
return maxLength;
}
};</span>
上面的方法时间复杂度为O(n^2),以下给出LeetCode的參考答案,时间复杂的为O(n),并且代码很easy!真实不得不佩服大牛。。。
思路:使用i和j两个指针进行搜索,i代表候选的最长子串的开头。j代表候选的最长子串的结尾。
先如果i不动。右移j。直到j到达原字符串的结尾,此时j-i就构成了一个候选的最长子串。
每次都维护一max_length,就能够选出最长子串了。如果字符j已经反复出现过(如果在位置k),就须要停止右移了。
记录当前的候选子串并和max_length做比較。
以下就是一个非常好的处理,还真没想到。
在下一次搜寻中,i应该更新到k+1。这句话的意思是。用这个样例来理解。abcdef是个不反复的子串,abcdefc中(为了方便记录为abc1defc2),c1和c2反复了。那么下一次搜寻,应该跨过出现反复的地方进行,否则找出来的候选串依旧有反复字符,且长度还不如上次的搜索。所下面一次搜索。直接从c1的下一个字符d開始进行。也就是说,下一次搜寻中,i应该更新到k+1。
代码例如以下:
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int i = 0, j = 0;
int maxLength = 0;
bool exist[256] = {false};
int n = s.length();
while (j < n)
{
if (exist[s[j]])<span style="white-space:pre"> // 由于s[j] 中的是字符。能够自己主动转换为整型</span>
{
maxLength = max(maxLength, j - i);
while(s[i] != s[j])
{
exist[s[i]] = false;
i++;
}
i++;
j++;
}
else
{
<span style="white-space:pre"> </span>exist[s[j]] = true;
j++;
}
}
maxLength = max(maxLength, n-i);<span style="white-space:pre"> // 别忘了这一步</span>
return maxLength;
}
};
最新文章
- 解决ASP.NET 自定义报表部署到IIS浏览时出现ASP.NET会话已结束问题
- 小组项目alpha发布的评价
- ld链接问题解决
- centos复制到另外一台电脑连不上网
- share js 分享代码
- Qt在Windows下的三种编程环境搭建
- RequireJS入门(二)
- DataFrame
- docker 12 docker容器数据卷
- JS设计模式——观察者模式(通俗易懂)
- CentOS 6.5环境下heartbeat高可用集群的实现及工作原理详解
- 手动脱UPX压缩壳
- Oracle 12C -- 网络性能调优
- C语言实现文件复制功能(包括文本文件和二进制文件)
- Codeforce 633.C Spy Syndrome 2
- mysql-community-server安装完后不知道root密码
- scrapy docker 基本部署使用
- C++语言基础(23)-拷贝构造函数
- Winform绑定图片的三种方式
- 感知机学习算法(PLA)