一，字符串轉化
將字符串轉換成整數：atoi
將整數轉換為字符串：itoa
浮點數與字符串的轉換
1）字符串轉化為整數
需要注意的地方：
考慮要缜密，注意是否為數字字符；
判斷是否為NULL
開頭的‘+’‘-’符號的判斷
[html]
#include "stdio.h"
#include "string.h"
#include "assert.h"
int isDigit(char c)
{
if(c>='0'&&c<='9')
return 1;
else
return 0;
}
int myatoi(const char *str)
{
assert(str!=NULL);
int count=strlen(str);
int result=0;
int sign=1;
if(str[0]=='-')
{
sign=-1;
}
else if(str[0]=='+')
{
sign=1;
}
else if(isDigit(str[0]))
{
result=str[0]-'0';
sign=1;
}
for(int i=1;i<count;++i)
{
assert(isDigit(str[i]));
result=result*10+(str[i]-'0');
}
return result;
}
int main()
{
printf("%d\n",myatoi("123"));
}
別看一個這麼簡單的問題，實際要考慮的問題很多。還是看一下glibc的實現吧
[html]
#include "stdio.h"
#include "string.h"
#include "assert.h"
#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）itoa 函數的實現
char *itoa( int value, char *string,int radix);
先看一看使用：
[html]
#include <stdlib.h>
#include <stdio.h>
int main(void)
{
int number = 12345;
char string[25];
itoa(number, string, 10); //按十進制轉換
printf("integer = %d string = %s\n", number, string);
itoa(number, string, 16); //按16進制轉換
printf("integer = %d string = %s\n", number, string);
return 0;
}
整形轉化為字符串（這裡默認十進制的轉換）
[html] view plaincopy
//整形轉成字符串函數實現
//題目不難，重點考察面試者對問題考慮的全面程度
#include <iostream>
using namespace std;
void itoa_mf(int num,char str[])
{
int sign = num;
int i = 0;
int j = 0;
char temp[100];
if(sign < 0)//如果是負數就去掉符號,將-1234轉成1234
{
num = -num;
}
do//轉成字符串，1234轉成"4321"
{
temp[i] = num % 10 + '0';
num /= 10;
i++;
}while(num > 0);
if(sign < 0)//如果是負數的話，加個符號在末尾，如："4321-"
{
temp[i++] = '-';
}
temp[i] = '\0';
i--;
//將temp數組中逆序輸入到str數組中
//將"4321-" ====> "-1234"
while(i >= 0)
{
str[j] = temp[i];
j++;
i--;
}
//字符串結束標識
str[j] = '\0';
}
int main()
{
int a = +123;
char s[100];
itoa_mf(a,s);
cout << s << endl;
}
二，找出字符串的最長子串，要求子串的所有字符相同
例如：str ="sssddddabcdef" 則輸出字串為：dddd
[html]
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
char* GetSubstring(char* strSource)
{
char* strSubstring; //用於保存得到的子串，大小在找到最大子串後再確定，作為返回值
int nLen; //源字符串長度
int nCurPos; //當前統計字符串的頭指針位置(相對於原字符串第一個字符的位置)
int nCurCount; //當前統計字符串的長度（有相同字符組成的子字符串）
int nPos; //當前最長的子串的頭指針位置
int nCount; //當前最長的子串的長度
nLen = strlen(strSource);
//初始化變量
nCount = 1;
nPos = 0;
nCurCount = 1;
nCurPos = 0;
//遍歷整個字符串
for(int i = 1; i < nLen; i++)
{
if(strSource[i] == strSource[nCurPos])//如果當前字符與子串的字符相同，子串長度增1
nCurCount++;
else //如果不相同，開始統計新的子串
{
if(nCurCount > nCount)//如果當前子串比原先最長的子串長，把當前子串信息(起始位置 + 長度)保留下來
{
nCount = nCurCount;
nPos = nCurPos;
}
//長度復值為1，新串的開始位置為i
nCurCount = 1;
nCurPos = i;
}
}
//為返回的子串分配空間(長度為nCount,由於要包括字符串結束符\0,故大小要加1)
strSubstring = (char*)malloc(nCount + 1);
//復制子串(用其他函數也可以)
for(int i = 0; i < nCount; i++)
strSubstring[i] = strSource[nPos + i];
strSubstring[nCount] = '\0';
return strSubstring;
}
int main()
{
//輸入一個字符串strSource
char *strSource="absceeeecd";
char* strSubstring = GetSubstring(strSource);
printf("最長子串為:%s\n長度為：%d",strSubstring,strlen(strSubstring));
//釋放strSubstring
free(strSubstring);
}
三，求兩個字符串的最大公共子字符串
算法時間復雜度：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);
}
十四，去掉中文中的英文字符
主要根據字節的第一位進行判斷。
十五，求一個字符串中連續出現次數最多的子串
