题解 | #单词倒排#

一种思路:时间复杂度,空间复杂度

#include 
#include 
#include 
//逆置相应段的元素
void reverse(char* str, int left, int right) {
    while (left < right) {
        char tmp = str[left];
        str[left] = str[right];
        str[right] = tmp;
        ++left;
        --right;
    }
}
int main() {
    char str[10000];
    gets(str);
    //数组长度
    int len = strlen(str);
    //清理多余非字母字符
    int slow = 0, fast = 0;
    //flag默认为1，表示空格已经被记录，直到出现新单词才变0，表示需要一个新空格
    int flag = 1;
    while (fast < len) {
        if (isalpha(str[fast])) {
            str[slow++] = str[fast];
            flag = 0;
        }
        else if (flag == 0) {
            str[slow++] = ' ';
            flag = 1;
        }
        ++fast;
    }
    str[slow] = '\0';
    //倒序字符串
    int cnt = strlen(str);
    reverse(str, 0, cnt-1);
    //逐个的单个的逆置单词
    int left = 0;
    int right = 0;
    flag = 1;
    //记录每个单词的开始下标和结束下标，再逆置两个下标之间的元素
    while (right <= cnt) {
        if (isalpha(str[right])) {
            ++right;
            flag = 0;
        }
        else {
            reverse(str, left, right - 1);
            ++right;
            left = right;
        }
    }
    puts(str);
    return 0;
}