递归 - 向后打印字符串

-3

什么是使用递归在java中向后打印字符串的最有效方法？如果你给出这个标题：递归 - 向后打印字符串

public void printBackwards(String s)

来源

2015-11-17 flowinwind

你问如何实现或纯粹效率？ –

如果通过'高效'来表示原始表现，那么这个问题将无法回答。 Java是一种语言规范;反转字符串的最有效方法将取决于该规范的实施情况，您正在操作的平台以及许多其他因素。幸运的是，在99.99％的情况下，您可以忽略所有这些，并使用最优雅的解决方案而不是最高效的解决方案。 – sprinter

答案应该是Big-O符号吗？ –

效率明智的最有效的方法是不使用递归。

迭代方法（遍历字符串并打印字符）是线性的，O（N），其中N是字符串的长度。

由于您询问递归解决方案，但它是二次的，O（N^2）表示时间复杂度，因为打印N个字符，每个函数调用都生成N个子字符串。（每次将N-1个字符复制到内存中）。

public void printBackwards(String s) { 
     if (!s.isEmpty()) { 
      int endPos = s.length() - 1; 
      System.out.print(s.charAt(endPos)); 
      printBackwards(s.substring(0, endPos)); 
     } 
    }

来源

2015-11-17 03:04:54

你打我吧> :-( :) – HyperNeutrino

@AlexL 。我喜欢你的破坏者警报代码，虽然:) –

我不是downvoter，但这有'O（N^2）'时间复杂性，因为'substring'必须复制字符。在“改进”String的实现之前，它将是线性的。 –

既然你想递归，我会给你一个提示（因为这是在类问题）：

打印的最后一个字符第一。你将如何递归打印它？现在只是倒退！

悬停揭示代码:)

公共无效printBackwards（一个String）{
如果（s.length（）== 0）返回;
是System.out.print（s.charAt（s.length（） - 1）;
printBackwards（s.substring（0，s.length（） - 1）;
}

来源

2015-11-17 03:10:10 HyperNeutrino

需要一个基本案例... –

@ cricket_007好的赶上！我会解决这个问题... – HyperNeutrino

的

最有效的方式使用递归是这样的：

static void printBackwards(String s) 
{ 
    printBackwards(s, 0, s.length()); 
    System.out.println(); 
} 

static void printBackwards(String s, int start, int end) 
{ 
    if ((end-start)<2) 
    { 
     if (end>start) 
     { 
      System.out.print(s.charAt(start)); 
     } 
     return; 
    } 
    int mid = start + (end-start)/2; 
    printBackwards(s, mid, end); 
    printBackwards(s, start, mid); 
}

这是比其他答案更为有效，因为它不分配一大堆新的字符串和只使用O（日志N）的堆栈.. 。

但是，你真的不需要递归来向后打印一个字符串。

注意：如果这是家庭作业，你的手在此，您将教授可能知道，你没有写吧:)

来源

2015-11-17 05:05:32

递归 - 向后打印字符串

回答

相关问题