字符串中'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().