微软面试题——反转字符串

微软面试题——反转字符串

Posted on 2005-07-19 16:04 k_eckel 阅读(3541) 评论(20)  编辑 收藏

k_eckel：http://www./blog/k_eckel & http://k-eckel.cnblogs.com

这是网络流传的Microsoft的面试题目之一：“编写反转字符串的程序，要求优化速度、优化空间”。因为最近一直很多关注算法方面的实践和研究，因此对这个问题进行了一些思考，给出了5种实现方法（有两种解法相关性比较大）。

解法一：第一次看到这题目，想到最简单、最直觉的解法就是：遍历字符串，将第一个字符和最后一个交换，第二个和倒数第二个交换，依次循环，即可，于是有了第一个解法：

char* strrev1(const char* str) {        int len = strlen(str);        char* tmp = new char[len + 1];        strcpy(tmp,str);          for (int i = 0; i < len/2; ++i)        {               char c = tmp[i];         tmp[i] = tmp[len – i - 1];         tmp[len – i - 1] = c;        }          return tmp; }

这里是通过数组的下标方式访问字符串的字符，实际上用指针直接操作即可。解法二正是基于此，实现代码为：

char* strrev2(const char* str) {        char* tmp = new char[strlen(str) + 1];        strcpy(tmp,str);        char* ret = tmp;          char* p = tmp + strlen(str) - 1;          while (p > tmp)        {               char t = *tmp;               *tmp = *p;               *p = t;                 --p;               ++tmp;        }          return ret; }

显然上面的两个解法中没有考虑时间和空间的优化，一个典型的优化策略就是两个字符交换的算法优化，我们可以完全不使用任何外部变量即完成两个字符（或者整数）的交换，这也是一个很经典的面试题目。特别是一些嵌入式硬件相关编程中经常要考虑寄存器的使用，因此经常有不使用任何第三个寄存器即完成两个寄存器数据的交换的题目。一般有两个解法，对应这里的解法三和解法四。

解法三的实现代码为：

char* strrev3(const char* str) {        char* tmp = new char[strlen(str) + 1];        strcpy(tmp,str);        char* ret = tmp;          char* p = tmp + strlen(str) - 1;          while (p > tmp)        {               *p ^= *tmp;               *tmp ^= *p;                            *p ^= *tmp;                 --p;               ++tmp;        }          return ret; }

解法四的实现代码为：

char* strrev4(const char* str) {        char* tmp = new char[strlen(str) + 1];        strcpy(tmp,str);        char* ret = tmp;          char* p = tmp + strlen(str) - 1;          while (p > tmp)        {               *p = *p + *tmp;               *tmp = *p - *tmp;               *p = *p - *tmp;                 --p;               ++tmp;        }          return ret; }

实际上我们还可以通过递归的思想来解决这个问题，思想很简单：每次交换首尾两个字符，中间部分则又变为和原来字符串同样的问题，因此可以通过递归的思想来解决这个问题，对应解法五的实现代码为：

char* strrev5(/*const */char* str,int len) {        if (len <= 1)               return str;          char t = *str;        *str = *(str + len -1);        *(str + len -1) = t;          return (strrev5(str + 1,len - 2) - 1); }

以下给出一个测试程序：

int main(int argc,char* argv[]) {        char* str = "hello";        P(str);          char* str2 = strrev1(str);        P(str2);          char* str3 = strrev2(str2);        P(str3);          char* str4 = strrev3(str3);        P(str4);          char* str5 = strrev4(str4);        P(str5);          char* str6 = strrev5(str5,strlen(str5));        P(str6);               return 0; }

  你就可以看到字符串"hello"和"olleh"交替输出了。

  说明：1）这里解法中没有认真考虑输入字符串的合法性和特殊长度（如NULL、一个字符等）字符串的处理；2）前4个算法不改变输入字符串的值，解法五修改了输入字符串。

Feedback

# re: 微软面试题——反转字符串

2005-07-20 20:53 by goodluck

解法四还可以更快一点，因为你求了两次strlen(str)。

# re: 微软面试题——反转字符串

2005-07-21 09:26 by k_eckel

你说的对，strlen是很耗时间的，：）

# re: 微软面试题——反转字符串

2005-07-26 13:58 by Alpha

是不是可以考虑用堆栈呢


pop到另外的数组然后交换字符串指针

时间上肯定快

空间..............

# re: 微软面试题——反转字符串

2005-07-28 12:29 by dirtysalt

似乎调用递归很不划算，能用循环为什么不用循环？？？
strlen()函数本身就遍历了一遍，为什么输入字符串时就计算好长度
然后用长度作为参数传入?
可能还有好解法只有微软的人能想出来了，看来我进微软有问题。

# re: 微软面试题——反转字符串

2005-07-28 15:17 by k_eckel

是的，这里只是给出几种不同的想法实现。
BTW：用递归实现好像是有一个同学曾经问过这个问题，so。。。。。

# re: 微软面试题——反转字符串

2005-11-04 11:32 by 郭永平

实际上还可以这样：这样，时间复杂度为O(N)，空间复杂度为O(0)：
#include "stdio.h"
#include "string.h"
void strrev6(char* str)
{
    char *p1, *p2;
    bool bOdd = false;
    p1 = p2 = str;

    /* Find the middle element. */
    while(*p2 != ‘\0‘)
    {
        p2++;
        if (*p2 == ‘\0‘)
        {
            bOdd = true;
            break;
        }
        p2++;
        p1++;
    }

    /* Prepare to swap. */
    if (bOdd)
    {
        p2 = p1 + 1;
        p1--;
    }
    else
    {
        p2 = p1;
　　　p1--;
    }
    /* Begin to swap. */
    while(*p2 != ‘\0‘)
    {
*p1 ^= *p2;
*p2 ^= *p1;
*p1 ^= *p2;
        p1--;
        p2++;
    }
}

int main(void)
{
int i = 0, iLen;
char *tmp = NULL;
char str[] = "123456";
iLen = strlen(str);
strrev6(str);
tmp = str;
for (; *tmp != ‘\0‘; )
{
printf("%c", *tmp++);
}
return 0;
}