趋势科技的笔试题
今天去笔试，碰到一道编程题，求字符串最长不含重复字符的子串长度，请问大牛用什么算法比较好？
如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是字符集的大小
[解决办法]
忘了格式了，重贴代码
#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;
}
#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;
}
//有码有真相
#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;
}
flag为1时就表示已经出现过了
我没理解到O（n）的解法，那位能贴下代码么。
[解决办法]
用不到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;
}
#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;
}
#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;
}
#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;
}
#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;
}
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;
}
delete []temp;
temp=0;
return max;
}
int main()
{
char * arr = "abcbef";
cout<<setMax(arr)<<endl;;
return 0;
}
[解决办法]
更正自己出错的代码
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;
}
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;
}
map+pair<char,int>去装每个字符
、
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;
}
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;
}
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;
}
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;
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;
