Log
- 【170414】完成 01 版书写(C++)
- 【170415】完成 02 版(Python)、03 版(C++)书写
- 【170416】看完参考答案,写下思路
题目
Longest Substring Without Repeating Characters
【题目类型备注】
哈希表, 字符串, 双指针
提交
01
【语言】
C++
【时间】
170414
【思路】
- 指针从头开始,一个一个查找字符,如果遇到的新的字符不在已有的记录表(使用哈希表记录,用字符
ch
映射整数i
,表示在最近的子串中ch
的坐标)中,就建立新的映射,并且继续下一轮查找 - 如果 1. 中遇到了已经在记录表中记录的字符
dupl
,那么 - 比较目前的最大子串长度与记录表长度(遇到
dupl
前的找到的这个子串的长度),将大者赋予最大子串长度 - 将指针移动到记录表中记录的
dulp
所对应的下标处·的后继坐标处·重新开始寻找最大子串 - 直到指针走到给定字符串的尾部,算法结束
【代码】
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int lmax = 0, lnow = 0;
std::unordered_map<char, int> tempchars;
for (int i=0; i<s.size(); ++i)
{
if (tempchars.find(s.at(i)) == tempchars.end())
{
tempchars[s.at(i)] = i;
lnow++;
}
else
{
if (lmax < lnow)
{
lmax = lnow;
}
i = tempchars[s.at(i)] + 1;
tempchars.clear();
tempchars[s.at(i)] = i;
lnow = 1;
}
}
if (lmax < lnow)
{
lmax = lnow;
}
return lmax;
}
};
【结果】
运行时:406 ms
报告链接:https://leetcode.com/submissions/detail/100093534/
不知道其他拥有 LeetCode 帐号的人能不能看到该报告,所以顺便附图如下:
Your runtime beats 6.06% of cpp submissions.总之好歹不算太勉强地过了……同样的逻辑用 Python 书写就超时了(在最后的 testcase 爆掉了……有一次侥幸的通过,但大多数情况下无法通过,所以最终求助于 C++)
02
【语言】
Python
【时间】
170415
【思路】
这次的思路其实是沿用第一次设计的算法的思路。那时候的思路是:
- 从头开始找子串,每找到一个新的字符就加入列表
tempchars
中 - 一旦找到旧字符,就把当前的
len(tempchars)
加入到备选的「最大子串长度」中(answers
,备选最大子串长度列表),然后从新找到的旧字符开始往后查找 - 直到查找完所有字符,算法结束
当然,那次的算法明显是有问题的:例如面对 "dvdf"
时,上述算法将算出 "dv"
(2) 和 "df"
(2),而答案显然应该是 "vdf"
(3)。于是才有了上述成功提交的版本 01。
版本 01 利用了哈希表来保存最近一次找到的无重复字符的子串,但缺陷(之一?)就在于:重复扫描了旧字符在旧子串之后(含)的所有字符。而实际上我们没有必要重复扫描那些字符——例如对于字符串 "fabedbca"
而言,(假定字符串从下标 0 开始,)当我们找到第 2 个 "b"
(下标为 5)时,我们没必要再从下标 2 开始搜索;我们只要记录子串的首、尾位置(用双指针),在遇到旧字符时更改字符串的首位置,并更改哈希表中的记录,然后继续从尾位置往后搜索即可,直到尾位置扫描到总串的尾部,算法结束。
该算法的时间复杂度应该是 O(n),不过应该还不是最优:由于在找到重复字符时要修改哈希表,而目前采取的修改哈希表的操作是:在改变首指针位置前,从首指针逐一扫描随后的字符,并移除哈希表中以这些字符为主键的键值对,直到首指针跑到重复字符前一位为止。在最坏情况下,该操作估计会导致头尾指针各扫描了一遍字符串,所以严格说应该是 O(2n)。不知道是否还有其他方法可以保证严格的 O(n)。
【代码】
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) <= 1:
return len(s)
#
lmax = 0
lnow = 0
tempchars = {}
first = 0
last = 0
while (last < len(s)):
# this loop
if s[last] not in tempchars:
tempchars[s[last]] = last
lnow += 1
else:
if lmax < lnow:
lmax = lnow
newfirst = tempchars[s[last]]+1
for ind in range(first, newfirst):
rubbish = tempchars.pop(s[ind])
first = newfirst
tempchars[s[last]] = last
lnow = last - first + 1
# next loop
last += 1
#
if lmax < lnow:
lmax = lnow
return lmax
【结果】
运行时:152 ms
报告链接:https://leetcode.com/submissions/detail/100140073/
不知道其他拥有 LeetCode 帐号的人能不能看到该报告,所以顺便附图如下:
Your runtime beats 27.29% of python submissions.我还以为这次应该是最优解了,没想到还有更快的解法啊。后面再研究看看。
03
【语言】
C++
【时间】
170415
【思路】
同提交 02
【代码】
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int lmax = 0, lnow = 0, first = 0, last = 0, newfirst;
std::unordered_map<char, int> tempchars;
for (last=0; last<s.size(); ++last)
{
if (tempchars.find(s.at(last)) == tempchars.end())
{
tempchars[s.at(last)] = last;
lnow++;
}
else
{
if (lmax < lnow)
{
lmax = lnow;
}
newfirst = tempchars[s.at(last)] + 1;
for (int i=first; i<newfirst; ++i)
{
tempchars.erase(s.at(i));
}
first = newfirst;
tempchars[s.at(last)] = last;
lnow = last - first + 1;
}
}
if (lmax < lnow)
{
lmax = lnow;
}
return lmax;
}
};
【结果】
运行时:49 ms
报告链接:https://leetcode.com/submissions/detail/100146824/
不知道其他拥有 LeetCode 帐号的人能不能看到该报告,所以顺便附图如下:
Your runtime beats 25.37% of cpp submissions.00
参考解法:
最优解太美了!问题的关键在于抓住「无重复字符的最长子串」的关键意思(看注释),就可以用极少的存储解决本题!
唯一的疑惑是:参考解法中容
int
器长度为 256,然后在下面使用时直接用字符当索引,所以应该是将这些索引数值当 ASCII 用。但为什么是 256 而非 128?
自己实现一遍最优解:
- [date-language] 。。。
网友评论