Я сегодня возился с рекурсией. Часто метод программирования, который не используется достаточно.
Я решил рекурсивно изменить строку. Вот что я придумал:
//A method to reverse a string using recursion
public String reverseString(String s){
char c = s.charAt(s.length()-1);
if(s.length() == 1) return Character.toString(c);
return c + reverseString(s.substring(0,s.length()-1));
}
Мой вопрос: есть ли лучший способ в Java?
Лучший способ - не использовать рекурсию. Эти материалы обычно используются для обучения студентов концепции рекурсии, а не фактических лучших практик. Так что, как вы это делаете, все в порядке. Просто не используйте рекурсию в Java для такого рода вещей в приложениях реального мира;)
PS. Помимо того, что я только что сказал, я бы выбрал "" как базовый случай моей рекурсивной функции:
public String reverseString(String s){
if (s.length() == 0)
return s;
return reverseString(s.substring(1)) + s.charAt(0);
}
Если вы собираетесь это сделать, вы хотите работать с массивом символов, потому что String неизменен, и вы будете копировать строки по всему месту, если вы это сделаете.
Это непроверенный и полностью поток сознания. Вероятно, у него OB1. И очень не-Java.
public String reverseString(String s)
{
char[] cstr = s.getChars();
reverseCStr(cstr, 0, s.length - 1);
return new String(cstr);
}
/**
* Reverse a character array in place.
*/
private void reverseCStr(char[] a, int s, int e)
{
// This is the middle of the array; we're done.
if (e - s <= 0)
return;
char t = a[s];
a[s] = a[e];
a[e] = t;
reverseCStr(a, s + 1, e - 1);
}
Вы не хотите слишком глубоко входить. Разделение и победа - это путь. Также уменьшает общий размер временных строк и поддается параллелизации.
public static String reverseString(String str) {
int len = str.length();
return len<=1 ? str : (
reverseString(str.substring(len/2))+
reverseString(str.substring(0, len/2))
);
}
(Не проверено - это stackoverflow.)
String.concat вместо + улучшит производительность за счет ясности.
Изменить: просто для удовольствия, дружественная к хвосту версия наивного алгоритма.
public static String reverseString(String str) {
return reverseString("", str);
}
private static String reverseString(String reversed, String forward) {
return forward.equals("") ? reversed : (
reverseString(reversed+forward.charAt(0), forward.substring(1))
);
}
Правильное обращение с суррогатными парами предоставляется заинтересованному читателю.
Если вы пишете реальный код (не изучая рекурсию), используйте метод StringBuilder reverse(). Java Tutorial дает следующий пример:
String palindrome = "Dot saw I was Tod";
StringBuilder sb = new StringBuilder(palindrome);
sb.reverse(); // reverse it
System.out.println(sb);
вот моя рекурсивная обратная функция, которая отлично работает
public static String rev(String instr){
if(instr.length()<=1){
return instr;
} else {
return (instr.charAt(instr.length()-1)+rev(instr.substring(0,instr.length()-1)) );
}
}
Просто для этого, здесь хвостовой рекурсивный метод с использованием StringBuilder (который обычно рекомендуется для управления String s).
public String reverseString(String s_) {
StringBuilder r = new StringBuilder();
StringBuilder s = new StringBuilder(s_);
r = reverseStringHelper(r, s);
return r.toString();
}
private StringBuilder reverseStringHelper(StringBuilder r, StringBuilder s) {
if (s.length() == 0)
return r;
else
return reverseStringHelper(r.append(s.charAt(0)), s.deleteCharAt(0));
}
Непроверенный, я не занимался Java за многие годы, но это должно быть правильно.
Это зависит от того, что вы определяете как "лучшего".:-) Если серьезно; ваше решение в основном использует максимальную глубину рекурсии; если размер стека вызывает беспокойство по поводу вашего определения "лучше", тогда вам лучше использовать что-то вроде этого:
public String reverseString(String s) {
if (s.length() == 1) return s;
return reverseString(s.substring(s.length() / 2, s.length() -1) + reverseString(0, s.length() / 2);
}
Это то, что я нашел, чтобы работать и использовать рекурсивный. Вы можете передать str.length() как аргумент strLength
private static String reverse(String str, int strLength) {
String result = "";
if(strLength > 0)
result = str.charAt(strLength - 1) + reverse(str, strLength - 1);
return result;
}
Это определенно, как я буду рекурсивно реверсировать строку (хотя было бы неплохо распространить ее на случай пустой строки в вашем состоянии.) Я не думаю, что есть какой-либо принципиально лучший способ.
EDIT: возможно, более эффективно работать с массивом символов и пропускать "отсечку" по цепочке рекурсии, если вы получите мой дрейф, а не подстроки. Тем не менее, это на самом деле не стоит задирать, так как это не очень эффективный метод в первую очередь.
Как отметил Mehrdad, лучше не использовать рекурсию. Однако, если вы его используете, вы можете сохранить как первый, так и последний символ каждого вызова, тем самым сократив вдвое количество рекурсивных вызовов. То есть
public String reverseString(String s){
int len = s.length();
if (len <= 1) {
return s;
}
char fst = s.charAt(0);
char lst = s.charAt(len - 1);
return lst + reverseString(s.substring(1, len - 2)) + fst;
}
Это также обрабатывает случай пустой строки. Возможно, прохождение по StringBuilder с соответствующей способностью ускорит работу еще больше, но это оставило в качестве упражнения для читателя;)
Вы фиксируете основную идею, но извлечение последнего символа не улучшает ясность. Я бы предпочел следующее, другие могут не быть:
public class Foo
{
public static void main(String[] argv) throws Exception
{
System.out.println(reverse("a"));
System.out.println(reverse("ab"));
System.out.println(reverse("abc"));
}
public final static String reverse(String s)
{
// oft-repeated call, so reduce clutter with var
int length = s.length();
if (length <= 1)
return s;
else
return s.substring(length - 1) + reverse(s.substring(0, length - 1));
}
}
Вы можете попробовать с внешней переменной и добавить 1 к 1 все символы:
public static String back="";
public static String reverseString(String str){
if(str.length()==0){
return back;
}else {
back+=str.charAt(str.length()-1);
lees(str.substring(0,str.length()-1));
return back;
}
}
Здесь - моя неизменяемая версия:
String reverse(String str) {
if(str.length()<2) return str;
return reverse(str.substring(1)) +str.charAt(0);
}
и хвостовая рекурсивная версия:
String reverseTail(String str) {
if(str.length()<2) return str;
return str.charAt(str.length()-1)+ reverseTail(str.substring(0,str.length()-1));
В этом контексте это совершенно необязательно, но вы можете имитировать рекурсию и избегать проблем с глубиной рекурсии, если вы создаете свой собственный стек.
Итеративная реализация рекурсии, которая может потребоваться, когда у вас есть алгоритмы, которые являются неотъемлемо рекурсивными, но также должны запускать их для больших размеров проблем.
String recIterReverse (String word){
Stack <String> stack = new Stack <String> ();
stack.push(word);
String result = "";
while (!stack.isEmpty()){
String temp = stack.pop();
result = temp.charAt(0) + result;
if (temp.length() > 1){
stack.push(temp.substring(1));
}
}
return result;
}
вызов функции:
//str:string to be reversed,i=0,j=str.length-1
public void reverseString(String str,int i,int j)
{
if(i==j)
{
System.out.println(str);
return;
}
char x=str.charAt(i);
str=str.replace(str.charAt(i),str.charAt(j));
str=str.replace(str.charAt(j),x);
i++;j--;
reverseString(str,i,j);
}
этот метод работает тоже.
Попробуйте следующее:
public class reverse2
{
public static void main(String name)
{
String revname=new StringBuffer(name).reverse().toString();
System.out.println("original string " + name + " and the reverse of it is " + revname);
}
}
public static String rev(String name){
if(name.length()>=1){
System.out.print(name.charAt(name.length()-1));
return rev(name.substring(0,name.length()-1));
}
else{
return ""+name.substring(0);
}
}
String rev="";
public String reverseString(String s){
if (s.length()==0) return "";
return rev+s.substring(s.length()-1,s.length())+reverseString(s.substring(0, s.length()-1));
}
public String reverseString (String s) {
if (s != null && s.length () > 0 ) {
rev = rev + s.substring (s.length () - 1);
reverseString (s.substring (0, s.length () - 1));
}
return rev;
}
public class StringUtility {
public static void main(String[] args) {
StringUtility stringUtility = new StringUtility();
String input = "santosh123";
int middle = input.length() / 2;
middle = middle - 1;
System.out.println(stringUtility.stringReverse(input, middle));
}
public String stringReverse(String input, int middle) {
if (middle == -1) {
System.out.println("if");
return input;
} else {
System.out.println("else");
input = swapChar(input, middle);
middle = middle - 1;
return stringReverse(input, middle);
}
}
private String swapChar(String input, int middle) {
StringBuilder str = new StringBuilder(input);
char begin = str.charAt(middle);
int endIndex = input.length() - middle - 1;
char end = str.charAt(endIndex);
str.setCharAt(middle, end);
str.setCharAt(endIndex, begin);
System.out.println(str + " " + middle + " " + endIndex);
return str.toString();
}
}
Если вы думаете, что код меньше, тогда...
static String reverse(String str){
return str.length()>=2 ? str.charAt(str.length()-1) + reverse(str.substring(0,str.length()-1)) : str ;
}
Уже есть около 20 ответов, но я просто буду использовать рекурсивный алгоритм. Это может быть немного многословным, но, по крайней мере, это понятно.
public static String reverseString(String str) {
return reverseString("", str);
}
private static String reverseString(String result, String original) {
if (original.length() == 0) {
return result;
} else {
int length = original.length();
String lastLetter = original.substring(length - 1, length);
original = original.substring(0, length - 1);
return reverseString(result + lastLetter, original);
}
}
Код в основном рекурсивно берет конец строки и перемещает ее вперед. Например, если строка, которую мы хотим изменить, является "jam", то каждый раз, когда вызывается метод helper, исходные и исходные строки выглядят следующим образом:
// result: original:
// "" jam
// m ja
// ma j
// maj ""
Обратная строка, используя вызов рекурсивного метода.
Пример кода
public static String reverseString(String s) {
if (s.length() == 0) {
return s;
}
else {
return s.charAt(s.length() - 1) + reverseString(s.substring(0, s.length() - 1));
}
}
Это мое решение, которое я видел во многих решениях выше, мы получаем длину строки, но в идеале нам это не нужно. Zen должен использовать рекурсию, просто нарезать первую строку char и передать остальную часть рекурсивному методу. Ура!! мы получили решение.
private static void printReverse(String str) {
if (!str.isEmpty()) {
String firstChar = str.substring(0, 1); //Get first char of String
String newstr = str.substring(0, 0) + str.substring(1); // Get remaining string
printReverse(newstr); // Recursion magic
System.out.print(firstChar); //Output
}
}
public static String reverse(String s){
int n = s.length()-1;
if(n >=0)
return s.substring(s.length()-1)+ReverseString(s.substring(0,n--));
else return "";
}