#leetcode刷题之路3-无重复字符的最长子串
2019-02-25 16:09:26来源:博客园 阅读 ()
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
字符数组和字符串的区别,C语言字符数组和字符串区别详解
开始的想法是在对字符数组设置两个指针,初始化一个在位置0一个在位置1,ans初始化为1(非空),然后1向后找,0不动,取0到1之间的字符串,判断是否重复(这里单独写一个函数,输入字符串,输出是否重复以及重复字符的后一个的位置),不重复的话用后位置减去前位置,再和ans比较,大的话就保留。如果有重复则前位置向后移动一位,后位置在其后面一位,接着判断之间的字符串是否重复。
#include <iostream> using namespace std; //判断是否有重复 bool re_or_not(string s) { int len= s.length(); for(int i=0;i<len;i++){ for(int j=i+1;j<len;j++){ if(s[i]==s[j]){ std::cout << " true" << std::endl; return true; } } } std::cout << " false" << std::endl; return false; } int lengthOfLongestSubstring(string s) { //char* p1=(char*)s.data(); //char* p1=&s[0]; //char* p2=p1+1; int len=s.length(); //判空 if(len==0) return 0; int num=1; int begin=0; int end=begin+1; int n=0; while(s[end]!='\0'&&s[begin]!='\0'){ if(re_or_not(s.substr(begin,end-begin+1))){ begin++; end=begin+1; std::cout << " 此时begin="<<begin<< " 此时end="<<end<< std::endl; } else{ if(end-begin+1>num) num=end-begin+1; std::cout << " 此时begin="<<begin<< " 此时end="<<end<< std::endl; end++; } } return num; } int main() { string s="dewzyqprkqcmgfnrdfoflwsvkhylsfjxlhwlxne"; int n=lengthOfLongestSubstring(s); std::cout << n << std::endl; return 0; }
986 / 987 个通过测试用例
状态:超出时间限制
真的尴尬
再来:
优化,不用那个substring函数了
#include <iostream> using namespace std; //判断是否有重复 bool re_or_not(string s,int begin,int end) { int len= begin-end+1; for(int i=begin;i<len;i++){ for(int j=i+1;j<len;j++){ if(s[i]==s[j]){ std::cout << " true" << std::endl; return true; } } } std::cout << " false" << std::endl; return false; } int lengthOfLongestSubstring(string s) { //char* p1=(char*)s.data(); //char* p1=&s[0]; //char* p2=p1+1; int len=s.length(); //判空 if(len==0) return 0; int num=1; int begin=0; int end=begin+1; int n=0; while(s[end]!='\0'&&s[begin]!='\0'){ if(re_or_not(s,begin,end)){ begin++; end=begin+1; std::cout << " 此时begin="<<begin<< " 此时end="<<end<< std::endl; } else{ if(end-begin+1>num) num=end-begin+1; std::cout << " 此时begin="<<begin<< " 此时end="<<end<< std::endl; end++; } } return num; } int main() { string s="alqebriavxoo"; int n=lengthOfLongestSubstring(s); std::cout << n << std::endl; return 0; }
还是超时间;
再来:
因为所有字符只有256个,所以定义这样一个数组来判断重复就行了,同时,在遇到重复时,begin和end都后移一位
//判断是否有重复并输出位置
bool re_or_not(std::string s,int begin,int end)
{
int re[256]={0};
for(int i = begin; i<end+1; i++){
if(re[s[i]]==0){
re[s[i]]=1;
}
else return true;
}
return false;
}
int lengthOfLongestSubstring(string s) {
int len = s.length();
//判空
if (len == 0) return 0;
int num = 1;
int begin = 0;
int end = begin + 1;
int n = 0;
while (s[end] != '\0'&&s[begin] != '\0'){
if (re_or_not(s, begin, end)){
begin++;
end ++;
}
else{
if (end - begin + 1>num)
num = end - begin +1;
end++;
}
}
return num;
}
这时间。。。。。,看来要大改了
还是上面的256的思路
#include <iostream> #include <unordered_map> using namespace std; int lengthOfLongestSubstring(std::string s) { int len=s.length(); //判空 if(len==0) return 0; int re[256]={0}; int num=1; int begin=0; for(int i=0;i<len;i++) { if(re[s[i]]==0||begin>re[s[i]])//不重复,所以要尝试更新num //这里不仅要考虑对应位置的值为0,同时还要考虑这样的字符串”abbca“,按之前的方法,最后一个a被当作出现过处理了。但实际上这个a也要加入计算的,所以这里要再加上一个判断条件 //那就是如果此时begin>re[s[i]]的左边,也就是说就算重复了,但是新的a出现时,旧的a已经不再最长字符串的考虑范围内了(因为新字符串的begin位置已经在旧a的右边了) { if(num<i-begin+1) num=i-begin+1; } else//重复了,所以要把begin的位置更新到re中对应的字符对应的位置 { begin=re[s[i]]; } re[s[i]]=i+1;//+1是为了防止出错,因为i是从0开始的,后面的都要判断是否为0,所以要区别开 std::cout << " 此时i=" << i << " 此时num=" << num << std::endl; } return num; } int main() { std::string s="abbca"; int n=lengthOfLongestSubstring(s); std::cout << n << std::endl; return 0; }
执行用时: 32 ms, 在Longest Substring Without Repeating Characters的C++提交中击败了49.69% 的用户
内存消耗: 14.7 MB, 在Longest Substring Without Repeating Characters的C++提交中击败了0.93% 的用户
还可以吧
原文链接:https://www.cnblogs.com/biat/p/10432023.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- OI之路 2019-10-25
- 小白的C++之路——求质数 2019-10-25
- #leetcode刷题之路19-删除链表的倒数第N个节点 2019-03-13
- #leetcode刷题之路17-电话号码的字母组合 2019-03-13
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