h*****g
发帖数: 944 | 1 比如，“abcabcbb”最大的就是“abc”长度3
“bbbbb”最大就是“b”长度1
有O(N)的algo吗？ |
f***g
发帖数: 214 | |
h*****g
发帖数: 944 | 3 能展开说说或者给个链接吗？
【在 f***g 的大作中提到】
: 前后两个指针
: 类似那个最小覆盖算法
|
k******r
发帖数: 2300 | 4 用hash table，比方定义 int hTable[256], 然后初始化， . 然后再读字符串， 第一
个字符a，那么 if(
int hTable[256];
hTable['a'] = 0, ..., hTable['z']=0;
char c;
int len = 0;
int maxLen = 0;
while(c=read(str))
{
if(hTable[c]==0)
{
hTable[c]++;
len++;
}
else
{
if(maxLen
{
maxLen = len;
}
len=0;
hTable['a'] = 0, ..., hTable['z']=0;
hTable[c]++;
len++;
}
}
if(maxLen
{
maxLen = len;
len=0;
}
没作调试，可能有BUG，时间度大概是O(N)，就是个大概的意思，将就看吧。
【在 h*****g 的大作中提到】
: 比如，“abcabcbb”最大的就是“abc”长度3
: “bbbbb”最大就是“b”长度1
: 有O(N)的algo吗？
|
f***g
发帖数: 214 | 5 你的意思是，如果碰到了重复的字符，前面当前的结果全部舍弃不要？
有重叠怎么办？
两个指针：
前面的尽量往前scan，直到查表发现重复。
如果发现重复
后面的往前走直到去除掉那个要重复的字符。
每次前面的走一步都要update max
【在 k******r 的大作中提到】
: 用hash table，比方定义 int hTable[256], 然后初始化， . 然后再读字符串， 第一
: 个字符a，那么 if(
: int hTable[256];
: hTable['a'] = 0, ..., hTable['z']=0;
: char c;
: int len = 0;
: int maxLen = 0;
: while(c=read(str))
: {
: if(hTable[c]==0)
|
t****o
发帖数: 31 | 6 L(i)表示以第i个字符结尾的无重复字符子串的长度
1）若第i个字符出现过
d表示最近一次出现重复字符的位置，hashmap(第i个字符)表示上一次第i个字符出现的
位置
if d>hashmap(第i个字符) L(i)=L(d)+i-d
else L(i)=i-hashmap(第i个字符)
更新 d=i,hashmap(第i个字符)=i
2)否则L(i)=L(i-1)+1
返回最大的L(i) |
l*******e
发帖数: 309 | 7 #include
#include |
l*********s
发帖数: 5409 | 8 agelee
【在 f***g 的大作中提到】
: 前后两个指针
: 类似那个最小覆盖算法
|
k******r
发帖数: 2300 | 9 碰到了重复的字符， 保留当前不重复字符串的最大长度，然后回到初始状态，重新计
算。并不是“前面当前的结果全部舍弃不要”。 你的两个指针的做法跟我的相似。如
果我没有理解错，你的“每次前面的走一步”，不仅要update max，还要update 表。
【在 f***g 的大作中提到】
: 你的意思是，如果碰到了重复的字符，前面当前的结果全部舍弃不要？
: 有重叠怎么办？
: 两个指针：
: 前面的尽量往前scan，直到查表发现重复。
: 如果发现重复
: 后面的往前走直到去除掉那个要重复的字符。
: 每次前面的走一步都要update max
|
j***y
发帖数: 2074 | 10
我也感觉用map是个不错的选择，不过下面的代码有些不明白：
－－－
} else {
if (curr > longest)
longest = curr;
curr = i - m[c];
index = m[c]+1;
m[c] = i;
－－－
可以加点注释或者说明吗？谢谢。
【在 l*******e 的大作中提到】
: #include
: #include
|
j***y
发帖数: 2074 | 11
老大，能不能给段代码的例子？手生得紧，光看idea还是无法写出代码。
【在 f***g 的大作中提到】
: 你的意思是，如果碰到了重复的字符，前面当前的结果全部舍弃不要？
: 有重叠怎么办？
: 两个指针：
: 前面的尽量往前scan，直到查表发现重复。
: 如果发现重复
: 后面的往前走直到去除掉那个要重复的字符。
: 每次前面的走一步都要update max
|
g***s
发帖数: 3811 | 12 这题跟最大直方图是一个思路。
同理，用类似“发个湾区P公司的第一轮phone interview”第二题的方法也可解。
【在 k******r 的大作中提到】
: 碰到了重复的字符， 保留当前不重复字符串的最大长度，然后回到初始状态，重新计
: 算。并不是“前面当前的结果全部舍弃不要”。 你的两个指针的做法跟我的相似。如
: 果我没有理解错，你的“每次前面的走一步”，不仅要update max，还要update 表。
|
s*****y
发帖数: 897 | 13 Your algorithm is so niu.
【在 g***s 的大作中提到】
: 这题跟最大直方图是一个思路。
: 同理，用类似“发个湾区P公司的第一轮phone interview”第二题的方法也可解。
|
j***y
发帖数: 2074 | 14
为什么要去掉那个重复的字符呢？计数的时候把这个字符计为1不就好了吗？
可不可以用个最简单的方法：用一个map储存输入string中每个character
出现的次数，然后把map.end()-map.begin()不就是distinct character的数量了吗？
是不是我什么地方理解错了？
【在 f***g 的大作中提到】
: 你的意思是，如果碰到了重复的字符，前面当前的结果全部舍弃不要？
: 有重叠怎么办？
: 两个指针：
: 前面的尽量往前scan，直到查表发现重复。
: 如果发现重复
: 后面的往前走直到去除掉那个要重复的字符。
: 每次前面的走一步都要update max
|
