1

我最近在一次采访中被问到这个问题。作为一个刚毕业的学生，​​并且只编程了大约 2 年（所有学校工作），我不知所措。我有一个模糊的想法，但我确定我失败了。这是我写的：

string Reverse(string word, string reversed)
{
    if(word.length() == 0)
    {
        return reversed;
    }
    else
    {
        string temp;
        reversed = word.substr(0,1) + reversed;
        temp = word.substr(1);
        Reverse(temp, reversed);
    }

    return reversed;
}

现在我到家了，我正在测试它，返回的只是输入中的第一个字母。我对递归的概念模糊熟悉，但我显然在这方面失败了。非常感谢任何帮助/指针/建议。谢谢你。

编辑：在 Dennis Meng 的帖子之后，我做了以下更改：

string Reverse(string word, string reversed)
{
    if(word.length() == 0)
    {
        return reversed;
    }
    else
    {
        string temp;
        reversed = word.substr(0,1) + reversed;
        temp = word.substr(1);
        return Reverse(temp, reversed);
    }
}

现在，我得到了正确的返回值。非常感谢你。

4

6 回答 6

2

出了什么问题：

    else
    {
        string temp;
        reversed = word.substr(0,1) + reversed;
        temp = word.substr(1);
        Reverse(temp, reversed); // <-- Here's your problem
    }

    return reversed;
}

你知道调用应该返回正确的答案，那么为什么不直接返回呢？换句话说，如果你这样做了怎么办

    else
    {
        string temp;
        reversed = word.substr(0,1) + reversed;
        temp = word.substr(1);
        return Reverse(temp, reversed);
    }
}

反而？为什么你的代码只返回第一个字母的细节涉及按引用/按值传递；由于传递值的东西，你从来没有真正使用过递归调用中所做的事情。（你只是打了电话，然后扔掉了它返回的东西。）

于 2012-08-09T16:56:34.210 回答
1

我不确定你为什么在这里使用递归。这真的没有必要：

string Reverse(string word)
{
    string reversed = "";

    if(word.length() == 0)
    {
        return reversed;
    } 

    for (int i = word.length()-1; i>=0; i--){
        reversed = reversed+word[i];
    }

    return reversed;
}
于 2012-08-09T16:49:59.653 回答
1 
string Reverse(string word, string reversed) 
{
    ...
    Reverse(temp, reversed);

首先，您应该word通过 const 引用和reversed引用传递。当您调用递归函数时，您正在制作每个字符串的副本，因此最外面的函数看不到它们所做的任何事情。另一种选择是将递归函数的结果分配给reversed，但是您仍然到处都有大量的字符串副本。所以：通过引用传递变量。

第二：有更简单的方法来反转字符串：

 string Reverse(string word) //caller should _not_ see my changes, so I pass by value
 {
     for(int i=0; i<word.size()/2; ++i) { //for each letter in the first half
         int otherindex = word.size()-1-i; //find the letter on the other half
         char t = word[i];  //and swap them
         word[i] = word[otherindex];
         word[otherindex] = t;
     }
     return word; //return the result
 }
于 2012-08-09T16:51:31.383 回答
0

字符串只不过是一个字符数组。通常在这种情况下，您应该使用一个字符数组来解释算法。这是一个更好的方法。

void reverse(char* str, int len)
{
    for (int i = 0, j = len -1 ; i < len / 2; ++i, --j) {
         // Swap the values as i and j.
         int temp = str[i];
         str[i] = str[j];
         str[j] = temp;
    }
}

如果在 Java 中提出同样的问题，您必须确保将字符串转换为 char[] 数组反转它，然后形成一个字符串。这有助于保持创建的对象数量最少。至少，您应该使用 StringBuilder。

于 2012-08-09T16:55:07.100 回答
0

这是另一种解决方案（类似于已经发布的解决方案）。但是现在我发现这个解决方案不适合你，因为它使用了 std 的东西。

std::string reverse(std::string const& character_queue_) {
    using namespace std;
    string result;
    if(!character_queue_.empty()) {
        vector<char> character_stack;
        std::copy(character_queue_.begin(),character_queue_.end(),std::back_inserter(character_stack));
        while(!character_stack.empty()) {
           result.push_back(character_stack.back());
           character_stack.pop_back();
        }
    }
    return result;
}
于 2012-08-09T18:48:26.543 回答
-2

只是为了建议一种更好的处理递归的方法：

在 C++ 中使用递归进行字符串反转：

#include <iostream>
#include <string>
using namespace std;

string reverseStringRecursively(string str){
    if (str.length() == 1) {
        return str;
    }else{
        return reverseStringRecursively(str.substr(1,str.length())) + str.at(0);
    }
}

int main()
{
    string str;
    cout<<"Enter the string to reverse : ";
    cin>>str;

    cout<<"The reversed string is : "<<reverseStringRecursively(str);
    return 0;
}
于 2013-02-28T22:02:51.193 回答