开一篇文章记录在leetcode中HashTable主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结果,反思}的格式来记录,供日后复习和反思[注:有些题目的解法比较单一,就没有优化过程]。题目的顺序按照leetcode给出的题目顺序,有些题目在并不是按照题目本身序号顺序排列的,也不是严格按照难易程度来排列的。
因此,这篇文章并不具有很强的归类总结性,归类总结性知识将会在其他文章记录,本篇重点在记录解题过程中的思路,希望能对自己有所启发。
"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.class Solution {
public:
int lengthOfLongestSubstring(string s) {
string longest_substr="";
for(int index=0; index < s.size(); ++index)
{
set<char> char_set;
string tmp_substr = "";
find_longest_substr(s, index, char_set, tmp_substr);
if(tmp_substr.size() > longest_substr.size())
longest_substr = tmp_substr;
}
return longest_substr.size();
}
void find_longest_substr(string& s, int index, set<char>& char_set, string& tmp_substr)
{
for(int start = index; start < s.size(); ++start)
{
if(char_set.find(s[start])==char_set.end())
{
char_set.insert(s[start]);
tmp_substr+=s[start];
}
else break;
}
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() <= 1)
return s.size();
int length = 0, last_pos = 0;
set<char> substring;
for(int i = 0; i < s.size(); ++i)
find_longest_substr(s, i, substring, last_pos, length);
if(length < substring.size())
length = substring.size();
return length;
}
void find_longest_substr(string& s, int& index, set<char>& substring, int& last_pos, int& length)
{
if(substring.find(s[index]) == substring.end())
substring.insert(s[index]);
else
erase_duplicate_subsubstring(s, index, substring, last_pos, length);
}
void erase_duplicate_subsubstring(string& s, int& index, set<char>& substring, int& last_pos, int& length)
{
if(length < substring.size())
length = substring.size();
for(int j = last_pos; j < index; ++j)
{
substring.erase(s[j]);
if(s[j]==s[index])
{
last_pos = j+1;
break;
}
}
substring.insert(s[index]);
}
};