根本没学过这个东西,被薄纱,直接躺板板了,抑郁的时候垂死病中惊坐起,赶紧上来记一下笔记。
题目:给定一个字符串 s ,请你找出其中不含有重复字符的最长子串的长度。
评论区和官方参考答案都看了一遍,最终我选择了这个版本的答案:(才,才不是因为它简单呢)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int le = 0, ri = 1, maxlen = 0;//定义左指针,右指针,最大长度
int strlen = s.size();//定义strlen为字符串的长度
if(strlen <= 1) return strlen;//处理基准情况,当字符串长度为0或者1时直接不用比了
unordered_map<char,int> ump;//这个就是哈希表了,一般的形式是unordered_map<key,value>可以通过key的值查找对应的value,储存时是没有顺序的
ump.insert(make_pair(s[0], 0));//在已经建立好的哈希表中插入一组值,make_pair可以将两个数据合成一组数据,这里插入了s[0]作为key,插入0作为value
while(ri < strlen){//当右指针小于表长时
if( ump.count(s[ri]) != 0){//如果哈希表中有s[ri](用中文解释好复杂,这个应该看得懂吧),执行下面的语句,否则跳过
int temp_le = ump[s[ri]] + 1;//定义变量temp_le,值为哈希表中s[ri]的下一个值
for(int i = le; i < temp_le; i++){//遍历左指针直到i=temp_le
ump.erase(s[i]);
//删除哈希表中的s[i]对应的value,这已经是第三个没见过的函数了,麻了,正常用法有erase(pos,n)删除从pos开始的n个字符,
//erase(position)删除position处的字符,erase(first,last)删除从first到last之间的字符
}
le = temp_le;//把左指针赋值为temp_le(用while循环,左指针自增到temp_le后脱离循环可以吗)
}
ump.insert(make_pair(s[ri], ri));//在哈希表中插入一对值,key为s[ri],value为ri
int temp_length = ri - le + 1;//定义变量temp_length,值为每一次循环时左指针和右指针的差值
if(temp_length > maxlen) maxlen = temp_length;//每一次循环时,差值大于maxlen,将maxlen赋值为差值
ri++;//右指针自加
}
return maxlen;
}
};
代码都解释完了,捋一下解题思路啊:原作者的思路和答案掺糅在一起,太长了,我这里说简单点,看不懂这里有链接:(官方有思路视频,但我没看,比较懒):https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/227999/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
思路:首先遍历一遍字符串,把字符串的值和对应的位置都遍历进哈希表里,遍历的过程中如果遇到了相同的值,就把第一个左指针(temp_le)移到右指针前面一格的位置,然后把第一个指针(le)到第二个左指针间的元素全部删掉,在每一次循环结束的时候,比较当前左指针和右指针的差值与maxlen的大小,直到遍历结束,maxlen输出遍历其中差值最大的一次。
(虽然上一篇的博客的阅读量是大了点,但我毕竟还是个菜鸡,这种刷题笔记该记就得记)