趋势科技的笔试题

zhufeiguanghui 2010-09-30 02:26:32
今天去笔试，碰到一道编程题，求字符串最长不含重复字符的子串长度，请问大牛用什么算法比较好？
如abcbec，就返回3
...全文
2561 80 打赏 收藏 转发到动态 举报
写回复
用AI写文章
80 条回复
切换为时间正序
请发表友善的回复…
发表回复
fengll201216 2012-09-11
  • 打赏
  • 举报
 回复
真是个学习的好地方呀……
可以见识到各种算法思路～～～
好呀～～～
choclover 2012-04-03
  • 打赏
  • 举报
 回复
我也想的这种方法。
[Quote=引用 15 楼 的回复:]

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))……
[/Quote]
tianhenhei 2010-10-15
  • 打赏
  • 举报
 回复
#include <string>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;

int maxstr(const string&str)
{
int cur=0,sta=0,repeat;
int curlen=0,maxlen=0;
hash_map<char,int> hmap;

for(int i=0;i<str.size();++i)
{
if(hmap.find(str[i])==hmap.end())
{
curlen++;
if(maxlen<curlen) maxlen=curlen;
hmap[str[i]]=i;
}
else
{
repeat=hmap[str[i]];
if(repeat+1>sta)
sta=repeat+1;
curlen=i-sta+1;
hmap[str[i]]=i;
}
}
}
sunbody1986 2010-10-15
  • 打赏
  • 举报
 回复
我的。
效率低了，但是结果正确

#include <iostream>
#include <cassert>
using namespace std;
bool IsHaveChar(char inChar, const char *pStr, int strLength)
{
assert(pStr!=NULL);
for (int i=0; i<strLength; i++)
{
if (inChar == pStr[i])
{
return true;
}
}
return false;
}

int GetMaxSubstr(const char *str)
{
assert(str!=NULL);
int maxLength = 0;
const char *pResultPos = NULL;
int step = 0;
for (const char *pChar=str; *pChar!='\0'; pChar++)
{
for (step=1; *(pChar+step)!='\0'; step++)
{
if (IsHaveChar(*(pChar+step), pChar, step))
{
break;
}
else
{
if (step+1>maxLength)
{
maxLength = step+1;
pResultPos = pChar;
}
}
}
if ((pChar+step)=='\0')
{
break;
}
}
//////////////////////////////For Test///////////////////////////////////
cout<<"最长不重复子串"<<endl;
for (int i=0; i<maxLength; i++)
{
cout<<*(pResultPos+i);
}
cout<<endl;
//////////////////////////////////////////////////////////////////////////
return maxLength;
}

void main()
{
//char test[] = "2123123456";
char test[] = "abcbecghijkl";
cout<<test<<endl;
int max = GetMaxSubstr(test);
cout<<"最长不重复子串长度："<<endl;
cout<<max<<endl;
}
hhboring 2010-10-15
  • 打赏
  • 举报
 回复

program longabc;
var
a:array ['a'..'z']of integer;
s:string;
i,n,max,we:integer;
j:char;
dp:array[1..100]of integer;
begin
readln(s);
fillchar(dp,sizeof(dp),0);
n:=length(s);
we:=n+1;
for j:='a' to 'z' do
a[j]:=n+1;
for i:=n downto 1 do
begin
{if a[s[i]]=0 then
dp[i]:=dp[i+1]+1
else
dp[i]:=a[s[i]]-i;}
if we<a[s[i]] then
dp[i]:=we-i+1;
if we=a[s[i]] then
dp[i]:=we-i;
if we>a[s[i]] then
begin
dp[i]:=a[s[i]]-i;
we:=i;
end;
a[s[i]]:=i;
end;
max:=0;
for i:=1 to n do
if max<dp[i] then max:=dp[i];
writeln(max);
end.
we是距离i最近的重复字母
a记录上次s[i]出现的位置
也就是说 如果we<a[s[i]] 那么 这个字符串中间夹杂着其他重复过的字符 不能直接a[s[i]]-i
haoruixiang 2010-10-14
  • 打赏
  • 举报
 回复
