d******a
发帖数: 238 | 1 给定字符串，求其不出现重复字符的子字符串的最大长度，如何测试。
比如，“abcabcbb”最大的就是“abc”长度3
“bbbbb”最大就是“b”长度1 |
i**********e
发帖数: 1145 | 2 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 |
f*******4
发帖数: 1401 | 3 随便想的：
用一个256的table记录字符出现的情况，一快一慢两个指针，
快指针每向前移动一个字符就判断是不是已经出现过了，若没
出现过则继续前进，若出现过了则更新最大长度值，然后让慢
指针前进到快指针遇到的那个字符的后一个（因为只要有一个
重复的就不符合要求）
复杂度O(N)吧
【在 d******a 的大作中提到】
: 给定字符串，求其不出现重复字符的子字符串的最大长度，如何测试。
: 比如，“abcabcbb”最大的就是“abc”长度3
: “bbbbb”最大就是“b”长度1
|
f*******4
发帖数: 1401 | 4 厄 你的想法跟我一样 那就只要快慢指针就可以了
不用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
|
n********y
发帖数: 66 | 5 欢迎拍砖，就用了一个 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;
} |
i**********e
发帖数: 1145 | 6 恩，很好，利用两个指针就可以解了.
的确没必要用额外的 queue.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 f*******4 的大作中提到】
: 随便想的：
: 用一个256的table记录字符出现的情况，一快一慢两个指针，
: 快指针每向前移动一个字符就判断是不是已经出现过了，若没
: 出现过则继续前进，若出现过了则更新最大长度值，然后让慢
: 指针前进到快指针遇到的那个字符的后一个（因为只要有一个
: 重复的就不符合要求）
: 复杂度O(N)吧
|
i**********e
发帖数: 1145 | 7 呵呵，先赞一个.
该叫你 Tracy 吗？呵呵
昨天我忙着 update 在 blog 里新的面试题，还没看你的代码.
现在头脑有点晕，我现在去看看哈 :)
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 f*******4 的大作中提到】
: 厄 你的想法跟我一样 那就只要快慢指针就可以了
: 不用queue了
: PS：你的blog很好 学习中。。。
: PS：我的pre-order,in-order,post-order
: 遍历的代码对吗？
|
i**********e
发帖数: 1145 | 8 感觉有点罗嗦，代码应该可以更简洁些的...
一些常见面试题的答案与总结 -
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
发帖数: 1401 | 9 好的
我还是刚起步的菜鸟。。。
【在 i**********e 的大作中提到】
: 呵呵，先赞一个.
: 该叫你 Tracy 吗？呵呵
: 昨天我忙着 update 在 blog 里新的面试题，还没看你的代码.
: 现在头脑有点晕，我现在去看看哈 :)
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
g*********s
发帖数: 1782 | 10 这个省掉记录队列的想法确实不错。
不过正确的语义应该是queue/substr的head和tail，不是快慢指针。
【在 f*******4 的大作中提到】
: 厄 你的想法跟我一样 那就只要快慢指针就可以了
: 不用queue了
: PS：你的blog很好 学习中。。。
: PS：我的pre-order,in-order,post-order
: 遍历的代码对吗？
|
|
|
j*****u
发帖数: 1133 | 11 这个短些，用你的思路
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
|
d******a
发帖数: 238 | 12 确实两个指针，加个数组就能搞到O(n)了。事后想想这道题出的还是挺有水平的。 |
P****i
发帖数: 1362 | 13 table需要记录每个字符最后出现的位置，只记录是否出现过没法达到O(N)吧
【在 f*******4 的大作中提到】
: 随便想的：
: 用一个256的table记录字符出现的情况，一快一慢两个指针，
: 快指针每向前移动一个字符就判断是不是已经出现过了，若没
: 出现过则继续前进，若出现过了则更新最大长度值，然后让慢
: 指针前进到快指针遇到的那个字符的后一个（因为只要有一个
: 重复的就不符合要求）
: 复杂度O(N)吧
|
s*********l
发帖数: 103 | 14
子字符串要求连续吗？
"abcabcbbd"的结果应该是3还是4?
估计应该是默认连续的，觉得可以用类似求最大和连续子序列的方法
我的C代码
http://fayaa.com/code/view/16599/
只用移动指针，不用额外空间。
【在 d******a 的大作中提到】
: 给定字符串，求其不出现重复字符的子字符串的最大长度，如何测试。
: 比如，“abcabcbb”最大的就是“abc”长度3
: “bbbbb”最大就是“b”长度1
|
i**********e
发帖数: 1145 | 15 不用记录位置，记录是否出现过就可以了。
位置由两个指针来记录。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 P****i 的大作中提到】
: table需要记录每个字符最后出现的位置，只记录是否出现过没法达到O(N)吧
|
i**********e
发帖数: 1145 | 16 Failed for this case:
"abcbde"
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*********l 的大作中提到】
:
: 子字符串要求连续吗？
: "abcabcbbd"的结果应该是3还是4?
: 估计应该是默认连续的，觉得可以用类似求最大和连续子序列的方法
: 我的C代码
: http://fayaa.com/code/view/16599/
: 只用移动指针，不用额外空间。
|
s*********l
发帖数: 103 | 17 谢谢测试. 代码里有一个小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
|
i**********e
发帖数: 1145 | 18 代码虽然对了，但是你这个不用 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记录目前发现的最大不重复子串，
|
c*******t
发帖数: 1095 | 19 "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];
|
s*********l
发帖数: 103 | 20 不用表肯定没有用表快，但是复杂度也没有那么糟糕。你也注意到了这问题区区那么一
点空间，可以分析一下内层循环的最坏情况和平均情况。
【在 i**********e 的大作中提到】
: 代码虽然对了，但是你这个不用 table 复杂度是很高的。
: 你不用表的话，就只有每次前进都从前指针一直往后扫，直到碰到后指针为止。这复杂
: 度没法做到 O(N)。
: 简单来说，不用表的复杂度是 O(N^2)，N 为字符串长度。（循环基本跟冒泡排序差不
: 多，你可以比较一下）
: 虽说表利用空间换取速度，但这问题区区那么一点空间，是非常值得的。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
|
|
s*********l
发帖数: 103 | 21 这个题目不错，还可以把字符换成其他范围更广的对象，比如URL, IP地址, 英文单词
等等。
【在 d******a 的大作中提到】
: 给定字符串，求其不出现重复字符的子字符串的最大长度，如何测试。
: 比如，“abcabcbb”最大的就是“abc”长度3
: “bbbbb”最大就是“b”长度1
|
i**********e
发帖数: 1145 | 22 呵呵，
想说 O(N^2) 和 O(N) 的复杂度相差不大，有没有搞错？
不过这问题由于局限于26个不同的字母，所以可以保证过了26个字母就会有至少一个重
复的。
万一如果没有这样的局限，你的代码肯定会跑得更慢了。。只要一直没遇到重复的，你
的指针就一直要从头开始扫描.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*********l 的大作中提到】
: 不用表肯定没有用表快，但是复杂度也没有那么糟糕。你也注意到了这问题区区那么一
: 点空间，可以分析一下内层循环的最坏情况和平均情况。
|
s*********l
发帖数: 103 | 23
所以对这道题来说，即使不用额外空间，时间复杂度也是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
发帖数: 1362 | 24 那每次前边的下标移动的时候都得更新一遍table
【在 i**********e 的大作中提到】
: 不用记录位置，记录是否出现过就可以了。
: 位置由两个指针来记录。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
