题目:
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 the length of 1.
Given "pwwkew"
, the answer is "wke"
, with the length of 3. Note that the answer must be a substring, "pwke"
is a subsequence and not a substring.
对于这个题目我的理解就是对一个string求最长的子串(里面的字母不能重复)。
这道题目是一道字符串的题目,首先就是应该复习一下c++中字符串string类的用法,下面是一个博客中的示范使用c++的代码,我抄录了下来,https://www.cnblogs.com/engraver-lxw/p/7581540.html为作者网页:
#include<iostream>
#include<string>
using namespace std; int main()
{
string str1 = "hello";
string* str2 = new string("hello");
string str3 = "world"; //获取字符串长度
int length = str1.length();
cout << "调用str.length()函数获取字符串长度:" << length << endl;
cout << endl; //字符串连接
string str4 = str1 + str3;
cout << "字符串连接结果:" << str4 << endl;
cout << endl; //字符串比较
if (str1 < str3)
cout << "字符串比较:" << "str1<str2" << endl;
cout << endl; //获取字符串的第一个字符
string::const_iterator it = str1.begin();
cout << *it << endl;
cout << endl; //获取字符串的最后一个字符
it = str1.end();//end是指向最后一个字符后面的元素,而且不能输出,所以cout << *it << endl;这样输出会报错
it--;
cout << *it << endl;
cout << endl; //倒置串
reverse(str1.begin(), str1.end());
cout << "倒置串:" << str1 << endl;
cout << endl; //字符串转字符数组
//不推荐的用法,但是需要了解
string a = "abc123";
const char *b;//这里必须为const char *,不能用char *,不然下一句会报错
b = a.c_str();
cout << "a:" << a << endl;
cout << "b:" << b << endl;
a = "asd456";
cout << "a:" << a << endl;
cout << "b:" << b << endl;
//推荐用法
string c = "abc123";
char *d = new char[];
strcpy(d, c.c_str());//因为这里没有直接赋值,所以指针类型可以不用const char *
cout << "c:" << c << endl;
cout << "d:" << d << endl;
c = "asd456";
cout << "c:" << c << endl;
cout << "d:" << d << endl;
cout << endl; //查找串
//find-从指定位置起向后查找,直到串尾
string st1("babbabab");
cout << st1.find('a') << endl;//1,默认从位置0(即第1个字符)开始查找
cout << st1.find('a', ) << endl;//4 在st1中,从位置2(b,包括位置2)开始,查找a,返回首次匹配的位置
cout << (st1.find('c', ) == -) << endl;//1
cout << (st1.find('c', ) == ) << endl;//1 两句均输出1,原因是计算机中-1和4294967295都表示为32个1(二进制)
string st2("aabcbcabcbabcc");
str1 = "abc";
cout << st2.find(str1, ) << endl;//6,从st2的位置2(b)开始匹配,返回第一次成功匹配时匹配的串(abc)的首字符在st2中的位置,失败返回-1
cout << st2.find("abcdefg", , ) << endl;//6 取abcdefg得前3个字符(abc)参与匹配,相当于st2.find("abc", 2) //rfind-从指定位置起向前查找,直到串首
cout << st1.rfind('a', ) << endl;//6 //find_first_of-在源串中从位置pos起往后查找,只要在源串中遇到一个字符,该字符与目标串中任意一个字符相同,就停止查找,返回该字符在源串中的位置;若匹配失败,返回-1
string str6("bcgjhikl");
string str7("kghlj");
cout << str6.find_first_of(str7, ) << endl;//2,从str1的第0个字符b开始找,g与str2中的g匹配,停止查找,返回g在str1中的位置2 //find_last_of-与find_first_of函数相似,只不过查找顺序是从指定位置向前
string str("abcdecg");
cout << str.find_last_of("hjlywkcipn", ) << endl;//5,从str的位置6(g)开始向前找,g不匹配,再找c,c匹配,停止查找,返回c在str中的位置5 //find_first_not_of-在源串中从位置pos开始往后查找,只要在源串遇到一个字符,与目标串中的任意字符都不相同,就停止查找,返回该字符在源串中的位置;若遍历完整个源串,都找不到满足条件的字符,则返回-1
cout << str.find_first_not_of("kiajbvehfgmlc", ) << endl;//3 从源串str的位置0(a)开始查找,目标串中有a,匹配,..,找d,目标串中没有d(不匹配),停止查找,返回d在str中的位置3 //find_last_not_of-与find_first_not_of相似,只不过查找顺序是从指定位置向前
cout << str.find_last_not_of("kiajbvehfgmlc", ) << endl;// system("pause");
return ; }
用这个很自然的思路,当然也很自然的gg了,其实样例倒是可以过,不过当时的想法只是粗略的
把他们都当作是一定是小写字母了,没有仔细的思考。
先把这份错误的代码贴出来:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int used[]={};
string::iterator it=s.begin();
string::iterator itForRequest=s.end();
itForRequest--;
int ans=;
for(;it<=itForRequest;it++)
{
string::iterator temp=it;
int sum=;
for(int i=;i<=;i++)
{
used[i]=;
}
while(true)
{
if(temp>itForRequest) break;
if(used[*temp-'a']==)
{
used[*temp-'a']++;
temp++;
sum++;
}
else
{
if(sum>ans) ans=sum;
break;
}
}
}
return ans;
}
};
当然后来发现这个方法也没毛病,完全可行,毕竟ASII码表也就不到一百个数字,我把每个数字
搞一个数组元素就完全没问题了,当然也发现了前面代码的一点小bug主要就是在之前代码的20
行的判断内部应该加上sum>ans的判断,否则如果只有单个字母就会导致边界条件的错误,现在
把正确代码贴上来:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int used[]={};
string::iterator it=s.begin();
string::iterator itForRequest=s.end();
itForRequest--;
int ans=;
for(;it<=itForRequest;it++)
{
string::iterator temp=it;
int sum=;
for(int i=;i<=;i++)
{
used[i]=;
}
while(true)
{
if(temp>itForRequest) break;
if(used[*temp]==)
{
used[*temp]++;
temp++;
sum++;
if(sum>ans) ans=sum;
}
else
{
if(sum>ans) ans=sum;
break;
}
}
}
return ans;
}
};