程序员面试100题(算法)之翻转句子中单词的顺序
方法一：
// 程序员面试100题(算法)之翻转句子中单词的顺序#include "stdafx.h" #include<iostream> using namespace std; void reverse(char* begin, char* end) { if ((begin == NULL) || (end == NULL)) return ;char temp; while (begin < end) { temp = *begin;*begin = *end;*end = temp; ++begin; --end; } } char *reverseSentence(char *pData) { if(NULL == pData) return NULL; char *begin = pData; char *end = pData; while(*end != '\0') { end++; } end--; //reverse the overall sentence reverse(begin, end); //reverse each word in the reversed sentence begin = pData; end = pData; while(*begin != '\0') { if(*begin == ' ') { begin++; end++; continue; } if(*end == ' ' || *end == '\0') { end--; reverse(begin, end); end++; begin = end; } else { end++; } } return pData; } int _tmain(int argc, _TCHAR* argv[]) { char sentence[] = "I am in China today!! I am very happy!!!!"; char *newSentence = NULL; newSentence = reverseSentence(sentence); cout << newSentence << endl; return 0; }
方法二：（用异或实现反转）
#include "stdafx.h"#include <iostream>#include <cstring> using namespace std; void Reverse(char* b, char* e) { if ((b == NULL) || (e == NULL)) return ; while (b < e) { *b ^= *e; *e ^= *b; *b ^= *e; ++b; --e; } } void WordReverse(char* s) { if (s == NULL) return; Reverse(s, s + strlen(s) - 1); char* b = s; char* e = s; while(*e) { if (*e == ' ') { Reverse(b, e - 1); ++e; b = e; } else ++e; } Reverse(b, e - 1); } int _tmain(int argc, _TCHAR* argv[]){ char my[] = "I am a student"; Reverse(my, my + strlen(my) - 1); cout << my << endl; char my2[] = "I am a student "; WordReverse(my2); cout << my2 << endl; return 0;}
附：
1、递归逆置字符串
char *recurReverse(char* s, int left, int right){if(left >= right)return s;char c = s[left];s[left] = s[right];s[right] = c;recurReverse(s, left + 1, right - 1);}2、普通的字符串逆置，申请新的空间，然后逆序复制过去。
char *commonReverse(char* s) { if(NULL == s){return NULL;}char *end = s;while(*end != '\0'){end++;}end--;char *newStr = (char*)malloc(sizeof(char) * (strlen(s) + 1));char *str = newStr;while(end != s){*newStr = *end;end--;newStr++;}*newStr = *end;*(++newStr) = '\0';return str;}