java - indexOf的递归实现
问题描述
我已经在这里和其他地方阅读了许多以前的问题,但我还没有找到我需要的东西。我需要编写 indexOf 的递归实现。问题是我不能使用任何局部变量,并且只能提供一个字符串和一个字符作为输入。
该方法应该返回一个介于 0 和字符串长度之间的值 - 如果找到了 char,则返回 1,如果不存在,则返回 -1。我知道实际的“indexOf”也允许您搜索字符串,但这种方法被简化了。
我试过这个,但它很愚蠢,因为我使用了真正的indexOf:
public static int indexOf(String s, char c){
if(s.indexOf(c) < 0){ // I'd like to change this
return -1;
}
if (s.length() == 0) //base case #1
{
return -1;
}
else if (s.charAt(0) == c) //base case #2
{
return 0;
}
else {
return 1 + indexOf(s.substring(1), c);
}
}
我特别看到了这一点,但是可以在没有变量的情况下编写它吗?谢谢
解决方案
如果您不想要局部变量,则需要在内部方法中进行递归。
优点是速度要快得多,因为它不必创建新String
对象,并且如果与优化它的语言一起使用,逻辑是尾递归的。
public static int indexOf(String s, char c) {
return indexOf0(s, c, 0);
}
private static int indexOf0(String s, char c, int index) {
if (index == s.length())
return -1;
if (s.charAt(index) == c)
return index;
return indexOf0(s, c, index + 1);
}
推荐阅读
- c# - 由于此错误,我的代码行无法工作?
- node.js - 数据未发送到 plotly
- c++ - CGAL 没有计算完整的德劳内三角剖分
- linux - 重新连接(拨号 tcp [(IPv6 addr)]:443: connect: network is unreachable)
- adobe - 使用 Adobe Acrobat Pro 2017 自动扫描:有快捷键吗?
- angular - mat-nav-list 始终以项目为重点
- javascript - .trigger('change') 满足验证后不断刷新分页数据表
- node.js - 如何使用 webpack 为多个目标构建?
- java - 为什么 Build.VERSION.SDK_INT 显示不正确的数字?
- ios - 而委托要么是 nil 要么没有实现 peripheral:didUpdateValueForCharacteristic:error:?