看了 71楼的评论 发现 我的也有漏洞 改了 代码
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;
haoruixiang 2010-10-14
  • 打赏
  • 举报
 回复
嘿嘿 搞delphi的 来试试 大家多多指教啊
haoruixiang 2010-10-14
  • 打赏
  • 举报
 回复 
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;
盈都键盘侠 2010-10-14
  • 打赏
  • 举报
 回复
每天回帖赚10分
想要多吃饭 2010-10-11
  • 打赏
  • 举报
 回复
[Quote=引用 56 楼 yangjian8915 的回复:]

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;

……
[/Quote]

方法也不对，测试数据：
abcbecghijkl，返回值为7，应该为9
想要多吃饭 2010-10-11
  • 打赏
  • 举报
 回复
[Quote=引用 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<len;i++……
[/Quote]

这个方法是有问题的，
测试数据：
abcbecghijkl
返回值为7，其实应该为9的。
chin_chen 2010-10-10
  • 打赏
  • 举报
 回复 
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;

}
phil999 2010-10-09
  • 打赏
  • 举报
 回复
C# 代码，不好意思


        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;

        }
x642458 2010-10-09
  • 打赏
  • 举报
 回复
[Quote=引用 1 楼 baihacker 的回复:]

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

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

O(n)的时间和O(字符集)的空间可以搞定
[/Quote]
对，就KMP变形么
showjim 2010-10-08
  • 打赏
  • 举报
 回复
hash
zmr0469 2010-10-08
  • 打赏
  • 举报
 回复
#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];
}
你好小菜 2010-10-08
  • 打赏
  • 举报
 回复
这么早额 我也来学习额
liang_8918 2010-10-08
  • 打赏
  • 举报
 回复
如果用鸽巢算发呢?
定义数组A[26],0-25分别对应A-Z,每读取一个字符相应的A[i]值加1;
再定义数组B[A[i]],当第一个B[j]为2出现时,累加所有A[i]值为1(判断有多少个A[i]为1),得到的数就是最大子串的长度了。
xpjandy 2010-10-08
  • 打赏
  • 举报
 回复
这题目其实跟 求一数字序列中最大和一样
O(N)的算法
xpjandy 2010-10-08
  • 打赏
  • 举报
 回复 
、

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;

}
加载更多回复（58）
趋势科技笔试题 趋势科技的笔试题
趋势科技的笔试题 1、#include class A{ public: A() {func(0);}; virtual void func(int data) {printf("A1 :%d\n",data);} virtual void func(int data) const {printf("A2 :%d\n",data);} void func(char *str) {printf("A3 :(%s)\n",str);} }; class B:public A{ public: void func() {printf("B1 :%s\n","");} void func(int data) {printf("B2 :%d\n",data);} void func(char *str) {printf("B3 :(%s)\n",str);} };
趋势科技笔试真题
趋势科技的笔试真题，全英文扫描的很清晰，对于倾心趋势的同学，很具有参考价值。
直播访谈 |《问诊未来·院长系列: 长远趋势与转折点》
在谢丹阳教授看来，不管你是在哪一个领域和产业，首先在你的心中要把握几条长远趋势，第二个当这个转折点到来的时候你要能够比较正确的去做出反应。那么文明社会有哪些长远趋势？我们又该怎样判断“高危”和“良机”呢？相信这期直播会对不同领域的你我都有所助益。世界总是喧闹的，有很多的热点，但是我们需要记住的是长远的趋势。
趋势科技笔试题（很全很清楚）.doc
很全面的趋势科技的笔试题，大家可以从中学习
趋势科技笔试题（软件）
趋势科技笔试题 word文档的 需要的可以下载
数据结构与算法

33,008

社区成员

35,326

社区内容

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章