Codingbat递归练习（java）

Question

我怎样才能递归地解决这个问题而不是使用替换方法？我正在努力改进递归方法。

给定一个字符串，递归地（无循环）计算一个新字符串，其中所有小写 'x' 个字符都已更改为 'y' 个字符。

changeXY("codex") → "codey"
changeXY("xxhixx") → "yyhiyy"
changeXY("xhixhix") → "yhiyhiy"

我是这样骗过去的，想看JavaString方法replace的源码，没看懂。这是我的方法。

public String changeXY(String str) {
  int len = str.length();
  int i = 0;
  String changedStr = str.replace("x","y");


  if (len == 0)
    return str;

  return changedStr;

}

关于如何以递归方式执行此操作的任何想法？

这是一个我也不知道该怎么做的额外练习。谢谢你的帮助！！！

给定一个字符串，递归地计算一个新字符串，其中所有 'x' 个字符都已被删除。

noX("xaxb") → "ab"
noX("abc") → "abc"
noX("xx") → ""

Answer 1

递归几乎总是由两件事组成：

停止递归的条件。

假设我们可以解决一个较小的问题，如何使用该假设解决当前问题。

public String changeXY(String str) {

  // when to stop
  if (str.length() == 0){
    return str;
  }

  // handle the "special case" using an assumption we can solve str.substring(1)
  if (str.charAt(0) == 'x'){
    return 'y' + changeXY(str.substring(1));
  }
  // handle the "simple" case using an assumption we can solve str.substring(1)
  return str.charAt(0) + changeXY(str.substring(1));
}

一旦你了解了它的工作原理，其他练习就很容易了。

Answer 2

伪代码：

  changeXY(input) {
    if (input.isEmpty()) return "";
    head = "firstChar"(input);
    tail = "theRest"(input);
    return (head == 'x' ? 'y' : head) + changeXY(tail);
  }


  noX(input) {
    if (input.isEmpty()) return "";
    head = "firstChar"(input);
    tail = "theRest"(input);
    return (head == 'x' ? '' : head) + noX(tail);
  }

您所要做的就是实现或调用适当的 Java API 而不是 "firstChar" 和 "theRest"。我相信这会是小菜一碟 ;)

Answer 3

第一次练习：

public String changeXY(String str) {
      int len = str.length();
      String changedStr = "";
      for(int i=0; i<len; i++){
          if(str.charAt(i) == 'x'){
              changedStr+="y";
          }else{
              changedStr+=str.charAt(i);
          }
      }

      if (len == 0)
        return str;

      return changedStr;

}

当它是 "x" 时，更改为 y 直到字符串终止。

第二个练习更简单：只需将 changedStr+="y" 部分更改为 continue java 指令。

但是，这段代码对初学者来说并不友好。它要求您对循环有一般性的了解。如果您是学生，我真的建议您查看其他答案。它们更容易理解和掌握。

Answer 4

递归基于两件事： 1- 基本情况：这将阻止方法在特定条件下调用自身 2- 操作：您想通过此方法执行的操作 + 通过更改其参数再次调用该方法以达到基本情况。在这种情况下，您必须执行以下操作

public String changeXY(String string){

    string = string.toLowerCase();
    if(string.length()==0)
    { 
        return string;
    }
    else if (str.charAt(0) == 'x')
    {
        return 'y' + changeXY(str.substring(1));
    }

    return str.charAt(0) + changeXY(str.substring(1)); 
}

Answer 5

希望我的回答能说明一切:)

public String changeXY(String str) {
  if (str.length() == 0) return ""; // return empty string if we reached the end of string
  String count = str.substring(0,1); // get the current string
  if (str.substring(0, 1).equals("x")) count = "y"; // if its x then replace it with y 
  // attach it to our final string and make recursive call passing string past the read character
  return count + changeXY(str.substring(1)); 
}

Answer 6

python代码

def changeXY(s):
    if len(s) == 1 and s == 'x' : return 'y'
    if len(s) == 1 : return s
    char,sub = s[0:1],s[1:]       
    if char == 'x' :  char = 'y'  
    return char + changeXY(sub)

Answer 7

只在给定字符串中有'x'的地方才进入递归。进行递归调用，直到所有 'x' 都更改为 'y'.

public String changeXY(String str) {
  if(str.contains("x")){
    int idx = str.indexOf("x");
    return changeXY(str.substring(0,idx) + "y" + str.substring(idx+1, str.length()));
  }
  else return str;
}

Answer 8

第一次练习...

public String changeXY(String str) {
  if(str.length() == 0) return str;
  if(str.charAt(0) == 'x') return 'y' + changeXY(str.substring(1, str.length()));
  return str.charAt(0) + changeXY(str.substring(1, str.length()));
}

第二次练习...

public String noX(String str) {
  if(str.length() == 0) return str;
  if(str.charAt(0) == 'x') return "" + noX(str.substring(1));
  return str.charAt(0) + noX(str.substring(1)); 
}

Codingbat递归练习（java）

Coding Bat Recursion exercise (java)

java

string

recursion