字符串操作

r囧r小猫 2022-05-30 04:06 248阅读 0赞

[http://rjwyr.blog.163.com/blog/static/112986400201153061911864/][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”。

\*/

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;

![microblog.png_1][]转发至微博

[http_rjwyr.blog.163.com_blog_static_112986400201153061911864]: http://rjwyr.blog.163.com/blog/static/112986400201153061911864/
[microblog.png_1]: /images/20220530/79f9f717b76743a7ba570e69a1226dd5.png

字符串操作

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关字符串操作

相关字符串操作

相关字符串操作

相关字符串操作

相关字符串操作

相关字符串操作

相关字符串操作

相关字符串操作

相关字符串-操作

相关字符串操作