java - 字符串中 'x' 个字符的数量 - 递归

Question

我正在练习 Java 中非常基本的递归问题。

“给定一个字符串，递归地(无循环)计算字符串中小写‘x’字符的数量”

countX("xxhixx") → 4

countX("xhixhix") → 3

countX("hi") → 0

-

 public int countX(String str) {
      if (str == null || str.length() == 0)
        return 0;
      else if (str.length() == 1)
        return str.charAt(0) == 'x' ? 1 :0;
      else {
        return (str.charAt(str.length()-1) == 'x' ? 1 : 0 ) + countX(str.substring(0,str.length()-1));
      }
    }

这很好用。但是，我想知道是否有更好的写法。我发现这个代码对于一个简单的问题来说很复杂。

Answer 1

您认为这很麻烦的主要原因是它确实如此。递归解决方案通常不是计算字符串或数组中事物的最佳选择。除了代码看起来很奇怪之外，至少对我来说，您实际上是在为每个字符创建一个新的堆栈框架和一个新版本的字符串。这是低效的(虽然我想知道 String.substring 是否优化为指向原始缓冲区而不是制作完整副本，因为字符串是不可变的)。

但是，考虑到您的问题的限制，您可能可以去掉在代码中进行的一些冗余检查:

public int countX(String str) {
    if(str == null || str.isEmpty())
        return 0;
    return (str.charAt(0) == 'x' ? 1 : 0) + countX(str.substring(1));

由于您已经测试了 null 和空字符串，因此长度为 1 的字符串不再是特例。

通过在每次迭代中删除第一个字符而不是最后一个字符，您可以使索引和对 substring 的调用更加清晰。这也删除了对 str.length() 的两次显式调用。