应届生求职招聘论坛

标题: 昨晚趋势科技的一道笔试题 [打印本页]

---

作者: zhufeiguanghui    时间: 2010-9-30 14:22
标题: 昨晚趋势科技的一道笔试题
求字符串最长不含重复字符的子串长度，请问大牛用什么算法比较好？  如abcbec，就返回3

---

作者: kkccww21    时间: 2010-9-30 14:58
public static int search(String text) {
                int max = 0, max1, max2;
                if (!hasSameChar(text)) {
                        return text_length();
                } else {
                        //取所有可能的子窜
                        String s1 = text_substring(0, text_length() - 1);
                        max1 = search(s1);
                        String s2 = text_substring(1, text_length());
                        max2 = search(s2);
                }
                max = max1 > max2 ? max1 : max2;
                return max;
        }
        
        private static boolean hasSameChar(String str){
                for (int i = 0; i < str_length(); i++) {
                        for (int j = i + 1; j < str_length(); j++) {
                                if (str_charAt(i) == str_charAt(j)) {
                                        return true;
                                }
                        }
                }
                return false;
        }

---

作者: wangben85    时间: 2010-9-30 15:15
int GetMaxSubStr(const unsigned char *str)
{
    int maxLen = 0; //初始化最大子串长度
    if (NULL == str) //入参判断
    {
        return 0;
    }
    int lastPos[256]; //代表着256个可能的字符（ASC2码），数组元素值代表字符串中字符的最后出现的位置
    for (int i = 0; i < 256; ++i)
    {
        lastPos[i] = -1;
    }   
    for (int pos = 0; str[pos] != '\0'; ++pos)
    {
        unsigned char c = str[pos]; //c的数值为这个字符的ASC2码
        if (lastPos[c] > -1) //此字符已经出现过
        {
            int len = pos - lastPos[c] + 1; //计算子串的长度
            if (len > maxLen) //与先前最大子串长度进行比较
            {
                maxLen = len;
            }
        }
        lastPos[c] = pos;
    }
    return maxLen;
}

---

作者: zhufeiguanghui    时间: 2010-9-30 15:48

int GetMaxSubStr(const unsigned char *str)
{
    int maxLen = 0; //初始化最大子串长度
    if (NUL ...
wangben85 发表于 2010-9-30 15:15

    你的程序明显是错误的，对于"2123123456"，应该输出6

---

作者: zhufeiguanghui    时间: 2010-9-30 15:51

int GetMaxSubStr(const unsigned char *str)
{
    int maxLen = 0; //初始化最大子串长度
    if (NUL ...
wangben85 发表于 2010-9-30 15:15

    你的程序明显是错的，"2123123456" 应该输出6

---

作者: zhufeiguanghui    时间: 2010-9-30 15:52
3楼的程序明显是错的

---

作者: qxfly    时间: 2010-9-30 18:00
显然DP。。。

---

作者: xiaocai416    时间: 2010-9-30 19:27
大家试试吧，欢迎指正。如果不是错的，时间复杂度为O（n）。

int search_max_substr(char *str)
{
    if(str == NULL)
        return 0;

    int maxlen = 0, len = 0;
    int range_begin = 0;//标记最长不含重复字符的子串可能出现范围的起始位置
    int pos[256];//用字符的ASCII码作为索引，标记该字符最近一次出现的位置
    for(int i = 0; i<256; i++)
        pos = -1;
    for(int j = 0; j<strlen(str); j++)
    {
        if( pos[str[j]] < range_begin )//如果该字符在当前搜索范围内没出现过
        {

            len++;
            if(len>maxlen)
                maxlen = len;//及时更新最大长度
        }
        else//该字符在在当前搜索范围内已出现过
        {
            len++;
            len -=(pos[str[j]] - range_begin+1);//修正子串长度(笔试时忘了加1了)
            range_begin = pos[str[j]]+1;//当前搜索范围起始位置更新到字符str[j]上次（此次为j）出现的位置的后一位，
            pos[str[j]] = j;

        }
        pos[str[j]] = j; //标记其位置
    }
    return maxlen;

}

---

作者: mmsz1020    时间: 2010-9-30 19:51
笔试都考什么啊？
谢谢~

---

作者: flydream81    时间: 2010-10-2 14:36
回复 8# xiaocai416


    恩  可以得出正确的结果， 除了第十行的一点笔误。

---

作者: 风流沙驼    时间: 2010-10-5 20:24


转自 http://_jo**_li/blog/archives/359

#include <iostream.h>
#include <string.h>

int search(char *text)
{
    int pos[256]; //用于记录字符最近一次出现的位置，使用ASC码做索引
    int maxL = 0;   //记录最大长度
    int start = 0;   //记录连续字符串的起始位置
    int end = strlen(text), i, tL;  //end为字符串text上界
    for (i=0; i<128; i++) pos = -1;  //为每个字符初始化位置
   
    for (i=0; i<end; i++)   //遍历字符串
    {
        int index = text;   //得到当前字符索引
        if (pos[index] >= start)    //当前字符在起始位置之后出现过，则出现重复
        {
            tL = i - start;         //计算长度
            if (tL > maxL) maxL = tL;  //若大于maxL，则记录
           
            start = pos[index] + 1;    //重置start位置，为重复的字符之后一个位置
        }
      
        pos[index] = i;              //记录当前字符位置
    }

    //末尾处理
    tL = i - start;
    if (tL > maxL) maxL = tL;

    return maxL;
}

void main()
{
    char a[]="xabc123eDd56xesdADBfjkg";

    cout<<search(a)<<endl;
}

---

作者: luweiseu    时间: 2010-10-11 11:09
回复 3# wangben85


int len = pos - lastPos[c] + 1; //计算子串的长度
definitely wrong

---

作者: luweiseu    时间: 2010-10-11 11:09
回复 3# wangben85


     int len = pos - lastPos[c] + 1; //计算子串的长度
错了

---

作者: luweiseu    时间: 2010-10-11 11:12
回复 8# xiaocai416


    太强了，崇拜:83)

---

作者: cicido    时间: 2010-10-15 22:06
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char *str;
int main()
{
int i=0,j=1,k,n,maxlen,besti,bestj,temp;
char *p=(char *)malloc(sizeof(char)*100);
maxlen=0;
str=(char *)malloc(sizeof(char)*100);
printf("请输入原字符串：\n");
scanf("%s",str);
n=strlen(str);
while(j<n&&i<j)
{
for(k=i;k<j;k++)
if(str[j]==str[k])
break;
if(k<j)
{
temp=j-i;
if(temp>maxlen)
{maxlen=temp;besti=i;bestj=j-1;}
i=k+1;j++;
}
else
{
temp=j-i+1;
if(temp>maxlen)
{maxlen=temp;besti=i;bestj=j;}
j++;
}
}
strncat(p,str+besti,maxlen);
printf("子串为：%s\n",p);
}


~                                                                                                                                                            
~                                                                                                                                                            
"maxsubstr.c" 38L, 567C                                                                                                                    14,1         全部

---

作者: ggset    时间: 2011-10-14 02:59
楼上给力

---

欢迎光临 应届生求职招聘论坛 (https://bbs.yingjiesheng.com/)

Powered by Discuz! X3.2