A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

三,求两个字符串的最大公共子字符串
        算法时间复杂度:O(n^2)
        思想:两个字符串先从第一个字串的第一个字符开始,依次与第二个字串的各个位置字串比较字串
                    需要记录下最长公共子串在str1中的位置和子串长度
[html]
#include<iostream>
#include<cstring>
#include<cassert>
using namespace std;
void findMaxSubstr(const char * str1 , const char * str2 , char * maxSubstr)
{
    assert((str1!=NULL)&&(str2!=NULL));
    assert(maxSubstr!=NULL);
    int maxPos=-1;
    int maxLen=0;
    int k;  
    for(int i=0; i<strlen(str1); i++)
    {
        for(int j=0; j<strlen(str2); j++)
        {
            if(str1[i]==str2[j])
            {
                for(k=1; (str1[i+k]==str2[j+k])&&(str1[i+k]!='\0'); k++)
                             ;
                    if(k>maxLen)
                    {
                        maxPos=i;
                        maxLen=k;
                    }
            }
        }
    }
    if(maxPos==-1)
    {
        maxSubstr[0]='\0';
    }
    else
    {
        memcpy(maxSubstr , str1+maxPos , maxLen);
        maxSubstr[maxLen]='\0';
    }
}
int main()
{
    char substr[20];
    findMaxSubstr("tianshuai" , "mynameistianshuai" , substr);
    cout<<substr<<endl;
    return 0;
}


四,字符串查找并记录出现次数(普通与kmp)(观察strstr实现),替代
          函数原型:extern char *strstr(char *str1, char *str2);
   功能:找出str2字符串在str1字符串中第一次出现的位置(不包括str2的串结束符)
          使用:printf("%s",strstr("tianshuai","shuai"));
                      输出:shuai
             实现:
[html]
#include "stdio.h"
char *strstr(char *buf, char *sub)
{
    register char *bp;
    register char *sp;

    if (!*sub)
        return buf;
    while (*buf)
   {
        bp = buf;
        sp = sub;
        do  
        {
            if (!*sp)
                return buf;
        } while (*bp++ == *sp++);
        buf += 1;//从下一个位置查找  
    }
    return 0;
}
int main()
{
    printf("%s",strstr("tianshuai","tian"));  
     
}  
求子串的个数只需要略微更改一下就可以
[html]
#include "stdio.h"
  
int  strstr(char *buf, char *sub)
{
    register char *bp;
    register char *sp;
     
    int count=0;
    int pos=0;  
      
    if (!*sub)
        return 0;
    while (*buf)
   {
        bp = buf;
        sp = sub;
        pos=0;  
        do  
        {
            pos++;  
            if (!*sp)
            {
                count++;  
            }  
                //return buf;
        } while (*bp++ == *sp++);
         
        buf += pos;//从下一个位置查找  
    }
    return count;
}
int main()
{
    printf("%d",strstr("tianshuai,tianshuai,tianshui","tian"));  
     
}  


五,解析一个字符串,对字符串中重复出现的字符,只在第一次出现时保留,就是去除重复的字符。
         如:abdabbefgf -> abdefg。
         根据字符集,建立一个flag数组用来表示是否出现过。
六,给出一个函数来输出一个字符串的所有排列
        字典序生成算法问题:字典序
        采用next_permutation的算法思想,首先进行一个字符重排序找到按字典序最小的那个字符序列,以它为开端逐步生成所有排列。
七,翻转字符串
         参考例子
八,从一个字符串中找出第一个不重复字符
         这个也比较简单,类似于5的方法。
九,去除字符串中相邻两个字符的重复
         这个应该等价于题目5
十,判断字符串是否含有回文字符子串
        枚举字符串的每个位置,作为回文串的中间位置(分偶数奇数两种情况),如果找到或者找不到都会立即停止,所以总的复杂度不超过O(n)
十一,求最长回文子串
         dp
                f[i][j] = f[i+1][j-1]
               s[i] == s[j]
         false s[i] != s[j]
        当然这里有一个小小的限定,f[i][j]表示以i,j为首尾的回文串能否构成。然后再找到一个最长的就可以算法,复杂度O(n^2)。实际上这个问题只要枚举回文串的中间位置就可以了,这样实际上就跟10一样了。不过10只需判断是否存在,这需要找到最长的那个。
