趋势科技的笔试题

今天去笔试，碰到一道编程题，求字符串最长不含重复字符的子串长度，请问大牛用什么算法比较好？
如abcbec，就返回3

80 个解决方案

#1

用dp[i]表示以第i个字符开始的最长不重复子串的右端点位置。
用appear[x]表示字符x最近一次的出现位置。

从右往左扫描。
初始情况下dp[n+1] = n + 1; apear[所有字符] = n + 1;
假设扫描到第i个字符，
那么以i开始最长的，应该是 第i个字符最近出现的位置左边 和 以dp[i+1]的较小者。

O(n)的时间和O(字符集)的空间可以搞定

#2

么以i开始最长的，应该是 第i个字符最近出现的位置左边 和 以dp[i+1]的较小者。

没看明白...
直觉上觉得时间O(n)不能...

#3

"那么以i开始最长的，应该是 第i个字符最近出现的位置左边 和 以dp[i+1]的较小者。"
应该是较大者吧,递归,DP问题,不过O(n)就觉得不太可能,最好的情况是O(n)倒是对的

#4

#define CHAR_SET_SIZE 256

int GetMaxUSubStrLen(char *s)
{
    int maxLen = 0;
    int times[CHAR_SET_SIZE] = {0};
    char *pStart, *pEnd;

    pStart = pEnd = s;
    while (*pEnd != '\0')
    {
        int idx = GetCharIdx(*pEnd);
        if (times[idx] == 0)
        {
            ++pEnd;
            times[idx] = 1;
            if (pEnd - pStart > maxLen)
                maxLen = pEnd - pStart;
        }
        else
        {
            int idx_s = GetCharIdx(*pStart);
            times[idx_s] = 0;
            ++pStart;
        }
    }

    return maxLen;
}
假设GetCharIdx()可以在O(1)时间内完成, 上面得循环每次或者pStart加1，或者pEnd加1。
到pStart和pEnd都到字符串结尾时肯定结束，因此最多循环2n次。
该算法时间复杂度是O(n), 空间复杂度是O(m) m是字符集的大小

#5

忘了格式了，重贴代码

#define CHAR_SET_SIZE 26

int GetMaxUSubStrLen(char *s)
{
    int maxLen = 0;
    int times[CHAR_SET_SIZE] = {0};
    char *pStart, *pEnd;

    pStart = pEnd = s;
    while (*pEnd != '\0')
    {
        int idx = GetCharIdx(*pEnd);
        if (times[idx] == 0)
        {
            ++pEnd;
            times[idx] = 1;
            if (pEnd - pStart > maxLen)
                maxLen = pEnd - pStart;
        }
        else
        {
            int idx_s = GetCharIdx(*pStart);
            times[idx_s] = 0;
            ++pStart;
        }
    }

    return maxLen;
}

#6

我的方法有点笨！

int MAX_String(char* ch,int len)
{
for(int i=0;i<len;i++)
{
for(int j=i+1;j<len;j++)
{
if(ch[i]==ch[j])
{
len=j+1;
break;
}
}
}
return len-1;
}
len为输入字符串的长度

#7

DP问题

#8

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int DP(char* arr)
{
    int len = (int)strlen(arr);
    int* pResult = (int*)malloc(sizeof(int)*len);
    for(int i=0;i<len;i++)pResult[i]=1;
    int Max = 1;
    int Allalph[256];
    for(int i=0;i<256;i++)Allalph[i]=-1;

    for (int i = 0 ; i < len; i++)
    {
        
        if(Allalph[arr[i]]!=-1)//出现过啦
            memset(Allalph,-1,Allalph[arr[i]]+1),i-1>=0 ? (Allalph[pResult[i-1]]=0):(NULL),pResult[i]=i-Allalph[arr[i]];
        else
            Allalph[arr[i]]=i,i-1>=0 ? (pResult[i]=pResult[i-1]+1):(NULL), pResult[i]>Max?(Max=pResult[i]):(NULL);
    }
    return Max;
}
int main()
{
    char* arr = "2123123456";
    printf("%d",DP(arr));
    return 0;

}

#9

楼主这么早起来发贴，强，，学习

#10

//有码有真相

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	const char* str = "abcbec";
	const int n = strlen(str);
	int dp[256], last[256];
	for (int i = 0; i < 256; ++i) last[i] = n;
	dp[n] = n;
	for (int i = n - 1; i >= 0; --i)
	{
		dp[i] = min(dp[i+1], last[str[i]] - 1);
		last[str[i]] = i;
	}
	int ans = -1;
	for (int i = 0; i < n; ++i) if (dp[i] - i > ans) ans = dp[i] - i;
	printf("%d\n", ans + 1);
	return 0;
}

#11

我这个有点笨，O(nlogn)：

