java如何递归地反转字符串数组？

Question

应该递归地反转字符串数组

在实现这一点上有困难。如果我使用for循环，我只会在数组的末尾启动它，然后打印出从最后一个元素开始到第一个元素结束的数组

我不太确定如何递归地做。我在考虑使用交换，但当我不知道如何更改正在交换的元素时，这个想法有点失败了

任何想法或朝正确方向推进都将不胜感激

---

这就是我到目前为止所做的。我知道这是错误的，我得到了一个错误的界限异常，我不知道如何修复。我想我没有正确地交换第一个和最后一个。但我的想法对吗

这就是我想到的。 a是一个数组。它在一个班级里

// reverse an array 

public void rev() 
{
    rev(0,a.length-1);
} 

private void rev(int first, int last)
{
if(last == 0)
{
//do nothing
}

else
{
while(first != last)
{
int temp = first;
first = last;
last = temp;


System.out.print(" " + a[first]);
rev((first + 1), (last - 1));
}

}
}

---

进行了一些更改，它反转了最后3个元素，但重复了第二个元素。我没有控制何时运行的if语句，所以它不应该一直运行到left=right吗

这就是我把它改成的

// reverse an array 
public void rev() 
{
    rev(0,a.length-1);
} 

private void rev(int first, int last)
{
    if(last == 0)
    {
    //do nothing
    }

    else
    {


    String temp = a[first];
    a[first] = a[last];
    a[last] = temp;

    System.out.print(" " + a[first]);
    rev(first+ 1, last-1);

    }
}

Answer 1

我总是喜欢有一个调用私有递归方法的简单公共方法。这样，在代码中的其他地方，您只需给它一个数组，而不必担心其他参数。此外，这会捕获空数组，但是您仍然需要在靠近开始的某个点检查null。如果数组为null，可能会在public方法中引发异常

public String[] reverseArray(String[] theArray) {
    this.reverseArrayWorker(theArray, 0, theArray.length -1);
}

private String[] reverseArrayWorker(String[] theArray, int left, int right) {
    // Check your base cases first
    if (theArray.length <= 1) {
        // Array is one element or empty
        return theArray;
    } else if (left - right <= 0) {
        // If there are an odd # of items in the list you hit the center
        // If there are an even number your indexes past each other
        return theArray;
    }
    // Make the recursive call
    this.reverseArrayWorker(theArray, left + 1, right - 1);
    // Switch the two elements at this level
    String temp = theArray[left];
    theArray[left] = theArray[right];
    theArray[right] = temp;
    // Return the array up a level
    return theArray;
}

Answer 2

递归的诀窍是试着用一个基本情况来思考问题，然后用一种方法将所有问题简化为基本情况

因此，如果您试图反转列表，您可以这样想：

1. 大小为1的列表的反面是该列表
2. 对于size > 1列表，输出列表中的第一个元素将是输入列表的最后一个元素
3. 输出列表的其余部分将与输入列表相反，减去最后一个元素

现在有了递归定义

希望有帮助

Answer 3

while循环太多了，因为您无论如何都在使用递归，请像这样尝试

private void rev(int first, int last)
{
   if(first < last)
   {
      var temp = a[first];
      a[first] = a[last];
      a[last]  = temp;
      rev(first + 1, last - 1);
   }
}

Answer 4

public int[] reverse(int[] returnMe, int[] original, int curPos){
    if (original.length == 1){
        return original;
    }else{
        if (curPos < original.length){
            returnMe[curPos] = original[original.length - 1 - curPos];
            reverse(returnMe, original, curPos + 1);
        }else{
            return returnMe;
        }
    }
}    

Answer 5

这里有一个例子（但没有字符串，因为它是家庭作业），但希望它会给你的想法

public static List<Character> reverse(List<Character> chars) {
    return chars.isEmpty() ? chars : 
     addToList(chars.get(0), reverse(chars.subList(1, chars.length()));
}

public static T List<T> addToList(T t, List<T> ts) {
    List<T> ret = new ArrayList<T>();
    ret.addAll(ts);
    ret.add(t);
    return ret;
}

Answer 6

这也行。有点像口齿不清的解决方案

public static List<String> append(String x, List<String> xs) {
    xs.add(x);
    return xs;
}

public static List<String> reverse(List<String> xs) {
    return xs.isEmpty()
            ? xs
            : append(xs.get(0), reverse(xs.subList(1, xs.size())));
}

输入/输出：

List          ==> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Reversed list ==> [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]