当然这个问题还有更快的算法:http://richardxx.yo2.cn/articles/kmp和extend-kmp算法.html
------------------------------------------------------引用开始------------------------------------------------------------------------
             KMP的另外一个研究方向是Extend KMP(以下简称EK),它是说求得T与所有的S(i)的最长公共前缀(LCP),当然,要控制复杂度在线性以内。
             EK我第一次听说是07年baidu校园招聘的笔试题中,它当时的题目是求最长回文子串,当然这是一个耳熟能详,路人皆知可以用Suffix Array很好解决的问题。事后听一个同学说他写了三个算法:Suffix Array,Suffix Tree和EK,当时就不明白EK是什么东西,但又没当面问他,于是这个东西就搁置了很久。知道后来北大的月赛一道题说可以用EK来做,我才终于从03年林希德的文章中开始认识到它,就像KMP一样,这个算法也一下就吸引了我。
           设Q(i)表示T和S(i )的后缀的LCP,P(i)表示T和T(i)的后缀的LCP,那么和KMP一样,我们试图用P来求得Q,而P可以用自匹配求得,并且和求Q的过程相似。
           我以求P为例简要说明一下。P(2)就直接匹配即可,从i = 3开始,如下:
                      设k < i,E(k) = k + P(k) - 1,且对所有j < i,有E(k) >= E(j)。
                      那么,当E(k) >= i时,便可以推知T(i) = T( i - k + 1 ),于是如果P( i - k + 1 ) < E(k) - i + 1,那么P(i) = P( i - k + 1),否则P(i) >= P( i - k + 1 ),从E(k)开始向后匹配到E(i),有P(i) = E(i) - i + 1,并且更新 k = i;
                      还有就是E(k) < i,肯定有E(k) = i - 1,不过这个不重要,重要的是直接从i开始做暴力匹配即可得到E(i),则P(i) = E(i) - i + 1,更新k = i。
                      希望我把EK说清楚了,不过这种东西还是自己推导一下有意思,而且记忆周期更长。
           最后来罗列下题目。KMP的经典题目是POJ 2185,是要找最小覆盖矩形,如果你认为懂KMP了就去尝试它。EK的经典题是POJ 3376,有一定挑战;当然还有就是上面说的最长回文子串,提醒下用分治+EK来做是其中一种方法。
嗯,下次打算说下Suffix Array,主要是它那个传说中的线性DC3算法,不过我现在还没把握能不能简单的把它说清楚,姑且认为可以吧。
------------------------------------------------------引用结束------------------------------------------------------------------------
十二,字符串移位包含的问题
            题目:给定两个字符串S1与S2,要求判定S2是否能够被通过s1作循环移位得到的字符串包含,例如,给定s1=AABCD与S2=CDAA,返回true;给定s1=ABCD 与 s2=ACBD,返回false.
            直接枚举匹配或者比较s2能否匹配s1s1,以第一个为例也就是说比较AABCDAABCD和CDAA。
十三,strlen strcpy(注意重叠)
[html]
#include "stdio.h"
#include "assert.h"
  
char *<span>strcpy</span> (char *dest,const char *src)
{
    assert(src!=NULL);  
    char *temp=dest;
    while((*dest++=*src++)!='\0')
            ;
    return dest;
}

int main()
{
    char *dest;
    char *src="tianshuai";
    <span>strcpy</span>(dest,src);
    printf("%s",dest);  
}  

上面这个比较复杂,再看FreeBsd的实现

char *strcpy(char * __restrict to, const char * __restrict from)
{
        char *save = to;
        for (; (*to = *from) != 0; ++from, ++to);
        return(save);
}
十四,去掉中文中的英文字符
            主要根据字节的第一位进行判断。
十五,求一个字符串中连续出现次数最多的子串

6 个回复

倒序浏览
我也是在最大字母串那没写出来就交了测试题,楼主分享的太好了。赞~
回复 使用道具 举报
ch8898163 发表于 2014-9-25 08:53
我也是在最大字母串那没写出来就交了测试题,楼主分享的太好了。赞~

你也中枪了吗?:lol
回复 使用道具 举报
学习一下~~~
回复 使用道具 举报
太长了  懵了
回复 使用道具 举报
这些都是iOS入学流程最后的面试题吗?这么叼?
回复 使用道具 举报
是 ios的面试题吗
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马