无重复字符的最长子串
字符 重复 最长 子串
2023-09-14 08:59:24 时间
题目
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
解答
比如
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
我第一次是这样想的。
比如说abcabcbb,我要找到的就是重复的区间。
我分析为:
a,到下一个a的距离是多少。
b到下一个b的距离是多少。
我开始打算用队列。
如果我一个一个加入进去,然后查找队列,如果队列中有的话。
那么我就移除第一个,如果第一个等于现在的元素那么停止,如果不是继续移除,再加入现在的元素,然后统计数量。
当然这里是找最大的,所以每找到一个子系列的时候,我需要去统计与比较出最大的。
后来我想到用字典,但是我不知道怎么从第一个移除,然后我每次子系列的时候都会去保存从新开始的子系列到一个字符中,然后遍历。
上面两种都不好,后来我看了别人的代码。
后来就有了滑动窗口。
代码如下:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;
unordered_set<char> dic;
int left=0;
int result=0;
for(int i=0;i<s.size();i++)
{
while(dic.find(s[i])!=dic.end())
{
dic.erase(s[left]);
left++;
}
result=max(result,i-left+1);
dic.insert(s[i]);
}
return result;
}
};
后来我找到一个c语言大佬写的,我只想说句强。
int lengthOfLongestSubstring(char * s){
int start = 0, end = 0, maxlen = 0;
char map[256] = {0};
map[(int)*(s+start)] = 1;
while( *(s+end) != 0 )
{
maxlen = maxlen>(end-start+1)?maxlen:(end-start+1);
++end;
while( 0 != map[ (int)*(s+end) ] )//将要加入的新元素与map内元素冲突
{
map[ (int)*(s+start) ] = 0;
++start;
}
map[(int)*(s+end)] = 1;
}
return maxlen;
}
相关文章
- Java IO--字节-字符流转换OutputStreamWriter/InputStreamReader
- (剑指Offer)面试题55:字符流中第一个不重复的字符
- (剑指Offer)面试题35:第一个只出现一次的字符
- 算法练习之合并两个有序链表, 删除排序数组中的重复项,移除元素,实现strStr(),搜索插入位置,无重复字符的最长子串
- LeetCode: 3_Longest Substring Without Repeating Characters | 求没有重复字符的最长子串的长度 | Medium
- 如果是除去末尾特定字符或字符串:TrimEnd方法性能优于Remove方法
- 无重复字符的最长子串
- LeetCode(3):无重复字符的最长子串
- 无重复字符的最长子串
- 字符矩阵乘法可视化设计神经网络并推演神经网络的意义
- 395. 至少有 K 个重复字符的最长子串-分治法-力扣双百代码
- LeetCode 3. 无重复字符的最长子串(C语言)
- NC179 长度为 K 的重复字符子串
- 字符编码几个缩写 ACR CCS CEF CES TES
- 易飞-凭证打印异常(字符中含有空格,自己主动分行导致显示异常)
- 至少有 K 个重复字符的最长子串——分治算法,不太容易想到
- python3实现字符串的全排列的方法(无重复字符)
- 手把手带你编写一个规范的字符设备驱动
- Android 字符串的替换字符
- 【3】无重复字符的最长子串 【LeetCode】