摘录于下, 来源: http://rjwyr.blog.163.com/blog/static/112986400201153061911864/
字符串操作
#include <iostream> #include <sstream> #include <limits> #include <vector> #include <string> using namespace std;
/*\
1.翻转句子中的单词
题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。
句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。
例如输入“I am a student.”,则输出“student. a am I”。
使用:reverse_iterator
*/
*/ void reverseWord() { vector<string> vec; /* string str,word; getline(cin,str); istringstream in_str(str); while(in_str>>word)vec.push_back(word); */ string word; while(cin>>word) vec.push_back(word); vector<string>::reverse_iterator it;/************************/ for(it=vec.rbegin();it!=vec.rend();it++) cout<<*it<<" "; cout<<endl; } /*
/*
2.第一个只出现一次的字符
例如abcaccd 输出b
解题思路:利用hash思想,字符一共256个,则建立一个大小为256的数字
*/
int getFirstNoRepeatCh() { char str[256]; int s[256],i; cout<<"please input the word:"; cin>>str; for(i=0;i<256;i++) s[i]=0; for(i=0;str[i]!='\0';i++) s[str[i]]++; for(i=0;str[i]!='\0';i++) { if(s[str[i]]==1) { cout<<str[i]<<endl; return i; } } return 0; }
/*
3.把字符串转化为数字
题目不难,但是考察编程习惯,比如判断正负号,是否为数字字符,是否越界等
函数返回值指示是否正确转化,sum代表转化后的值
*/
bool converseToNumber(const char *pStr, int &sum) { const char *pChar=pStr; int flag=1; bool isValid=true; __int64 s=0; if(pStr==NULL) return false; if(*pChar=='-') { flag=-1; pChar++; } else { if(*pChar=='+') pChar++; } while(*pChar != '\0') { if( *pChar <='9' && *pChar>='0') { s=10*s+ (*pChar -'0'); //overflow if(s > std::numeric_limits <int>::max()) { isValid=false; s=0; break; } } //the char is not a digit,input error else { isValid=false; s=0; break; } } if(*pChar == '\0') { if(flag<0) s=0-s; sum=static_cast<int>(s); } return isValid; }
/*
4.左旋字符串
定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。
请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。
*/
/*
思路1,将字符串看成两部分XY,目标是YX,我们利用将X Y 分别翻转来得到结果 (XT YT)T=YX.
*/
//reverse the word void reverse(char *pStart,char *pEnd) { char ch; if(pStart!=NULL && pEnd!=NULL) { while(pStart<pEnd) { ch=*pStart; *pStart=*pEnd; *pEnd=ch; pStart++; pEnd--; } } } char * leftConverseStr(char *pStr,int m) { if(pStr!=NULL) { int len=static_cast<int>(strlen(pStr)); if(len>0 && m<len && m>0) { char *pFirstS=pStr; char *pFirstE=pStr+m-1; char *pSecondS=pStr+m; char *pSecondE=pStr+len-1; reverse(pFirstS,pFirstE); reverse(pSecondS,pSecondE); reverse(pFirstS,pSecondE); } } return pStr; }
/*
5.在字符串中删除特定的字符.
输入They are students.”和”aeiou”,则删除之后的第一个字符串变成”Thy r stdnts.”。
遍历源字符串,对每个字符在第二个字符串中查找是否存在,存在则删除。首先我们对第一部分进行优化,由于删除一个字符时,后面的都要
往前移,这样删除一个字符需要O(n),太耗时了,一个改进的做法是维护两个指针 pFast pSlow,当当前字符是需要删除的字符时,pFast ++
,是不需要删除的字符时,两个都++,这样我们最后得到了pslow就是结果,对于查找部分,利用hash,时间复杂度O(1).
*/
char * delChar(char *pSource,char *pDel) { char hashT[256]; memset(hashT,0,sizeof(hashT)); char *pChar=pDel; while(*pChar!='\0') { hashT[*pChar]=1; pChar++; } char *pFast=pSource,*pSlow=pSource; while(*pFast != '\0') { if(hashT[*pFast] != 1) { *pSlow=*pFast; pSlow++; } pFast++; } *pSlow='\0'; return pSource; }
/*
6.对称子字符串的最大长度
题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出4。
解题思路:判断一个字符串是否对称相信都会做,从两边向中间开始逐一判断,如果采用这个思路,我们需要枚举出所有可能的子串
即n^2个,然后对每一个子串判断是否对称,这样时间复杂度O(n^3).因为存在重复判断,所以时间负责度会这么高,我们换一种思路
从中间像两端判断,这样可以降低复杂度,为O(n^2)
*/
int getLongestSymmetricalLength(char *pStr) { int len=0; if(pStr!=NULL) { int tmp=0; len=1; char *pChar=pStr; while(*pChar != '\0') { //odd length char *pLeft=pChar-1; char *pRight=pChar+1; while(pLeft >= pStr && *pRight!= '\0' && (*pLeft==*pRight)) { pLeft--; pRight++; } tmp=pRight-pLeft-1; if(tmp>len) len=tmp; pLeft=pChar; pRight=pChar+1; while(pLeft >=pStr && *pRight!='\0' && (*pLeft==*pRight)) { pLeft--; pRight++; } //even length tmp=pRight-pLeft-1; if(tmp>len) len=tmp; pChar++; } } return len; } int main() { // reverseWord(); // getFirstNoRepeatCh(); /* cout<<"please input the converseStr :"; char str[100]; int sum=0; cin>>str; if(converseToNumber(str,sum)) cout<<sum<<endl; else cout<<"invalid input,converse error"<<endl; */ /* cout<<"please input the leftConverseStr :"; char str[100]; int m=5; cin>>str; char * re=leftConverseStr(str,3); cout<<re<<endl; */ /* cout<<"please input the source and del string :"; char source[100],del[100]; // cin>>source>>del; cin.getline(source,100,'\n'); cin.getline(del,100,'\n'); char *re=delChar(source,del); cout<<re<<endl; */ char str[100]; cout<<"please input the string :"; cin>>str; int re=getLongestSymmetricalLength(str); cout<<re<<endl; return 0; }