算法题
- 题目
Given a string, find the length of the longest substring without repeating characters.
- Example
- Given "abcabcbb", the answer is "abc", which the length is 3.
- Given "bbbbb", the answer is "b", with the length of 1.
- Given "pwwkew", the answer is "wke", with the length of
- Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
算法题解读
- 题目大意:给定一个字符串,找出不含有重复字符的最长子串的长度
- 解读Example
- 给定"abcabcbb",没有重复字符的最长子串是"abc",那么长度就是3
- 给定"bbbbb",最长子串就是"b",长度就是1
- 给定pwwkew,最长子串就是"wke",长度为3,
- ==注意,==必须是一个子串."pwke",是子序列,而不是子串
暴力解决方案
3.1 思路
逐个检查所有的子字符串,看它是否不含有重复字符
3.2 算法
为了枚举给定字符串的所有子字符串,我们需要枚举它们开始和结束的索引,假如开始和结束的索引分别是i和j.那么我们有0<=i<=j<=n.因此,使用i从0到n-1以及j从i 1到n这2个嵌套循环.我们就可以遍历出a的所有子字符串.
3.3 复杂的分析
- 时间复杂度:
o(n3); - 空间复杂度:
o(min(n,m));
3.4 参考代码
代码语言：javascript复制//(2)无重复字符的最长子串
//求字符串长度函数
int strLength(char *p)
{
int number = 0;
while (*p) {
number ;
p ;
}
return number;
}
//判断子字符在字符串中是否唯一
int unRepeatStr(char *a,int start,int end)
{
for (int i=start;i<end;i ) {
char c = a[i];
for (int j = i 1; j < end; j ) {
if (c == a[j]) {
return 0;
}
}
}
return 1;
}
//找出不含有重复字符串最长子串的长度
int LengthLongestSubstring(char *a)
{
int n = strLength(a);
int ans = 0;
for (int i = 0; i < n; i ) {
for (int j = 0; j < n; j ) {
if (unRepeatStr(a, i, j)) {
ans = (ans > j-i)?ans:j-i;
}
}
}
return ans;
}
int main(int argc, const char * argv[]) {
//2)无重复子串的最长子串
char *s = "pwwkew";
int n = LengthLongestSubstring(s);
printf("%d",n);
return 0;
}算法面试系列文章：
BAT面试算法进阶(1)--两数之和
BAT面试算法进阶(3)- 无重复字符的最长子串(滑动窗口法)
BAT面试算法进阶(4)- 无重复字符的最长子串(滑动法优化 ASCII码法)
BAT面试算法进阶(5)- BAT面试算法进阶(5)- 最长回文子串(方法一)
BAT面试算法进阶(6)- BAT面试算法进阶(6)-最长回文子串(方法二)
BAT面试算法进阶(7)- 反转整数
BAT面试算法进阶(8)- 删除排序数组中的重复项
BAT面试算法进阶(9)- 三维形体投影面积
BAT面试算法进阶(10)- 最长的斐波那契子序列的长度(暴力法)
BAT面试算法进阶(11)- 最长的斐波那契子序列的长度(动态规划法)
BAT面试算法进阶(12)- 环形链表(哈希表法)
还不赶紧
