1

我试图用递归找到最长的字符串，虽然我得到了正确的答案，但我不确定我的方法是否是递归的。我的主目录中有一个链表，我需要找到最长的链表。我的字符串最大的方法是“递归”

import java.util.LinkedList;


public class MyLinkedList extends LinkedList<String> {
  public static String max="";

public static void main(String[] args) {
    // TODO Auto-generated method stub

    MyLinkedList myLinkedList = new MyLinkedList();
    myLinkedList.add("Sarah");
    myLinkedList.add("Barbara");
    myLinkedList.add("Tom");
    myLinkedList.add("George");
    String largest = myLinkedList.findLargestStarter();
    String largest1= largest( myLinkedList,0, 1);
    System.out.println("Largest "+largest1);
    System.out.println("max "+max);

}


public String findLargestStarter()
{
    //largest=max;
    return null;


}

public static  String largest(MyLinkedList myLinkedList, int lowerIndex, int upperIndex)
{
     if(lowerIndex == upperIndex)   //the size of the sublist                       // is 1
      max= myLinkedList.get(lowerIndex);
   else
   {
      max = largest(myLinkedList, lowerIndex + 1, upperIndex);
      if( myLinkedList.get(lowerIndex).length() >      myLinkedList.get(upperIndex).length())
          max= myLinkedList.get(lowerIndex);
      else
          max= myLinkedList.get(upperIndex);
   }
//   System.out.println(max);
     return max;
}

}

4

3 回答 3

0

您可以进行一些小的改进，以使该程序更具可读性和整体性更好：

  • 消除全局静态变量的使用。它应该返回答案作为返回参数的递归函数的味道和点真的很差
  • 如果您想尝试正确进行递归，而不是创建自己的数据结构，请使用 java.util 包中的列表。

我整理了几行可以解决您的问题的行。方法只是每次更深时减少列表直到它为空：

import java.util.Arrays;
import java.util.List;

public class FindTheLongest {

    public static void main(String[] args) {
        final List<String> list = Arrays.asList(new String[] { "Sarah", "Barbara", "Tom", "George" });
        System.out.println(findLongestString(list, list.get(0)));
    }

    private static String findLongestString(List<String> list, String longestString) {
        if (!list.isEmpty())
        {
            final List<String> nextList = list.subList(1, list.size());
            final String nextLongestString = longestString.length() > list.get(0).length() ? longestString : list.get(0);
            return findLongestString(nextList, nextLongestString);
        }
        return longestString;
    }
}

请让我知道你在找什么。

于 2012-10-15T05:37:35.127 回答
0

不逐行进行，您的递归方法largest看起来不错：

  1. 它从 else 块中调用自己。第一行为满意。
  2. 顶部有一个终止条件（您的 if 块），它不会调用自己。第二行为满意。

我不明白您为什么将逻辑放在块中对largest方法的调用下方。else希望你能更好地理解这一点。

于 2012-10-15T05:18:34.500 回答
0

我们的目标是练习递归。

我更欣赏 Yogendra Singh 的回答，因为它更具学术性。

Petro Semeniuk 的提议行之有效，但这不是问题所在。

AMHO 重用 LinkedList<T> 不是一个好的选择。

为了理解递归，触及它的内部行为，我们必须开发一个简单的链表实现，除了 java.lang 之外根本没有导入，并逐步调试它的方法。

我建议这样的课程：

public class StringNode // no generics, it's not the goal
{
   public StringNode next;
   public String     text;

   public StringNode( String text )
   {
      this( text, null );
   }

   public StringNode( String text, StringNode next )
   {
      this.text = text;
      this.next = next;
   }

   public String getLongest()
   {
      String nextText = (( next == null ) ? "" : this.next.getLongest());
      return ( this.text.length() > nextText.length()) ? this.text : nextText;
   }

   public static void main( String[] args )
   {
      StringNode head = null;
      for( String text : new String[] { "Sarah", "Barbara", "Tom", "George" })
      {
         head = new StringNode( text, head );
      }
      System.err.println( head.getLongest());
   }
}

性能说明：new 运算符不直接在 main() 之外调用。

于 2012-10-15T05:54:42.820 回答