【题目】
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.
【分析】
从左到右扫描,当遇到重复字母时,以上一个重复字母的index+1,作为新的搜索起始位置,直到最后一个字母。
【代码】
/*********************************
* 日期:2015-01-20
* 作者:SJF0115
* 题目: 3.Longest Substring Without Repeating Characters
* 网址:https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/
* 结果:AC
* 来源:LeetCode
* 时间复杂度:O(n)
* 空间复杂度:O(1)
* 博客:
**********************************/
#include <iostream>
#include <cstring>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.length();
if(len <= 1){
return len;
}//if
bool visited[256];
// 初始化
memset(visited,false,sizeof(visited));
// 计算
int max = 0,cur = 0,start = 0;
for(int i = 0;i < len;){
// 没有元素和该元素重复
if(!visited[s[i]]){
visited[s[i]] = true;
++cur;
++i;
}//if
else{
// 更新最大长度
if(cur >= max){
max = cur;
}//if
cur = 0;
memset(visited,false,sizeof(visited));
int index = 0;
// 寻找之前重复元素的下一个元素的下标
for(int j = start;j < i;++j){
if(s[i] == s[j]){
index = j+1;
break;
}//if
}//for
start = index;
i = index;
}
}//for
if(cur > max){
max = cur;
}//if
return max;
}
};
int main(){
Solution solution;
string str("abbacdafg");
int result = solution.lengthOfLongestSubstring(str);
// 输出
cout<<result<<endl;
return 0;
}
【代码二】
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.length();
if(len <= 1){
return len;
}//if
// 记录上次出现的位置
int last[256];
// 初始化
memset(last,-1,sizeof(last));
// 计算
int max = 0,cur = 0,start = 0;
for(int i = 0;i < len;++i){
// 有元素和该元素重复
if(last[s[i]] >= 0){
if(cur > max){
max =cur;
}//if
// 当遇到重复字母时,以上一个重复字母的index+1,
// 作为新的搜索起始位置
i = last[s[i]] + 1;
cur = 0;
memset(last,-1,sizeof(last));
}//if
++cur;
last[s[i]] = i;
}//for
if(cur > max){
max = cur;
}//if
return max;
}
};
【分析三】
对上一个思路继续进行优化。
在上一个思路中当遇到重复字母时,以上一个重复字母的index+1,作为新的搜索起始位置。上一个重复字母的下一个字母到当前字母可以不用重复遍历。
在本思路中搜索起点不是上一个重复字母的index+1而是当前字母。
通过记录上一个LonestSubstring Without Repeating Characters的起点,来计算出在当前字母时的长度。
【代码三】
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.length();
if(len <= 1){
return len;
}//if
// 记录上次出现的位置
int last[256];
// 初始化
memset(last,-1,sizeof(last));
// 计算
int max = 0,cur = 0,start = 0;
for(int i = 0;i < len;++i){
int pos = (int)s[i];
// 有元素和该元素重复
if(last[pos] >= start){// not last[pos] >= 0
// 更新长度
cur = cur - (last[pos] - start);
// 更新起点
start = last[pos] + 1;
}//if
else{
++cur;
}
// 更新字符位置
last[pos] = i;
if(cur > max){
max =cur;
}//if
}//for
return max;
}
};
分享到:
相关推荐
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17...
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
LeetCode-3.Longest_Substring_Without_Repeating_Characters 给定一个字符串,找出没有重复字符的最长子字符串的长度。 示例 1: 输入:“abcabcbb” 输出:3 解释:答案是“abc”,长度为 3。 解决方案 Python3:...
lru缓存leetcode leetcode 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. ...
3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7.Reverse Integer 8.String to Integer (atoi) 9....
leetcode Python 001 leetcode的算法问题 这是我的解决方案,用 cpp 、 java 和 python 编写 #LeetCode 解决的问题: 001. Two Sum 002. Add Two Numbers 003. Longest Substring Without Repeating Characters4. ...
3.Longest Substring Without Repeating Characters 5.Longest Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted Array 53.Maximum Subarray 70.Climbing Stairs 121.Best Time to Buy...
答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...
Leetcode.3 Longest Substring Without Repeating Characters Leetcode.76 Minimum Window Substring Leetcode.438 Find All Anagrams in a String Pattern: two points 双指针是这样的模式:两个指针朝着左右方向...
3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring 6.ZigZag Conversion 7.Reverse Integer 8.String To Integer 9.Palindrome Number 10.String ...
leetcode 跳跃 leetcode 动态规划,背包问题 01背包问题:416. Partition Equal Subset Sum 最长回文:5. Longest Palindromic Substring - 字数组余数:523. Continuous Subarray Sum - 无重复字符的最长子串:3. ...
leetcode 跳跃 LeetCode Solved by Python easy/middle/hard:15/36/5 1. Two Sum 两数之和 2. Add Two Numbers 两数相加 3. Longest Substring Without Repeating Characters 无重复字符的最长子串 4. Median of ...
3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 7.Reverse Integer 8.String to Integer (atoi) 9.Palindrome Number 11.Container With Most Water 14.Longest Common Prefix ...
#3:Longest Substring Without Repeating Characters #5:Longest Palindromic Substring 链表 #2:Add Two Numbers 分而治之 #53:Maximum Subarray 队列/集 #3:Longest Substring Without Repeating Characters 优先...
3. Longest Substring Without Repeating Characters 最长没有重复字符的子序列 记录各字符最近一次出现的位置 4. Median of Two Sorted Arrays 求两有序数列的中位数,可泛化为求两有序数列的第k位数,二分法 5. ...
leetcode 答案 LeetCode My LeetCode solution List 4. Longest Substring Without Repeating Characters: Using the dict[] to record the last position of each letter. 5. Longest Palindromic Substring: ...
3.Longest Substring Without Repeating Characters 滑动窗口。其实就是一个队列,比如例中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,滑动这个...
leetcode Python 001 力码 ├── Algorithms │ ├── cpp │ │ ├── 001 - Two Sum.cpp │ │ ├── 002 - Add Two Numbers.cpp │ │ ├── 003 - Longest Substring Without Repeating ...
leetcode 2 sum c Leetcode 记录我的Leetcode之旅 题号 难度 知识点 完成情况 1. Two Sum Easy 搜索 :check_mark_button: 2. Add Two Numbers Medium 链表 :check_mark_button: 3. Longest Substring Without ...