面试题 翻转一个字符串的单词顺序

Posted on | In |

面试题简述：
输入：给定一个字符串，用空格分隔各个单词。e.g. “This is a student”
输出：将单词顺序翻转。 “student a is This”

思路：

  1. 第一次面微软的时候，是做了一个栈，读到空格压栈，然后再pop出来加上空格。这个要注意的是最后一个单词的处理，因为最后一个单词没有空格。虽然只是一次遍历，但是要开辟栈空间来存储所有的单词，如果这个字符串很长的话就会占用过多的内存。
  2. 面Apple CoreOS的时候出了同样的题，最开始给出了上述的方法，上述方法的栈是通过c++来实现的，但是内核编程中是要通过纯C，并且连C库都不能使用。这个时候给出的一个方法是，建立一个单词指针数组，来保存每个单词的头指针。并且在原来的字符串上进行修改。
  3. 但是这仍然要开辟更多的内存空间来保存，后来被要求尝试完全不开辟新的内存空间的方法。
  4. 那么就是如下最正确的方法：两个指针做字符串全翻转。翻转之后，空格的位置是固定的，只需要再把单词自身翻转过来就可以了。同样要注意最后一个单词不是空格指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>

void reverse(char * str, int length){

    char * end = str + length -1;
    char * start = str;
    // char tmp;

    while(start < end){
        // tmp = *start;
        // *start = *end;
        // *end = tmp;

        *start ^= *end;
        *end ^= *start;
        *start ^= *end;

        start++;
        end--;
    }

}

int main(){

    char str[] = "This is, a student.";
    reverse(str, sizeof(str)-1);

    printf("%s\n", str);

    char* front = str;
    char* back = front;
    
    while(*back != '\0'){ //not reaching the end of the str
        if((*back < 'a' || *back > 'z') && (*back < 'A' || *back > 'Z')){
            reverse(front, back-front);
            printf("%s\n", str);
            front = back+1;
            back = front;
        } else{
            back++;
        }
    }
    reverse(front, back-front);
    printf("%s\n", str);

    return 0;
}