如果字符包括了abc....xyz
则定义一段连续内存（比如数组，vector）
struct unit{
char c;
int flag;
};

struct unit un[26];//连续，有序：分别表示a-z 26个字符，flag初始为0

然后扫描字符串*p时，用二分在un里面查找:
flag为0时就写un[i].c=*p; un[i].flag=1;
flag为1时就表示已经出现过了

我没理解到O（n）的解法，那位能贴下代码么。

#12

STL 一行搞定〜

#include<iostream>
#include<string>
#include<set>

using namespace std;

int main (int argc, char * const argv[])
{

	string str="abcbec";

	///////////
	set<char> sl(str.begin(), str.end());

	//输出
	cout << sl.size();

	return 0;
}

#13

引用 12 楼 doox8086 的回复:

STL 一行搞定〜
C/C++ code

#include<iostream>
#include<string>
#include<set>

using namespace std;

int main (int argc, char * const argv[])
{

    string str="abcbec";
    
    ///////////
    set<char……

我很无语

#14

引用 12 楼 doox8086 的回复:

STL 一行搞定〜

－ －！！！

回头一看〜〜发觉理解错误〜。。原来是求 子串长

#15

用不到DP，简单的线性扫描就可以了
pre指向当前不重复字符串的起始位置
#include<stdio.h>
#include<memory.h>
int search(char *text)
{
	int pos[256],len,max=0,pre=0,i;
	unsigned char x;
	memset(pos,-1,sizeof(pos));
	for(i=0;text[i];++i)
	{
		x=text[i];
		if(pos[x]==-1||pos[x]<pre)
			pos[x]=i;
		else
		{
			len=i-pre;
			max=max>len?max:len;
			pre=pos[x]+1;
			pos[x]=i;
		}
	}
	max=max>i-pre?max:i-pre;
	return max;
}
int main()
{
	char text[1000000];
	while(gets(text))
		printf("%d\n",search(text));
	return 0;
}

#16

用递归很方便，
f(n)=f(n-1)+1   此时首字符不在子串中出现
f(n)=f(n-1)     此时首字符在子串中出现
f(n)=n          此时n=0或1

#include <iostream>
#include <string>
using namespace std;

size_t getMaxSubStrLen(const string& str)
{
	if (str.size() < 2) return str.size();

	// 对[1, n]的子串进行递归
	string tailStr(str.begin()+1, str.end());	
	size_t tailLen = getMaxSubStrLen(tailStr);

	if (tailStr.find(str[0]) < tailStr.size()) ++tailLen;
	return tailLen;
}

int main()
{
	string str("abcbec");
	cout<<"Max Sub-string length for '"<<str<<"' is "<<getMaxSubStrLen(str)<<endl;
	system("pause");
	return 0;
}

#17

引用 16 楼 xiaoboalex 的回复:

用递归很方便，
f(n)=f(n-1)+1   此时首字符不在子串中出现
f(n)=f(n-1)     此时首字符在子串中出现
f(n)=n          此时n=0或1

C/C++ code

#include <iostream>
#include <string>
using namespace std;

size_t getMaxSubStrLen(const st……

不好意思，上面的代码有问题，这样的递归并不成立。

#18

int foo(unsigned char *p)
{
   unsigned char c, f[256] = {0};
   int n;

   for (n=0; c=*p++; ++n)
      if (c != f[c]) f[c] = c; else break;

   return n;
}

#19

我觉得先简单排序,在相邻的数据比较，利用一个变量来记不同元素个数！就可以得出结果了！

#20

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX_CHAR_LEN 1024
typedef char bool;
#define true 1
#define false 0

int usage(int argc,char** argv)
{
	printf("%s string\n",argv[0]);
	return 1;
}
int Maxlen = -1;
int Index = 0;

bool findMaxSubStr(const char* Str,int BeginIndex)
{
	int length = 0;
	unsigned int charapps[255]= {0};
	char* p = Str+BeginIndex;
	while ( *p )
	{
		if ( charapps[*p] != 0 )
			return findMaxSubStr(Str,charapps[*p]);
		charapps[*p] = p-Str+1;
		length ++;
		if ( length > Maxlen )
		{
			Maxlen = length;
			Index = BeginIndex;
		}
		p++;
	}
	return true;
}


int main(int argc,char** argv)
{
	if ( argc != 2 )
		return usage(argc,argv);
	if ( findMaxSubStr(argv[1],0) == true )
	{
			argv[1][Index+Maxlen] = 0;
			printf("max length [%d],beginindex[%d],str[%s]\n",Maxlen,Index,argv[1]+Index);
	}
	return 0;
}

#21

飞雪飞雪～我爱你！ 你老霸道了！

#22

晕，清华版数据结构教程上面的例题。

#23

在O(1)的空间复杂度+ O(N)的时间复杂度内搞定

#24

恩 飞雪已经给出解了

#25

不错的题目,学习了

#26

令last[256]所有元素置为-1;
1. diff = i-last[str[i]];
2. cnt[i] = cnt[i-1]+1;  (cnt[i-1] < diff) 
             = diff      (cnt[i-1] >= diff) 
3. last[str[i]]=i; 
4. goto 1;  
因为只用到最后一个cnt[i],所以只需要一个元素即可

#27

飞飞 雪雪  

#28

引用 10 楼 baihacker 的回复:

C/C++ code

//有码有真相

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    const char* str = "abcbec";
    const int n = strlen(str);
    int dp[256], last……

我比较笨
没看懂，求解释

#29

#15 楼的代码比较容易理解
多谢各为~

#30

不错的题目,学习了

#31

只会最土的那种。。。泪奔

#32

不知道是哪个地方的趋势啊，现在对趋势也很关注，不知道待遇如何。

#33

是南京的趋势，在中国，趋势只有在南京才有研发中心，待遇：研究生 10W/Y，本科生 8W/Y,不过很难进

引用 32 楼 tojoevan 的回复:

不知道是哪个地方的趋势啊，现在对趋势也很关注，不知道待遇如何。

#34

看不懂啊看不懂.
谁能贴个清晰的说明.

#35

想不出这个DP啊.
我觉得就是扫描加记录啊,从头开始扫,遇到重复的就停下,记录max.
然后把第一个字符的记录扣掉,再从当前位置判断一下,重复的话继续扣掉第二个字符,否则继续前进就是了.

#36

#include <iostream>
#include <bitset>
using namespace std;

int main()
{
	string input="abcbec";
	bitset<26> letter;
	size_t max_len=1;

	for(string::size_type cur=0,st=0;cur!=input.size();)
	{
		if(letter[input[cur]-'a']==true)
		{
			if(cur-st>max_len)
			{
				max_len=cur-st;
			}
			letter.reset(input[st]-'a');
			st++;
		}
		else
		{
			letter.set(input[cur]-'a');
			++cur;
			if(cur-st>max_len)
			{
				max_len=cur-st;
			}
		}
	}

	cout<<max_len<<endl;
	return 0;
}

要我写,我就这样写.

意思就是字符标记的集合可以递推使用.

#37

引用 8 楼 ayw215 的回复:

C/C++ code
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int DP(char* arr)
{
    int len = (int)strlen(arr);
    int* pResult = (int*)malloc(sizeof(int)*len);
    for(int i=0;i<……

大哥，你这个程序有问题。memset(Allalph, -1, Allalph[arr[i]]+1);达不到你想要的效果。
试试：char* arr = "212731234567";

#38

引用 37 楼 wuxupeng999 的回复:

引用 8 楼 ayw215 的回复:
C/C++ code
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int DP(char* arr)
{
int len = (int)strlen(arr);
int* pResult = (int*)malloc(sizeof(int)*len);
for(i……

多谢提醒哈
我忘记了这里memset是按照char来设定的了
改改就ok啦

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int DP(char* arr)
{
    int len = (int)strlen(arr);
    int* pResult = (int*)malloc(sizeof(int)*len);
    for(int i=0;i<len;i++)pResult[i]=1;
    int Max = 1;
    int Allalph[256];
    for(int i=0;i<256;i++)Allalph[i]=-1;

    for (int i = 0 ; i < len; i++)
    {
        
        if(Allalph[arr[i]]!=-1)//出现过啦
        {
            for(int k = 0;k<Allalph[arr[i]];k++)Allalph[arr[k]]=-1;
            i-1>=0 ? (Allalph[pResult[i-1]]=0):(NULL),pResult[i]=i-Allalph[arr[i]];
        }
        else
            Allalph[arr[i]]=i,i-1>=0 ? (pResult[i]=pResult[i-1]+1):(NULL), pResult[i]>Max?(Max=pResult[i]):(NULL);
    }
    return Max;
}
int main()
{
    char* arr = "212731234567";
    printf("%d",DP(arr));
    return 0;

}

#39

引用 35 楼 qq120848369 的回复:

想不出这个DP啊.
我觉得就是扫描加记录啊,从头开始扫,遇到重复的就停下,记录max.
然后把第一个字符的记录扣掉,再从当前位置判断一下,重复的话继续扣掉第二个字符,否则继续前进就是了.

4楼的跟你的代码是同样的思路。同样，有个地方不太好。
当letter[input[cur]-'a']==true的时候， st++;然后继续循环，这样不好。在这种条件下循环里边的代码只有letter.reset(input[st]-'a');这一句会被执行。没必要在跑那么多次大循环。
改成这样：

        if(letter[input[cur]-'a'] == true)
        {
            if(cur - st > max_len)
            {
                max_len = cur - st;
            }
            while (input[st] != input[cur])
            {
                letter.reset(input[st] - 'a');
                 ++st;
            }
           ++st;
           ++cur;
        }

---------------
我觉得上边的几种算法（10楼、38楼）效率差不多。动态规划的还比较费空间。
不知道有没有高手愿意分析一下它们有没有性能差异

#40

学习学习

#41

引用 39 楼 wuxupeng999 的回复:

引用 35 楼 qq120848369 的回复:
想不出这个DP啊.
我觉得就是扫描加记录啊,从头开始扫,遇到重复的就停下,记录max.
然后把第一个字符的记录扣掉,再从当前位置判断一下,重复的话继续扣掉第二个字符,否则继续前进就是了.

4楼的跟你的代码是同样的思路。同样，有个地方不太好。
当letter[input[cur]-'a']==true的时候， st++;然后继续循环，这……

但是,要注意到st到cur始终没有重复.
如果st与cur重复了,那么st+1...cur不可能重复.

你的意思可能是为了节约if else的判断次数,我同意你.

#42

我前几天面华赛就是被这个难住了，~~~~(>_<)~~~~ 

#43

引用 10 楼 baihacker 的回复:

C/C++ code

//有码有真相

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    const char* str = "abcbec";
    const int n = strlen(str);
    int dp……

求解释 不懂什么是DP

#44

引用 10 楼 baihacker 的回复:

C/C++ code

//有码有真相

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    const char* str = "abcbec";
    const int n = strlen(str);
    int dp……

（1）在VC6.0下编译，其中min用不了啊？
（2）你的方法也不可行，abcbec应当输出4，你的输出3，是不是重赋值错误？

#45

引用 10 楼 baihacker 的回复:

C/C++ code

//有码有真相

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    const char* str = "abcbec";
    const int n = strlen(str);
    int dp[256], last……

求解释  ~(@^_^@)~

#46

估计很多人不懂,我献丑解释一下算法思想.

字符串：abcddefgghi

start(st)表示当前判断的 字符子串 起始端
end(e)表示当前判断的 字符子串 末端

1.st=1,e=1  标记a
2.st=1,e=2  标记b
3.st=1,e=3  标记c
4.st=1,e=4  标记d
5.st=1,e=5  d被标记过,所以st..e-1开头的子串是st=1开头的最长串
6.st=2,e=5  首先抹除string[st=1]的标记,判断string[e]是否标记过.如果string[e]被标记过,那么st...e-1是st=2开头的最长串.
7.st=3,e=5. 抹除string[st=2]发现string[e]还是被标记过,st++,st..e-1是st=3开头的最长传...
8.st=4,e=5  抹除string[st=3]发现string[e]还是被标记过，st++,st..e-1是st=3开头的最长传...

9.st=5,e=5  抹除string[st=4]发现string[e]=d没有标记过,所以e++
10.st=5,e=6,......................

剩下不解释。

#47

汗 ~~~~~不好意思看错了，呵呵，"abcbec"看成了"abcbef";

#48

我的方法比较笨。。。
#include<iostream>
#include<string>
using namespace std;

int setMax(char * text)
{
int len=strlen(text),tlen=0,max=0;
char * temp=new char[len+1];
char *ttemp=new char[len+1];
bool mark=false;
memset(temp,'\0',len);
temp[0]=text[0];
tlen=1;
max=tlen;
for(int i=0;i<len;i++)
{
int j;
for(j=0;j<tlen;j++)
{
if(text[i]!=temp[j])
{
mark=true;
continue;
}
else
{
mark=false;
max=tlen>max?tlen:max;
if(j+1<tlen)
{
int n=0;
for(int k=j+1;k<tlen;k++)
{
ttemp[n]=temp[k];
n++;
}
strcpy(temp,ttemp);
temp[n]=temp[j];
tlen=n+1;
}
else
{
temp[0]=temp[j];
tlen=1;
}
break;
}
}
if(j==tlen && mark==true)
{
temp[tlen++]=text[i];
}
}
max=tlen>max?tlen:max;
delete []temp;
temp=0;
return max;
}

int main()
{
    char * arr = "abcbef";
    cout<<setMax(arr)<<endl;;
    return 0;

}

#49

飞雪的方法很好，呵呵

#50

更正自己出错的代码

int foo(const unsigned char *p)
{
   unsigned char c;
   int i, l, m, f[256];
   int head = -1;

   for (i=0; i<256; ++i)
      f[i] = -1;

   for (i=0, m=0; c=*p++; ++i) {
      if (f[c] >= head)
         head = f[c] + 1;
      
      l = i - head + 1;
      m = max(l, m);
      f[c] = i;
   }

   return m;
}