趋势科技的笔试题,该如何处理

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

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

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

O(n)的时间和O(字符集)的空间可以搞定
[解决办法]

#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是字符集的大小
[解决办法]
忘了格式了，重贴代码

C/C++ code

#define CHAR_SET_SIZE 26int 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;}
[解决办法]
我的方法有点笨！
[code=C/C++][/code]
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为输入字符串的长度
[解决办法]
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<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;}
[解决办法]
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[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;} 
 
[解决办法]
我这个有点笨，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）的解法，那位能贴下代码么。
[解决办法]
C/C++ code
用不到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;}
[解决办法]
用递归很方便，
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 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;}
[解决办法]
探讨


用递归很方便，
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……

[解决办法]
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;
}

[解决办法]
[code=C] 
 #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; 
 } 
 [/code]
[解决办法]
令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],所以只需要一个元素即可
[解决办法]
想不出这个DP啊.
我觉得就是扫描加记录啊,从头开始扫,遇到重复的就停下,记录max.
然后把第一个字符的记录扣掉,再从当前位置判断一下,重复的话继续扣掉第二个字符,否则继续前进就是了.
[解决办法]
C/C++ code
#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;}
[解决办法]
探讨

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<……

[解决办法]
探讨


引用:
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……

[解决办法]
探讨

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

[解决办法]
探讨

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

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

[解决办法]
探讨

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……

[解决办法]
探讨

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……

[解决办法]
探讨


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……

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

字符串：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,......................

剩下不解释。
[解决办法]
我的方法比较笨。。。
#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;

}


[解决办法]
更正自己出错的代码
C/C++ code
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;}
[解决办法]
C/C++ code
int func(char* text){    assert(text);    int nCurrLen = 0;    int nMaxLen = 0;    int nRepeatedPos = -1;    char hash_table[256] = {0}; //hash全字符    char const* p = text;        for (int i = 0; p[i] != '\0'; ++i)    {        if (hash_table[p[i]] == 0)  //当前字符不重复        {            hash_table[p[i]] = 1;  //设置重复标识            ++nCurrLen;            if (nCurrLen > nMaxLen)            {                nMaxLen = nCurrLen;            }        }        else  //当前字符重复        {            for (int j = 0; j < i; ++j)            {                hash_table[p[j]] = 0;  //清楚重复字符之前的所有标识                if (p[i] == p[j])                {                    nRepeatedPos = j; //记录重复字符第一次出现位置                    break;                }            }            nCurrLen -= (nRepeatedPos + 1);  //当前长度减去重复字符之前的长度            --i;        }    }    return nMaxLen;}
[解决办法]
感觉用堆栈，UINT MaxLen=0;读入一个字符与栈中每个比较（从栈底开始），若相同则将栈底到相同点之间的串取出，和MaxLen比较，结束后留在栈中的串Len再与MaxLen比较。26*O(n)=O(n)
------解决方案-------------------- 
 
C/C++ code
map+pair<char,int>去装每个字符
[解决办法]
如果用鸽巢算发呢?
定义数组A[26],0-25分别对应A-Z,每读取一个字符相应的A[i]值加1;
再定义数组B[A[i]],当第一个B[j]为2出现时,累加所有A[i]值为1(判断有多少个A[i]为1),得到的数就是最大子串的长度了。
[解决办法]
hash
[解决办法]
这个问题看着好眼熟呀。
[解决办法]
C/C++ code
、int find_maxlength(const char *str){    int IsAppear[26]={0};   // mark to know if the character appeared    int curleng=0,maxlength=0;    char *p=NULL;    if (!str)    {        return 0;    }    p=str;    while(*p)    {        int index=*p-'a';           if (!IsAppear[index])        {            IsAppear[index]=1;            curleng++;        }        else        {            curleng=0;        }        if (curleng>maxlength)        {            maxlength=curleng;        }        p++;    }    return maxlength;}void main(){    char *s="abcbec";    int length=find_maxlength(s);    cout<<length<<endl;}
[解决办法]
#define Max 256
int dictionary[Max];
int dp[Max];
int _max;
int Dp(char *source, int length)
{
_max = 0;
for ( int i = 0; i < Max; i++ )
{
dictionary[i] = length;
}

for ( int i = 0; i < length; i++)
{
dp[i] = length;
}

for ( int i = length-2; i >= 0; i--)
{
if ( dp[i+1] < dictionary[source[i]-'a'])
{
dp[i] = dp[i+1];
}
else
{
dp[i] = dictionary[source[i]-'a'];
}
dictionary[source[i]-'a'] = i;
if ( _max < dp[i] - i )
{
_max = dp[i] - i;
}
}

return  dp[0];
}
[解决办法]
C# 代码，不好意思
C# code
        public int GetMaxLengthOfSubstringWithoutDuplicateChars(string s)        {            Queue<char> queue = new Queue<char>();            int result = 0;            for (int i = 0; i < s.Length; i++)            {                if (queue.Contains(s[i]))                {                    queue.Clear();                }                queue.Enqueue(s[i]);                if (queue.Count > result)                {                    result = queue.Count;                }            }            return result;        }
[解决办法]
探讨


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

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

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

[解决办法]
C/C++ code
int solve(char* ary,int len){    if(ary==NULL || len<0)        return 0;    int max=0,currentMax=0,minPos=0,index=0;    int hash[27]={0};        for(int i=0;i<len;i++)    {        index=ary[i]-'a'+1;        if(hash[index]!=0)        {            if(hash[index]-1>=minPos)            {                currentMax=i-hash[index]+1;                minPos=hash[index];            }            else                currentMax=i-minPos+1;        }        else            currentMax=i-minPos+1;        hash[index]=i+1;        if(currentMax>max)            max=currentMax;    }    return max;}int main(){    char ary[]="fedff";    cout<<solve(ary,sizeof(ary)/sizeof(char)-1);    system("pause");    return 0;} 
 
[解决办法]
探讨


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<len;i++……

[解决办法]
探讨


C/C++ code

int func(char* text)
{
    assert(text);
    int nCurrLen = 0;
    int nMaxLen = 0;
    int nRepeatedPos = -1;
    char hash_table[256] = {0}; //hash全字符
    char const* p = text;
    
  ……

[解决办法]
Delphi(Pascal) code
function TForm2.HFindMostlong(str: string): string;var I:integer; m_str:string;begin  result:='';  m_str:='';  for I := 1 to length(str) do  begin    if HIsHaveChar(m_str,str[I]) then    begin      if length(m_str) > length(result) then result := m_str ;      m_str:='';    end;    m_str := m_str + str[I];  end;end;function TForm2.HIsHaveChar(str: string; mChar: char): boolean;var i:integer;begin  result := false;  for I := 1 to length(str) do  begin    if mchar = str[i] then result := true;  end;end;
[解决办法]
看了 71楼的评论 发现 我的也有漏洞 改了 代码
Delphi(Pascal) code
function TForm2.HFindMostlong(str: string): string;var I:integer; m_str:string;begin  result:='';  m_str:='';  for I := 1 to length(str) do  begin    if HIsHaveChar(m_str,str[I]) then    begin      if length(m_str) > length(result) then result := m_str ;      m_str:='';    end;    m_str := m_str + str[I];  end;  if length(m_str) > length(result) then result := m_str ;end;function TForm2.HIsHaveChar(str: string; mChar: char): boolean;var i:integer;begin  result := false;  for I := 1 to length(str) do  begin    if mchar = str[i] then result := true;  end;end;