EB3 485 assigned to an office，是快有消息了吗？# EB23 - 劳工卡
d*a
1 楼
给定字符串，求其不出现重复字符的子字符串的最大长度，如何测试。
比如，“abcabcbb”最大的就是“abc”长度3
“bbbbb”最大就是“b”长度1
比如，“abcabcbb”最大的就是“abc”长度3
“bbbbb”最大就是“b”长度1
m*f
2 楼
议员得到回复，case 6/4 assigned to an office for adjudication. 一般这中情况
还要等多久？
还要等多久？
i*e
3 楼
LZ 谢谢分享。
我能想到的是用一个 table + double ended queue，O(n)，不知道还能不能更优化.
table 用来记录当前的字符访问过没.
每遇到一个不曾碰过的字符就 push 到 queue 的后边，然后纪录在 table 里.
如果字符被访问过了，就 update 一下 maximum length，然后一个一个从前头 pop，
直到 pop 出来的字符和此字符相等. 每次 pop 的时候也要更新 table.
总复杂度应该是 O(n)，因为每个字符最多被 push 和 pop 各一次.
解法有点类似于 google 的 sliding window 经典题.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
我能想到的是用一个 table + double ended queue，O(n)，不知道还能不能更优化.
table 用来记录当前的字符访问过没.
每遇到一个不曾碰过的字符就 push 到 queue 的后边，然后纪录在 table 里.
如果字符被访问过了，就 update 一下 maximum length，然后一个一个从前头 pop，
直到 pop 出来的字符和此字符相等. 每次 pop 的时候也要更新 table.
总复杂度应该是 O(n)，因为每个字符最多被 push 和 pop 各一次.
解法有点类似于 google 的 sliding window 经典题.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
c*6
4 楼
PD?
RD?
Center??
Weather?
【在 m**f 的大作中提到】
: 议员得到回复，case 6/4 assigned to an office for adjudication. 一般这中情况
: 还要等多久？
RD?
Center??
Weather?
【在 m**f 的大作中提到】
: 议员得到回复，case 6/4 assigned to an office for adjudication. 一般这中情况
: 还要等多久？
f*4
5 楼
随便想的：
用一个256的table记录字符出现的情况，一快一慢两个指针，
快指针每向前移动一个字符就判断是不是已经出现过了，若没
出现过则继续前进，若出现过了则更新最大长度值，然后让慢
指针前进到快指针遇到的那个字符的后一个（因为只要有一个
重复的就不符合要求）
复杂度O(N)吧
【在 d******a 的大作中提到】
: 给定字符串，求其不出现重复字符的子字符串的最大长度，如何测试。
: 比如，“abcabcbb”最大的就是“abc”长度3
: “bbbbb”最大就是“b”长度1
用一个256的table记录字符出现的情况，一快一慢两个指针，
快指针每向前移动一个字符就判断是不是已经出现过了，若没
出现过则继续前进，若出现过了则更新最大长度值，然后让慢
指针前进到快指针遇到的那个字符的后一个（因为只要有一个
重复的就不符合要求）
复杂度O(N)吧
【在 d******a 的大作中提到】
: 给定字符串，求其不出现重复字符的子字符串的最大长度，如何测试。
: 比如，“abcabcbb”最大的就是“abc”长度3
: “bbbbb”最大就是“b”长度1
m*r
6 楼
adjudication拿不到卡的，要一直等到有名额，所以还是要等到10月，不过至少有准信了
【在 m**f 的大作中提到】
: 议员得到回复，case 6/4 assigned to an office for adjudication. 一般这中情况
: 还要等多久？
【在 m**f 的大作中提到】
: 议员得到回复，case 6/4 assigned to an office for adjudication. 一般这中情况
: 还要等多久？
f*4
7 楼
厄 你的想法跟我一样 那就只要快慢指针就可以了
不用queue了
PS：你的blog很好 学习中。。。
PS：我的pre-order,in-order,post-order
遍历的代码对吗？
【在 i**********e 的大作中提到】
: LZ 谢谢分享。
: 我能想到的是用一个 table + double ended queue，O(n)，不知道还能不能更优化.
: table 用来记录当前的字符访问过没.
: 每遇到一个不曾碰过的字符就 push 到 queue 的后边，然后纪录在 table 里.
: 如果字符被访问过了，就 update 一下 maximum length，然后一个一个从前头 pop，
: 直到 pop 出来的字符和此字符相等. 每次 pop 的时候也要更新 table.
: 总复杂度应该是 O(n)，因为每个字符最多被 push 和 pop 各一次.
: 解法有点类似于 google 的 sliding window 经典题.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
不用queue了
PS：你的blog很好 学习中。。。
PS：我的pre-order,in-order,post-order
遍历的代码对吗？
【在 i**********e 的大作中提到】
: LZ 谢谢分享。
: 我能想到的是用一个 table + double ended queue，O(n)，不知道还能不能更优化.
: table 用来记录当前的字符访问过没.
: 每遇到一个不曾碰过的字符就 push 到 queue 的后边，然后纪录在 table 里.
: 如果字符被访问过了，就 update 一下 maximum length，然后一个一个从前头 pop，
: 直到 pop 出来的字符和此字符相等. 每次 pop 的时候也要更新 table.
: 总复杂度应该是 O(n)，因为每个字符最多被 push 和 pop 各一次.
: 解法有点类似于 google 的 sliding window 经典题.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
m*f
8 楼
修改了原贴，EB3, June current。
信了
【在 m********r 的大作中提到】
: adjudication拿不到卡的，要一直等到有名额，所以还是要等到10月，不过至少有准信了
信了
【在 m********r 的大作中提到】
: adjudication拿不到卡的，要一直等到有名额，所以还是要等到10月，不过至少有准信了
n*y
9 楼
欢迎拍砖，就用了一个 256 字节的table来检查一个数字是否出现过
#include
#include
#include
#include
char* nextpointer(char* str, int strlen)
{
char *p = str;
char *pend = str + strlen;
char count[256];
memset(count, 0, sizeof(count));
while (p < pend)
{
++count[*p];
if (count[*p] > 1)
{
return p;
}
++p;
}
return p;
}
void longestsingle(char* str, int strlen)
{
char *pstart = str;
char *pend;
char *pnextstart;
int len;
int longestlen = -1;
char *plongest = str;
char output[256];
if ( (str == NULL) || (strlen == 0) )
{
return;
}
pend = str + strlen;
while (pstart < pend)
{
pnextstart = nextpointer(pstart, strlen);
len = pnextstart - pstart;
if (len > longestlen)
{
plongest = pstart;
longestlen = len;
}
pstart = pnextstart;
strlen -= len;
}
memset(output, 0, sizeof(output));
memcpy(output, plongest, longestlen);
printf("longest non duplicate string from position %d: %s\n", plongest -
str, output);
return;
}
int main(int argc, char* argv[])
{
//cases to test
longestsingle(NULL, 0);
longestsingle("", strlen(""));
longestsingle("a", strlen("a"));
longestsingle("abcabcbb", strlen("abcabcbb"));
longestsingle("bbbbbb", strlen("bbbbbb"));
longestsingle("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ", strlen("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"));
longestsingle("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZZ", strlen("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZZ"));
longestsingle("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZa", strlen("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZa"));
longestsingle("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZa", strlen("
abcdefghijklmnopqrstuvwxyz01234567"));
longestsingle("abcdefghijklmnopqrstuvwxyz01234567", strlen("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZa"));
getchar();
return 0;
}
#include
#include
#include
#include
char* nextpointer(char* str, int strlen)
{
char *p = str;
char *pend = str + strlen;
char count[256];
memset(count, 0, sizeof(count));
while (p < pend)
{
++count[*p];
if (count[*p] > 1)
{
return p;
}
++p;
}
return p;
}
void longestsingle(char* str, int strlen)
{
char *pstart = str;
char *pend;
char *pnextstart;
int len;
int longestlen = -1;
char *plongest = str;
char output[256];
if ( (str == NULL) || (strlen == 0) )
{
return;
}
pend = str + strlen;
while (pstart < pend)
{
pnextstart = nextpointer(pstart, strlen);
len = pnextstart - pstart;
if (len > longestlen)
{
plongest = pstart;
longestlen = len;
}
pstart = pnextstart;
strlen -= len;
}
memset(output, 0, sizeof(output));
memcpy(output, plongest, longestlen);
printf("longest non duplicate string from position %d: %s\n", plongest -
str, output);
return;
}
int main(int argc, char* argv[])
{
//cases to test
longestsingle(NULL, 0);
longestsingle("", strlen(""));
longestsingle("a", strlen("a"));
longestsingle("abcabcbb", strlen("abcabcbb"));
longestsingle("bbbbbb", strlen("bbbbbb"));
longestsingle("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ", strlen("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"));
longestsingle("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZZ", strlen("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZZ"));
longestsingle("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZa", strlen("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZa"));
longestsingle("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZa", strlen("
abcdefghijklmnopqrstuvwxyz01234567"));
longestsingle("abcdefghijklmnopqrstuvwxyz01234567", strlen("
abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZa"));
getchar();
return 0;
}
i*e
10 楼
恩，很好，利用两个指针就可以解了.
的确没必要用额外的 queue.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 f*******4 的大作中提到】
: 随便想的：
: 用一个256的table记录字符出现的情况，一快一慢两个指针，
: 快指针每向前移动一个字符就判断是不是已经出现过了，若没
: 出现过则继续前进，若出现过了则更新最大长度值，然后让慢
: 指针前进到快指针遇到的那个字符的后一个（因为只要有一个
: 重复的就不符合要求）
: 复杂度O(N)吧
的确没必要用额外的 queue.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 f*******4 的大作中提到】
: 随便想的：
: 用一个256的table记录字符出现的情况，一快一慢两个指针，
: 快指针每向前移动一个字符就判断是不是已经出现过了，若没
: 出现过则继续前进，若出现过了则更新最大长度值，然后让慢
: 指针前进到快指针遇到的那个字符的后一个（因为只要有一个
: 重复的就不符合要求）
: 复杂度O(N)吧
i*e
11 楼
呵呵，先赞一个.
该叫你 Tracy 吗？呵呵
昨天我忙着 update 在 blog 里新的面试题，还没看你的代码.
现在头脑有点晕，我现在去看看哈 :)
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 f*******4 的大作中提到】
: 厄 你的想法跟我一样 那就只要快慢指针就可以了
: 不用queue了
: PS：你的blog很好 学习中。。。
: PS：我的pre-order,in-order,post-order
: 遍历的代码对吗？
该叫你 Tracy 吗？呵呵
昨天我忙着 update 在 blog 里新的面试题，还没看你的代码.
现在头脑有点晕，我现在去看看哈 :)
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 f*******4 的大作中提到】
: 厄 你的想法跟我一样 那就只要快慢指针就可以了
: 不用queue了
: PS：你的blog很好 学习中。。。
: PS：我的pre-order,in-order,post-order
: 遍历的代码对吗？
i*e
12 楼
感觉有点罗嗦，代码应该可以更简洁些的...
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 n********y 的大作中提到】
: 欢迎拍砖，就用了一个 256 字节的table来检查一个数字是否出现过
: #include
: #include
: #include
: #include
: char* nextpointer(char* str, int strlen)
: {
: char *p = str;
: char *pend = str + strlen;
: char count[256];
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 n********y 的大作中提到】
: 欢迎拍砖，就用了一个 256 字节的table来检查一个数字是否出现过
: #include
: #include
: #include
: #include
: char* nextpointer(char* str, int strlen)
: {
: char *p = str;
: char *pend = str + strlen;
: char count[256];
f*4
13 楼
好的
我还是刚起步的菜鸟。。。
【在 i**********e 的大作中提到】
: 呵呵，先赞一个.
: 该叫你 Tracy 吗？呵呵
: 昨天我忙着 update 在 blog 里新的面试题，还没看你的代码.
: 现在头脑有点晕，我现在去看看哈 :)
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
我还是刚起步的菜鸟。。。
【在 i**********e 的大作中提到】
: 呵呵，先赞一个.
: 该叫你 Tracy 吗？呵呵
: 昨天我忙着 update 在 blog 里新的面试题，还没看你的代码.
: 现在头脑有点晕，我现在去看看哈 :)
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
g*s
14 楼
这个省掉记录队列的想法确实不错。
不过正确的语义应该是queue/substr的head和tail，不是快慢指针。
【在 f*******4 的大作中提到】
: 厄 你的想法跟我一样 那就只要快慢指针就可以了
: 不用queue了
: PS：你的blog很好 学习中。。。
: PS：我的pre-order,in-order,post-order
: 遍历的代码对吗？
不过正确的语义应该是queue/substr的head和tail，不是快慢指针。
【在 f*******4 的大作中提到】
: 厄 你的想法跟我一样 那就只要快慢指针就可以了
: 不用queue了
: PS：你的blog很好 学习中。。。
: PS：我的pre-order,in-order,post-order
: 遍历的代码对吗？
j*u
15 楼
这个短些，用你的思路
static int LongestUniqueSubstring(string str)
{
if (string.IsNullOrEmpty(str)) return 0;
var lastPosition = new Dictionary(); // or use array with len
gth of #unicode_char
int maxLength = 0;
for (int head = 0, tail = 0; tail < str.Length; tail++)
{
int last;
if (lastPosition.TryGetValue(str[tail], out last))
head = last + 1;
else
maxLength = Math.Max(maxLength, tail - head + 1);
lastPosition[str[tail]] = tail;
}
return maxLength;
}
【在 i**********e 的大作中提到】
: 感觉有点罗嗦，代码应该可以更简洁些的...
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
static int LongestUniqueSubstring(string str)
{
if (string.IsNullOrEmpty(str)) return 0;
var lastPosition = new Dictionary
gth of #unicode_char
int maxLength = 0;
for (int head = 0, tail = 0; tail < str.Length; tail++)
{
int last;
if (lastPosition.TryGetValue(str[tail], out last))
head = last + 1;
else
maxLength = Math.Max(maxLength, tail - head + 1);
lastPosition[str[tail]] = tail;
}
return maxLength;
}
【在 i**********e 的大作中提到】
: 感觉有点罗嗦，代码应该可以更简洁些的...
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
d*a
16 楼
确实两个指针，加个数组就能搞到O(n)了。事后想想这道题出的还是挺有水平的。
P*i
17 楼
table需要记录每个字符最后出现的位置，只记录是否出现过没法达到O(N)吧
【在 f*******4 的大作中提到】
: 随便想的：
: 用一个256的table记录字符出现的情况，一快一慢两个指针，
: 快指针每向前移动一个字符就判断是不是已经出现过了，若没
: 出现过则继续前进，若出现过了则更新最大长度值，然后让慢
: 指针前进到快指针遇到的那个字符的后一个（因为只要有一个
: 重复的就不符合要求）
: 复杂度O(N)吧
【在 f*******4 的大作中提到】
: 随便想的：
: 用一个256的table记录字符出现的情况，一快一慢两个指针，
: 快指针每向前移动一个字符就判断是不是已经出现过了，若没
: 出现过则继续前进，若出现过了则更新最大长度值，然后让慢
: 指针前进到快指针遇到的那个字符的后一个（因为只要有一个
: 重复的就不符合要求）
: 复杂度O(N)吧
s*l
18 楼
子字符串要求连续吗？
"abcabcbbd"的结果应该是3还是4?
估计应该是默认连续的，觉得可以用类似求最大和连续子序列的方法
我的C代码
http://fayaa.com/code/view/16599/
只用移动指针，不用额外空间。
【在 d******a 的大作中提到】
: 给定字符串，求其不出现重复字符的子字符串的最大长度，如何测试。
: 比如，“abcabcbb”最大的就是“abc”长度3
: “bbbbb”最大就是“b”长度1
i*e
19 楼
不用记录位置，记录是否出现过就可以了。
位置由两个指针来记录。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 P****i 的大作中提到】
: table需要记录每个字符最后出现的位置，只记录是否出现过没法达到O(N)吧
位置由两个指针来记录。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 P****i 的大作中提到】
: table需要记录每个字符最后出现的位置，只记录是否出现过没法达到O(N)吧
i*e
20 楼
Failed for this case:
"abcbde"
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*********l 的大作中提到】
:
: 子字符串要求连续吗？
: "abcabcbbd"的结果应该是3还是4?
: 估计应该是默认连续的，觉得可以用类似求最大和连续子序列的方法
: 我的C代码
: http://fayaa.com/code/view/16599/
: 只用移动指针，不用额外空间。
"abcbde"
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*********l 的大作中提到】
:
: 子字符串要求连续吗？
: "abcabcbbd"的结果应该是3还是4?
: 估计应该是默认连续的，觉得可以用类似求最大和连续子序列的方法
: 我的C代码
: http://fayaa.com/code/view/16599/
: 只用移动指针，不用额外空间。
s*l
21 楼
谢谢测试. 代码里有一个小bug,
line25
if (p
if (p
http://fayaa.com/code/view/16599/
算法还是一样，类似求最大和连续子序列
四个指针,curr_head,curr_tail记录当前不重复子串,
longest_begin和longest_end记录目前发现的最大不重复子串，
如果当前不重复子串比目前发现的最大不重复子串还要长，则更新。
【在 i**********e 的大作中提到】
: Failed for this case:
: "abcbde"
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
line25
if (p
if (p
http://fayaa.com/code/view/16599/
算法还是一样，类似求最大和连续子序列
四个指针,curr_head,curr_tail记录当前不重复子串,
longest_begin和longest_end记录目前发现的最大不重复子串，
如果当前不重复子串比目前发现的最大不重复子串还要长，则更新。
【在 i**********e 的大作中提到】
: Failed for this case:
: "abcbde"
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
i*e
22 楼
代码虽然对了，但是你这个不用 table 复杂度是很高的。
你不用表的话，就只有每次前进都从前指针一直往后扫，直到碰到后指针为止。这复杂
度没法做到 O(N)。
简单来说，不用表的复杂度是 O(N^2)，N 为字符串长度。（循环基本跟冒泡排序差不
多，你可以比较一下）
虽说表利用空间换取速度，但这问题区区那么一点空间，是非常值得的。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*********l 的大作中提到】
: 谢谢测试. 代码里有一个小bug,
: line25
: if (p
: if (p
: http://fayaa.com/code/view/16599/
: 算法还是一样，类似求最大和连续子序列
: 四个指针,curr_head,curr_tail记录当前不重复子串,
: longest_begin和longest_end记录目前发现的最大不重复子串，
你不用表的话，就只有每次前进都从前指针一直往后扫，直到碰到后指针为止。这复杂
度没法做到 O(N)。
简单来说，不用表的复杂度是 O(N^2)，N 为字符串长度。（循环基本跟冒泡排序差不
多，你可以比较一下）
虽说表利用空间换取速度，但这问题区区那么一点空间，是非常值得的。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*********l 的大作中提到】
: 谢谢测试. 代码里有一个小bug,
: line25
: if (p
: if (p
: http://fayaa.com/code/view/16599/
: 算法还是一样，类似求最大和连续子序列
: 四个指针,curr_head,curr_tail记录当前不重复子串,
: longest_begin和longest_end记录目前发现的最大不重复子串，
c*t
23 楼
"abcadabb"
答案应该是"bcad"吧
你的测出来不对
【在 n********y 的大作中提到】
: 欢迎拍砖，就用了一个 256 字节的table来检查一个数字是否出现过
: #include
: #include
: #include
: #include
: char* nextpointer(char* str, int strlen)
: {
: char *p = str;
: char *pend = str + strlen;
: char count[256];
答案应该是"bcad"吧
你的测出来不对
【在 n********y 的大作中提到】
: 欢迎拍砖，就用了一个 256 字节的table来检查一个数字是否出现过
: #include
: #include
: #include
: #include
: char* nextpointer(char* str, int strlen)
: {
: char *p = str;
: char *pend = str + strlen;
: char count[256];
s*l
24 楼
不用表肯定没有用表快，但是复杂度也没有那么糟糕。你也注意到了这问题区区那么一
点空间，可以分析一下内层循环的最坏情况和平均情况。
【在 i**********e 的大作中提到】
: 代码虽然对了，但是你这个不用 table 复杂度是很高的。
: 你不用表的话，就只有每次前进都从前指针一直往后扫，直到碰到后指针为止。这复杂
: 度没法做到 O(N)。
: 简单来说，不用表的复杂度是 O(N^2)，N 为字符串长度。（循环基本跟冒泡排序差不
: 多，你可以比较一下）
: 虽说表利用空间换取速度，但这问题区区那么一点空间，是非常值得的。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
点空间，可以分析一下内层循环的最坏情况和平均情况。
【在 i**********e 的大作中提到】
: 代码虽然对了，但是你这个不用 table 复杂度是很高的。
: 你不用表的话，就只有每次前进都从前指针一直往后扫，直到碰到后指针为止。这复杂
: 度没法做到 O(N)。
: 简单来说，不用表的复杂度是 O(N^2)，N 为字符串长度。（循环基本跟冒泡排序差不
: 多，你可以比较一下）
: 虽说表利用空间换取速度，但这问题区区那么一点空间，是非常值得的。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
s*l
25 楼
这个题目不错，还可以把字符换成其他范围更广的对象，比如URL, IP地址, 英文单词
等等。
【在 d******a 的大作中提到】
: 给定字符串，求其不出现重复字符的子字符串的最大长度，如何测试。
: 比如，“abcabcbb”最大的就是“abc”长度3
: “bbbbb”最大就是“b”长度1
等等。
【在 d******a 的大作中提到】
: 给定字符串，求其不出现重复字符的子字符串的最大长度，如何测试。
: 比如，“abcabcbb”最大的就是“abc”长度3
: “bbbbb”最大就是“b”长度1
i*e
26 楼
呵呵，
想说 O(N^2) 和 O(N) 的复杂度相差不大，有没有搞错？
不过这问题由于局限于26个不同的字母，所以可以保证过了26个字母就会有至少一个重
复的。
万一如果没有这样的局限，你的代码肯定会跑得更慢了。。只要一直没遇到重复的，你
的指针就一直要从头开始扫描.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*********l 的大作中提到】
: 不用表肯定没有用表快，但是复杂度也没有那么糟糕。你也注意到了这问题区区那么一
: 点空间，可以分析一下内层循环的最坏情况和平均情况。
想说 O(N^2) 和 O(N) 的复杂度相差不大，有没有搞错？
不过这问题由于局限于26个不同的字母，所以可以保证过了26个字母就会有至少一个重
复的。
万一如果没有这样的局限，你的代码肯定会跑得更慢了。。只要一直没遇到重复的，你
的指针就一直要从头开始扫描.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*********l 的大作中提到】
: 不用表肯定没有用表快，但是复杂度也没有那么糟糕。你也注意到了这问题区区那么一
: 点空间，可以分析一下内层循环的最坏情况和平均情况。
s*l
27 楼
所以对这道题来说，即使不用额外空间，时间复杂度也是O(kN)，
k的上限和N无关, 所以不能说是O(N^2),而且平均情况下k会小很多
看出现重复的概率, 没有错, 样本空间越大,重复概率越低, 平均扫描长度越长,
所以对那些假定样本空间可以无限大的情况, 最坏情况下复杂度会退化到O(N^2), 但同
样用Hash的话,最坏情况下的时空复杂度会是多少?
【在 i**********e 的大作中提到】
: 呵呵，
: 想说 O(N^2) 和 O(N) 的复杂度相差不大，有没有搞错？
: 不过这问题由于局限于26个不同的字母，所以可以保证过了26个字母就会有至少一个重
: 复的。
: 万一如果没有这样的局限，你的代码肯定会跑得更慢了。。只要一直没遇到重复的，你
: 的指针就一直要从头开始扫描.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
P*i
28 楼
那每次前边的下标移动的时候都得更新一遍table
【在 i**********e 的大作中提到】
: 不用记录位置，记录是否出现过就可以了。
: 位置由两个指针来记录。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
【在 i**********e 的大作中提到】
: 不用记录位置，记录是否出现过就可以了。
: 位置由两个指针来记录。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
相关阅读
复印件需不需要彩色的？HR3012独家消息有最近办过出生公证的么，说10月1号后格式改了？律师要的材料清单很奇怪NIU筹建DC分会，有感兴趣的朋友吗？11月交的485，今天收到EAD/AP卡了。到底是485交了后半年，还是绿卡拿到半年可以不受限制换工作LD是加拿大绿卡不愿意来美国,我能自己file, 不file她吗?交了485以后在pending期间可以renew/extend H1B么？09年前驾车去加拿大WINDSOR当天回来，美国海关没索要签证，也没要求填I-94 白卡，I-485上拿到绿卡后？填表的字体能变小不？大家帮看看这个对RFE的SR回信是啥意思？485材料清单里有1040/w2/paycheck吗？这种情况要不要催绿请问有多少11月上旬的RD还没收到指纹通知？请教EAD/AP申请打指纹一问下周开车去Dallas， 自己去查他们为什么不给我 receipt终于看明白了Irish的阴谋