分类： C/C++
2009-10-07 12:19:38
面试题目 字符串专题
1.将字符串转换成整数，将整数转换为字符串，浮点数与字符串的转换(atoi itoa)
int atoi(const char *str){
int res = 0;
int sign;
assert(str != NULL);
if(str[0] == '-') sign = -1;
else if(str[0] == '+') sign =1;
else if(isdigit(str[0])){sign = 1;res=str[0] - '0';}
for(int i = 1 ; str[i] != '\0' ; i++){
assert(isdigit(str[i]));
res = res*10 + sign*(str[i] - '0');
}
return res;
}
别看一个这么简单的问题，实际要考虑的问题很多。还是看一下glibc的实现吧
#define LONG_MAX 2147483647L
#define LONG_MIN (-2147483647L-1L)
long int _strtol_internal (const char *nptr, char **endptr, int base, int group)
{
//注意要使用unsigned long否则会发生溢出，因为long int最多2147483647L ，无法表示2147483648L
unsigned long int result = 0;
long int sign = 1;
//考虑前导空格
while (*nptr == ' ' || *nptr == '\t')
++nptr;
//考虑带有正负号
if (*nptr == '-')
{
sign = -1;
++nptr;
}
else if (*nptr == '+')
++nptr;
//如果出现非法输入
if (*nptr < '0' || *nptr > '9')
{
if (endptr != NULL)
*endptr = (char *) nptr;
return 0L;
}
//考虑进制
assert (base == 0);
base = 10;
if (*nptr == '0')
{
if (nptr[1] == 'x' || nptr[1] == 'X')
{
base = 16;
nptr += 2;
}
else
base = 8;
}
//防止非法字符
while (*nptr >= '0' && *nptr <= '9')
{
unsigned long int digval = *nptr - '0';
//防止溢出，如果溢出了long的表示范围，则置errno
if (result > LONG_MAX / 10 || (sign > 0 ? result == LONG_MAX / 10 && digval > LONG_MAX % 10 :
(result == ((unsigned long int) LONG_MAX + 1) / 10 && digval > ((unsigned long int) LONG_MAX + 1) % 10)))
{
errno = ERANGE;
return sign > 0 ? LONG_MAX : LONG_MIN;
}
result *= base;
result += digval;
++nptr;
}
return (long int) result * sign;
}
atoi函数就是这个函数讲第二个参数置为NULL，第三个参数置为10。不知道你注意到了那些空格，越界之类的判断没有。我同学说他写出来的代码最后就被要求加上了这些东西，最后还因此被卡掉了（
说是考虑不够慎密，汗）。
2.找出字符串的最长子串，要求子串的所有字符相同
int find_sub(char *str,char **begin,char **end){
unsigned int len = 1;
unsigned int max_len = 0;
char *t_begin = str;
char *t_end = str;
if(*str == '\0')return 0;
//注意起始条件，与循环都要保证循环不变形，可以这样考虑第一次循环前执行的，与while的其他循环是否有不同
//比如在while里，其他循环执行都有个str++,而第一次是否需要加上这个str++呢？
str++;
while(*str){
if(*str == *t_end){ len++;t_end = str;}
else{
if(len > max_len){
max_len = len;
*begin = t_begin;
*end = t_end;
}
len = 1;
t_begin = str;
t_end = str;
}
str++;
}
return max_len;
}
注意检查逻辑错误，边界条件。
3.求两个字符串的最大公共子字符串
dp，设两个字符串为A B定义子问题f[i][j]表示子串A[0...i] B[0...j]以i，j为结尾的最大公关子串长度。
f[i][j] = 0 if(A[i] != B[j])
= f[i-1][j-1]+1 else
这样可以找到复杂度为O(n^2)的算法
4.字符串查找并记录出现次数(普通与kmp)(观察strstr实现)，替代
看下标准实现，实际上是还是用的force-brute方法，并没有使用kmp这类的算法。看下lynx里的strstr.c
/* Written by Philippe De Muyter <>. */
/*
* NAME
*
* strstr -- locate first occurrence of a substring
*
* SYNOPSIS
*
* char *strstr (char *s1, char *s2)
*
* DESCRIPTION
*
* Locates the first occurrence in the string pointed to by S1 of the string
* pointed to by S2. Returns a pointer to the substring found, or a NULL
* pointer if not found. If S2 points to a string with zero length, the
* function returns S1.
*
* BUGS
*
*/
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;
}
5.解析一个字符串，对字符串中重复出现的字符，只在第一次出现时保留。如：abdabbefgf -> abdefg。
根据字符集，建立一个flag数组用来表示是否出现过。
6.给出一个函数来输出一个字符串的所有排列
采用next_permutation的算法思想，首先进行一个字符重排序找到按字典序最小的那个字符序列，以它为开端逐步生成所有排列。
7.翻转字符串
这个比较简单。
8.从一个字符串中找出第一个不重复字符
这个也比较简单，类似于5的方法。
9.去除字符串中相邻两个字符的重复
这个应该等价于题目5
10.判断字符串是否含有回文字符子串
枚举字符串的每个位置，作为回文串的中间位置(分偶数奇数两种情况)，如果找到或者找不到都会立即停止，所以总的复杂度不超过O(n)
11.求最长回文子串
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只需判断是否存在，这需要找到最长的那个。
当然这个问题还有更快的算法：和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算法，不过我现在还没把握能不能简单的把它说清楚，姑且认为可以吧。
------------------------------------------------------引用结束------------------------------------------------------------------------
12. 字符串移位包含的问题 给定两个字符串S1与S2，要求判定S2是否能够被通过s1作循环移位得到的字符串包含,例如，给定s1=AABCD与S2=CDAA，返回true;给定s1＝ABCD 与 s2=ACBD，返回false.
直接枚举匹配或者比较s2能否匹配s1s1,以第一个为例也就是说比较AABCDAABCD和CDAA。
13.strlen strcpy(注意重叠)
看glibc的实现，可以发现strlen它进行了加速处理，每次前进多个字节，将字符串转化为unsigned long类型，然后利用位运算判断该long型数据是否含有0字节。
strcpy的实现：
# define BOUNDS_VIOLATED (__builtin_trap (), 0)
# define CHECK_BOUNDS_LOW(ARG) \
(((__ptrvalue (ARG) < __ptrlow (ARG)) && BOUNDS_VIOLATED), \
__ptrvalue (ARG))
# define CHECK_BOUNDS_HIGH(ARG) \
(((__ptrvalue (ARG) > __ptrhigh (ARG)) && BOUNDS_VIOLATED), __ptrvalue (ARG))
char *
strcpy (
char *dest,
const char *src
)
{
reg_char c;
char *__unbounded s = (char *__unbounded) CHECK_BOUNDS_LOW (src);
const ptrdiff_t off = CHECK_BOUNDS_LOW (dest) - s - 1;
size_t n;
do
{
c = *s++;
s[off] = c;
}
while (c != '\0');
n = s - src;
(void) CHECK_BOUNDS_HIGH (src + n);
(void) CHECK_BOUNDS_HIGH (dest + n);
return dest;
}
上面这个比较复杂，再看FreeBsd的实现
sys/libkern/strcpy.c
35 char *
36 strcpy(char * __restrict to, const char * __restrict from)
37 {
38 char *save = to;39
40 for (; (*to = *from) != 0; ++from, ++to);
41 return(save);
42 }
14.去掉中文中的英文字符
主要根据字节的第一位进行判断。
15.求一个字符串中连续出现次数最多的子串
http://hi.baidu.com/charles_zhang/blog/item/147a948227390d98f603a6ca.html
