其实 字符串反转 在面试中会有各种各样。接下来的这种是比较金典的一种，昨天看了一篇文章，但是是 JAVA 实现的，于是就使用 OC 来操作了一遍，在实际的操作上是有很大区别的。
见题
把字符串“i am a student.”，翻转为“i ma a .tneduts”
一、常规方法
思路：
- 将字符串通过空格分割成数组
- 将数组中的元素再做反转
- 将反转后的数组变成字符串
代码如下：
/**
字符串反转
@note 如题: 把字符串“i am a student.”，翻转为“i ma a .tneduts”
@param string 原始字符串
@return 返回结果
*/
- (NSString*)reverseWithString:(NSString*)string {
// 有效性
if (!string || (string.length == 0)) {
return @"";
}
// 空格常量
static NSString* const spaceString = @" ";
// 将字符串分割成数组
NSArray* array = [string componentsSeparatedByString:spaceString];
// 中间变量
NSMutableArray* arrM = [NSMutableArray array];
// 转一转
for (int i=0; i<array.count; i++) {
NSString* str = [self reverseFromString:array[i]];
[arrM addObject:str];
}
return [arrM componentsJoinedByString:spaceString];
}
/**
字符串反转
@note 这个与 reverseWithString: 有所不同, 不用处理空格的情况
如题: 把字符串“student.”，翻转为“.tneduts”
*/
- (NSString*)reverseFromString:(NSString*)string {
// 有效性
if (!string || (string.length <= 1) ) {
return string;
}
// 字符
const char *str = [string UTF8String];
// 字符串长度
NSUInteger length = [string length];
// 动态分配空间
char *pReverse = (char*)malloc(length+1);
// 将 str copy 到 pReverse 中
strcpy(pReverse, str);
// 开始交换
[self reverseOptimizeFromSubString:pReverse startPosition:0 endPosition:(length-1)];
// 生成字符串
NSString *pstr = [NSString stringWithUTF8String:pReverse];
// 释放
free(pReverse);
// 返回
return pstr;
}
调用方式如下：
// 原始字符串
NSString* string = @"i am a student.";
// 反转后的字符串
NSString* reverseString = [self reverseWithString:string];
// 打印 i ma a .tneduts
NSLog(@"%@", reverseString);
这种方式确实是能实现，但是在过程中创建了很多的数组，这样在性能上肯定是不好的。下面有一个比较高级一点的方式。
二、比较高级一点的做法
第一种方式的做法，相对比较的消耗内存空间，下面的这种方式直接在一个字符串中做反转。具体代码如下：
/**
字符串反转 优化版本
@note 如题: 把字符串“i am a student.”，翻转为“i ma a .tneduts”
@param string 原始字符串
@return 返回结果
*/
- (NSString*)reverseOptimizeFromString:(NSString*)string {
// 有效性
if (!string || (string.length <= 1) ) {
return string;
}
// 字符
const char *chars = [string UTF8String];
// 字符串长度
NSUInteger length = [string length];
// 动态分配空间
char *pReverse = (char*)malloc(length+1);
// 将 str copy 到 pReverse 中
strcpy(pReverse, chars);
// 记录某个单词的开始位置
NSUInteger startPosition = 0;
// 空格字符
char spaceChar = ' ';
// 遍历 & 开始交换
for (NSUInteger i=0; i<length; i++) {
// 当前的字符
char c = pReverse[i];
if (c == spaceChar) {
NSLog(@"相等");
// 遇到空格了
// 要注意现在 i 的位置已经是在空格的位置了
// 所以需要交换的是 i 的前一个位置之前到 startPosition 的位置
// 开始交换
[self reverseOptimizeFromSubString:pReverse startPosition:startPosition endPosition:(i-1)];
// 每次都自动将 startPosition 的位置移动到最后, 就是当前的 i 的下一个
// 目的就是不希望起始位置咋空格的位置上
// 主要也是为了处理连续多个空格的情况
startPosition = i+1;
}
// 考虑最后一个单词
if (i == (length - 1)) {
// 开始交换
[self reverseOptimizeFromSubString:pReverse startPosition:startPosition endPosition:i];
}
}
// 生成字符串
NSString *pstr = [NSString stringWithUTF8String:pReverse];
// 释放
free(pReverse);
// 返回
return pstr;
}
调用方法：
// 原始字符串
NSString* string = @" i am a student. ";
// 反转后的字符串
NSString* reverseString = [self reverseOptimizeFromString:string];
// 打印 i ma a .tneduts
NSLog(@"%@", reverseString);
这种方式，仅仅是对字符串做一次遍历。更重要的是，这里可以是连续的空格。
三、公共方法
在上面的两种方式中，都用到如下的方法,代码如下：
/**
交换局部字符集
@description 比如 将 "1234" 换成 "1324" 那么 startPosition = 1, endPosition = 2
@param pReverse 即将要个交换的字符串
@param startPosition 起始位置
@param endPosition 结束位置
@return 返回 这个返回值可有可无, 因为 pReverse 是指针
*/
- (char *)reverseOptimizeFromSubString:(char *)pReverse startPosition:(NSUInteger)startPosition endPosition:(NSUInteger)endPosition {
// 只能是大于 0 的情况下 交换才有意义
if ((endPosition - startPosition) < 1) {
return pReverse;
}
// 开始交换
for(NSUInteger j=startPosition; j<(startPosition + ((endPosition+1)-startPosition)/2); j++) {
char cc = pReverse[j];
NSUInteger k = endPosition - (j - startPosition);
pReverse[j] = pReverse[k];
pReverse[k] = cc;
}
return pReverse;
}
具体可以直接看注释。具体的功能描述是：比如 将 "1234" 换成 "1324" 那么 startPosition = 1, endPosition = 2。如果换成 "4321" 那么 startPosition = 0, endPosition = 3
四、总结
弄完了才发现，所谓的常规方法看上去比较好理解，但是代码量相对来说有点多，其次是上面提到的，相对比较耗内存空间。
比较高级一点的做法，相对来说有点绕，但是看上去比较精炼。
我认为以上的方式就是很不错的了。
你说呢？
示例代码已经提交github CoderHG&Algorithm, 本节详情请见 HGTTController
