算功@LeetCode:Longest Substring Wi
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] 。。。
