0

这是面试问题:

如何转换Dogs like catscats 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;
}

我知道你可以使用指针、堆栈、向量来做到这一点……但面试官对此并不感兴趣!

4

5 回答 5

4

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

  • 您的主要问题是,每次您找到和' '/或'\0'您将反向字符串的字节从开头复制到该点。示例loop 5从索引 0-5 ( stac) from reversetostr以相反的顺序复制,但在loop 10您从索引 0-10 ( stac ekil) from reversetostr以相反的顺序复制,直到这里您已经打印了结果字符串('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;
}
于 2014-08-13T05:49:48.077 回答
2

分解你的算法。首先,您找到字符串的长度,不包括空字符终止符。这是正确的,尽管可以简化。

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

这可以很容易地写成:

size_t len = 0;
while (sentence[len])
    ++len;

接下来,您反转整个字符串,但第一个缺陷表面。您在此处声明的 VLA(可变长度数组)(您不需要也不应该使用,因为它是 C++ 扩展且非标准)不考虑也不设置终止空字符。

char reverse[len]; // !! should be len+1
int k = 0;
for (int j = len - 1; j >= 0; j--) {
    reverse[k] = sentence[j];
    k++;
}
// !! Should have reverse[k] = 0; here.
cout << reverse << endl; // !! Undefined-behavior. no terminator.

根本不需要这个临时缓冲区字符串。您没有理由不能就地完成整个操作。一旦我们计算len正确,您只需执行以下操作即可反转整个序列,从而将空字符终止符保留在适当的位置:

// reverse entire sequence
int i = 0, j = len;
while (i < j--)
{
    char c = sentence[i];
    sentence[i++] = sentence[j];
    sentence[j] = c;
}

接下来我们转到您尝试反转每个内部单词的地方。同样,就像以前一样,缓冲区长度不正确。应该是len+1。更糟糕的是(难以想象),当你找到一个单词的结尾时,你永远不会记得你离开的地方。该位置应该是您开始检查和跳过空白的下一个点。在不保留从当前点一直复制到字符串开头的情况下。这基本上爆炸catsdogs

int words = 0;
char str[len]; // !! should be len+1
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; //!! Undefined behavior. non-terminated string.

再一次,这可以毫无困难地就地完成。一种这样的算法看起来像这样(并注意反转实际单词的循环与反转整个缓冲区的算法并不巧合):

// walk again, reversing each word.
i = 0;
while (sentence[i])
{
    // skip ws; root 'i' at beginning of word
    while (sentence[i] == ' ') // or use std::isspace(sentence[i])
        ++i;

    // skip until ws or eos; root 'j' at one-past end of word
    j = i;
    while (sentence[j] && sentence[j] != ' ') // or use !std::isspace(sentence[j])
        ++j;

    // remember the last position
    size_t last = j;

    // same reversal algorithm we had before
    while (i < j--)
    {
        char c = sentence[i];
        sentence[i++] = sentence[j];
        sentence[j] = c;
    }

    // start at the termination point where we last stopped
    i = last;
}

把它们放在一起

尽管使用指针比所有这些索引变量要简单得多,但以下内容将就地完成您正在尝试的操作。

#include <iostream>

int main()
{
    char s[] = "dogs like cats";
    std::cout << s << '\n';

    size_t len = 0, i, j;
    while (s[len])
        ++len;

    // reverse entire sequence
    i = 0, j = len;
    while (i < j--)
    {
        char c = s[i]; // or use std::swap
        s[i++] = s[j];
        s[j] = c;
    }

    // walk again, reversing each word.
    i = 0;
    while (s[i])
    {
        // skip ws; root 'i' at beginning of word
        while (s[i] == ' ') // or use std::isspace
            ++i;

        // skip until ws or eos; root 'j' at one-past end of word
        j = i;
        while (s[j] && s[j] != ' ') // or use !std::isspace
            ++j;

        // remember the last position
        size_t last = j;
        while (i < j--)
        {
            char c = s[i]; // or use std::swap
            s[i++] = s[j];
            s[j] = c;
        }

        // start at last-left posiion
        i = last;
    }

    std::cout << s << '\n';
    return 0;
}

输出

dogs like cats
cats like dogs
于 2014-08-13T06:23:03.843 回答
0

由于他们不要求库,我假设 no std::string, no vectors​​,什么都没有,所以我用 C 写了它。唯一使用的是printf. 其他一切都是从头开始的:l

这个想法是你首先反转数组。然后按空格分割数组并反转每个单词。

示例:http: //ideone.com/io6Bh9

代码:

#include <stdio.h>

int strlen(const char* s)
{
    int l = 0;
    while (*s++) ++l;
    return l;
}


void reverse(char* str)
{
    int i = 0, j = strlen(str) - 1;

    for(; i < j; ++i, --j)
    {
       str[i] ^= str[j];
       str[j] ^= str[i];
       str[i] ^= str[j];
    }
}

void nulltok(char* str, char tok, int* parts)
{
    int i = 0, len = strlen(str);
    *parts = 1;

    for (; i < len; ++i)
    {
        if (str[i] == tok)
        {
            str[i] = '\0';
            ++(*parts);
        }
    }
}

char* reverse_sentence(char* str)
{
    char* tmp = str;
    reverse(str);

    int i = 0, parts = 0, len = strlen(str);
    nulltok(str, 0x20, &parts);

    while(parts--)
    {
        reverse(str);
        str += strlen(str) + 1;
    }

    for(; i < len; ++i)
        if (tmp[i] == '\0')
            tmp[i] = 0x20;

    return tmp;
}


int main(void)
{
    char str[] = "dogs like cats";
    printf("%s", reverse_sentence(str));

    return 0;
}
于 2014-08-13T06:08:33.483 回答
0

我的建议是将原始字符串分解为单词数组,然后反转该数组。然后将这些单词添加到您的反向句子中,中间有一个空格。

于 2014-08-13T04:06:02.790 回答
0

我的解决方案

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
string str;
cout<<"enter the sentence"<<endl;
getline(cin,str);
char* pch;
pch = strtok((char*)str.c_str()," ");
string rev = "";

while(NULL != pch)
{
    rev.insert(0,pch);
    rev.insert(0," ");
    pch = strtok(NULL," ");
}
cout<<"the reversed string is :"<<rev<<endl;
return 0;

}

于 2015-09-20T15:02:06.853 回答