c++ - 如何在不使用内置函数的情况下反转句子中的单词？

Question

这是面试题:

How to convert Dogs like cats to cats like Dogs ?

我的代码显示:cats like cats。我在哪里犯了错误？

#include <iostream>
using namespace std;

int main()
{
    char sentence[] = ("dogs like cats");
    cout << sentence << endl;

    int len = 0;

    for (int i = 0; sentence[i] != '\0'; i++)
    {
        len++;
    }
    cout << len << endl;

    char reverse[len];
    int k = 0;

    for (int j = len - 1; j >= 0; j--)
    {
        reverse[k] = sentence[j];
        k++;
    }

    cout << reverse << endl;

    int words = 0;
    char str[len];

    for (int l = 0; reverse[l] != '\0'; l++)
    {
        if (reverse[l] == ' ' || reverse[l] == '\0') // not sure about this part
        {
            for (int m = l; m >= 0; m--)
            {
                str[words] = reverse[m];
                words++;
            }
        }
    }

    cout << str;

    return 0;
}

我知道你可以使用指针、堆栈、 vector ...但是面试官对此不感兴趣!

Answer 1

这是您的示例代码的固定版本:

• 您的主要问题是，每次您找到 ' ' 或 '\0' 时，您都会从头到尾复制反向字符串的字节。 循环 5 中的示例，您从索引 0-5 (stac) 以相反的顺序从 reverse 复制到 str，但在 loop 10 中，您从索引 0-10 (stac ekil) 从 reverse 反向复制到 str顺序，直到这里你已经打印了结果字符串('cats like cats')，并且在 loop 15 中也是如此，所有这些都增加了 str 的索引，在您编写的最后一个循环通过了 str 的有效内存的末尾(因此未打印为输出)。
• 您需要跟踪最后一个单词何时结束反转以仅反转实际单词，而不是从开头到实际索引的字符串。
• 您不想计算单词反转中的特殊字符(' ' 和 '\0')，您会以 cats like\0dogs
结尾

提供修改后的示例代码:

#include <iostream>
using namespace std;

int main() {
    char sentence[] = ("dogs like cats");
    cout << sentence << endl;

    int len = 0;

    for (int i = 0; sentence[i] != '\0'; i++) {
        len++;
    }
    cout << len << endl;

    char reverse[len];
    int k = 0;

    for (int j = len - 1; j >= 0; j--) {
        reverse[k] = sentence[j];
        k++;
    }

    cout << reverse << endl;

    int words = 0;
    char str[len];

    // change here added last_l to track the end of the last word reversed, moved
    // the check of the end condition to the end of loop body for handling the \0
    // case
    for (int l = 0, last_l = 0; ; l++) {
        if (reverse[l] == ' ' || reverse[l] == '\0')
        {
            for (int m = l - 1; m >= last_l; m--) { // change here, using last_t to
                str[words] = reverse[m];            // only reverse the last word
                words++;                            // without the split character
            }
            last_l = l + 1;                         // update the end of the last
                                                    // word reversed
            str[words] = reverse[l];                // copy the split character
            words++;
        }
        if (reverse[l] == '\0')                     // break the loop
            break;
    }

    cout << str << endl;

    return 0;
}

一些代码，在使用语言最简单的特性的限制下编写。

#include <iostream>

// reverse any block of text.
void reverse(char* left, char* right) {
    while (left < right) {
        char tmp = *left;
        *left = *right;
        *right = tmp;

        left++;
        right--;
    }
}

int main() {
    char sentence[] = "dogs like cats";
    std::cout << sentence << std::endl;

    // The same length calculation as sample code.
    int len = 0;
    for (int i = 0; sentence[i] != '\0'; i++) {
        len++;
    }
    std::cout << len << std::endl;

    // reverse all the text (ex: 'stac ekil sgod')
    reverse(sentence, sentence + len - 1);

    // reverse word by word.
    char* end = sentence;
    char* begin = sentence;
    while (end < sentence + len) {
        if (*end != ' ')
            end++;

        if (end == sentence + len || *end == ' ') {
            reverse(begin, end - 1);
            begin = end + 1;
            end = begin;
        }
    }

    std::cout << sentence << std::endl;

    return 0;
}