剑指Offer58:翻转字符串

末蓝、 2022-01-30 12:47 144阅读 0赞

因为之前好像在哪看过类似这样的题目，但是看到第二小问，第一时间脑海没有解题思路，于是记录一下。

题目一：翻转单词顺序  
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，为简单起见，标点符号和普通字母一样处理。例如输入字符串“I am a student.”  
**书上给的思路是**：第一步翻转句子中所有的字符。比如翻转 “I am a student.”中所有字符得到“.tneduts a ma I”,此时不但翻转了句子中字符的顺序，连单词内的字符顺序也被翻转了。第二步再翻转每个单词中字符的顺序，就得到了“student. a am I”.这正是符合题目的输出。  
**这种方法就是全部翻转会改变所有单词字符内的顺序与位置，但是再根据空格翻转，这样就会达到想要的效果，不过这样要根据空格的位置来重新翻转。**  
代码：

char* Reverse(char *pData)
    	{
    			if(pData == null)
    			return null;
    			char*pBegin = pData;
    			char*pEnd = pData;
    			while(*pEnd!='\0')
    			pEnd++;
    			pEnd--;
    		//翻转整个句子
    		Reverse(pBegin,pEnd);
    		//翻转句子中每个单词
    		pBegin = pEnd = pData;
    		while(*pBegin!='\0'){
    				if(*pBegin==' '){
    				pBegin++;
    				pEnd++:
    				}else if(*pEnd== ' ' || *pEnd=='\0'){
    				Reverse(pBegin,--pEnd);
    				pBegin==++pEnd;
    				}else{
    				pEnd++;
    				}
    			}
    			return pData;
    	}
    void Reverse(char* pBegin,char*pEnd){
    		if(pBegin == null || pEnd==null)
    		return ;
    		while(pBegin < pEnd)
    		{
    			char temp = *pBegin;
    			*pBegin = *pEnd;
    				*pEnd = temp;
    			pBegin++;pEnd++;
    	}
    }

题目二：  
左旋转字符串  
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能，比如，输入字符串“abcdefg”和数字2，该函数将返回左旋转两位得到的结果“cdefgab”.

根据题目一，比如"hello world",先全部翻转，再单个字符翻转得到" world hello",就类比得到我们想要的结果，那么，如果我们把 ab看一部分，其余剩下的看另外一部分，那么，先单独翻转，即ab->ba ,cdefg->gfedc.然后再一次全部翻转，那么ba就翻到后面去了。

代码

char* LeftRotateString(char* pStr,int n)
    	{
    			if(pStr!=null)
    			{
    				int nLength = strlen(pStr);
    				if(nLength>0 && n>0 && n<nLength){
    					char* pFirstStart = pStr;
    					char* pFirstEnd = pStr+n-1;
    					char* pSeStart = pStr+n;
    					char* pSend   = pStr+nLength-1;
    					//翻转字符串前面n个字符
    					Reverse(pFirstStart,pFirstEnd);
    					//翻转字符串后面的部分
    					Reverse(pSeStart ,pSend);
    					//翻转整个
    					Reverse(pFirstStart,pSend);
    					}
    				}
    				return pStr;
    		}

结论：这提示我们，字符串的翻转，这一方法实质就是不断的增加翻转次数和找到合理的位置进行翻转。