Вот некоторый Java-код для реверсивной реверсии строки.
Может ли кто-нибудь объяснить вам, как это работает?
public static String reverse(String str) {
if ((null == str) || (str.length() <= 1)) {
return str;
}
return reverse(str.substring(1)) + str.charAt(0);
}
Я не понимаю, как это может работать.
Функция принимает первый символ строки - str.charAt(0) - помещает ее в конец, а затем вызывает себя - reverse() - в остатке - str.substring(1), добавляя эти две вещи вместе, чтобы получить ее результат - reverse(str.substring(1)) + str.charAt(0)
Когда переданный в String один символ или меньше, и поэтому остатка не останется - когда str.length() <= 1) - он перестает называть себя рекурсивно и просто возвращает переданную строку.
Итак, он работает следующим образом:
reverse("Hello")
(reverse("ello")) + "H"
((reverse("llo")) + "e") + "H"
(((reverse("lo")) + "l") + "e") + "H"
((((reverse("o")) + "l") + "l") + "e") + "H"
(((("o") + "l") + "l") + "e") + "H"
"olleH"
Вам нужно помнить, что у вас не будет только одного вызова - у вас будут вложенные вызовы. Поэтому, когда "самый сильно вложенный" вызов возвращается немедленно (когда он находит только "o" ), на следующем уровне вверх будет str.charAt(0) - где str будет "lo" в этой точке. Так что вернет "ol".
Затем следующий уровень получит "ol", выполнит str.charAt(0) для своего значения str (который является "llo" ), возвращая "oll" на следующий уровень.
Затем следующий уровень получит "oll" из своего рекурсивного вызова, выполнит str.charAt(0) для своего значения str (который является "ello" ), возвращая "olle" на следующий уровень.
Затем конечный уровень получит "oll" из своего рекурсивного вызова, выполнит str.charAt(0) для своего значения str (который является "hello" ), возвращая "olleh" исходному вызывающему.
Может возникнуть смысл думать о стеке, когда вы идете:
// Most deeply nested call first...
reverse("o") -> returns "o"
reverse("lo") -> adds 'l', returns "ol"
reverse("llo") -> adds 'l', returns "oll"
reverse("ello") -> adds 'e', returns "olle"
reverse("hello") -> adds 'h', returns "olleh"
Запустите его через отладчик. Все станет ясно.
Поскольку это рекурсивно, ваш вывод на каждом шаге будет примерно таким:
Итак, теперь к результатам:
Общее возвращаемое значение даст вам результат рекурсивного вызова плюс первый char
К возврату с 5 будет: "o"
Возврат из 4 будет: "o" + "l"
Возврат из 3 будет: "ol" + "l"
Возврат из 2 будет: "oll" + "e"
Возврат из 1 будет: "olle" + "H"
Это даст вам результат "olleH"
Запустите код ниже - он печатает:
Шаг 0: ello/H
Шаг 1: llo/e
Шаг 2: lo/l
Шаг 3: o/l
Шаг 3 возвращает: ol
Шаг 2 возвращает: oll
Шаг 1 возвращает: olle
Шаг 0 возвращает: olleH
код:
public class Test {
private static int i = 0;
public static void main(String args[]) {
reverse("Hello");
}
public static String reverse(String str) {
int localI = i++;
if ((null == str) || (str.length() <= 1)) {
return str;
}
System.out.println("Step " + localI + ": " + str.substring(1) + " / " + str.charAt(0));
String reversed = reverse(str.substring(1)) + str.charAt(0);
System.out.println("Step " + localI + " returns: " + reversed);
return reversed;
}
}
Встроенный образец;
public static String strrev(String str) {
return !str.equals("") ? strrev(str.substring(1)) + str.charAt(0) : str;
}
Возьмите строку Hello и запустите ее через рекурсивно.
Итак, первый вызов вернется:
return reverse(ello) + H
Второе
return reverse(llo) + e
Которая в конце концов вернет olleH
Вызов повторной передачи (подстрока (1)) выполняется перед добавлением charAt (0). так как вызов вложен, обратная ссылка на подстроку будет вызываться перед добавлением символа ex-second (новый первый символ, так как это подстрока)
reverse ( "ello" ) + "H" = "olleH"
-------- ------- ^
reverse ( "llo" ) + "e" = "olle"
--------- ^ -----
reverse ( "lo" ) + "l" = "oll"
-------- ^ -----
reverse ( "o" ) + "l" = "ol"
--------- ^ ----
"o" = "o"
запустите следующее, и вы увидите, что происходит:
public class RS {
public static String reverse(String str) {
System.out.println("--- reverse --- " + str);
if ((null == str) || (str.length() <= 1)) {
return str;
}
return add(reverse(str.substring(1)), charAt(str));
}
public static char charAt(String s) {
System.out.println("--- charAt --- " + s);
return s.charAt(0);
}
public static String add(String s, char c) {
System.out.println("--- add --- " + s + " - " + c);
return s + c;
}
public static void main(String[] args) {
System.out.println("start");
System.out.println("result: " + reverse("hello"));
System.out.println("end");
}
}
Самое лучшее решение, что я нашел.
public class Manager
{
public static void main(String[] args)
{
System.out.println("Sameer after reverse : "
+ Manager.reverse("Sameer"));
System.out.println("Single Character a after reverse : "
+ Manager.reverse("a"));
System.out.println("Null Value after reverse : "
+ Manager.reverse(null));
System.out.println("Rahul after reverse : "
+ Manager.reverse("Rahul"));
}
public static String reverse(String args)
{
if(args == null || args.length() < 1
|| args.length() == 1)
{
return args;
}
else
{
return "" +
args.charAt(args.length()-1) +
reverse(args.substring(0, args.length()-1));
}
}
}
Выход: C:\Users\admin\Desktop > java Manager Самир после реверса: reemaS Одиночный символ a после реверса: a Значение null после обратного: null Рахул после реверса: luhaR
public class ReverseString{
private static String reverse(String text, String reverseStr){
if(text == null || text.length() == 0){
return reverseStr;
}
return reverse(text.substring(1), text.charAt(0)+reverseStr);
}
public static void main(String [] args){
System.out.println(reverse("hello", "")); //output is "olleh"
}
}
Другие решения для обратного преобразования строки в Java.
Преобразуйте строку в массив char, используя функцию .toCharArray().
public static char[] reverse(char in[], int inLength, char out[],
int tractOut) {
if (inLength >= 0) {
out[tractOut] = in[inLength];
reverse(in, inLength - 1, out, tractOut + 1);
}
return null;
}
class Test {
public static void main (String[] args){
String input = "hello";
System.out.println(reverse(input));
}
private static String reverse(String input) {
if(input.equals("") || input == null) {
return "";
}
return input.substring(input.length()-1) + reverse(input.substring(0, input.length()-1));
} }
Вот пример фрагмента кода, это может вам помочь. Работал для меня.
import java.util.*;
public class StringReverser
{
static Scanner keyboard = new Scanner(System.in);
public static String getReverser(String in, int i)
{
if (i < 0)
return "";
else
return in.charAt(i) + getReverser(in, i-1);
}
public static void main (String[] args)
{
int index = 0;
System.out.println("Enter a String");
String input = keyboard.nextLine();
System.out.println(getReverser(input, input.length()-1));
}
}
AFAIK, в каждой функции рекурсии есть 2 вещи:
Всегда есть условие остановки, которое:
if ((null == str) || (str.length() <= 1)) {return str; } }
Рекурсия использует стековую память, которая использует механизм LIFO, поэтому происходит возврат.
import java.util.Scanner;
public class recursion{
public static void main (String []args){
Scanner scan = new Scanner(System.in);
System.out.print("Input: ");
String input = scan.nextLine();
System.out.print("Reversed: ");
System.out.println(reverseStringVariable(input));
}public static String reverseStringVariable(String s) {
String reverseStringVariable = "";
for (int i = s.length() - 1; i != -1; i--) {
reverseStringVariable += s.charAt(i);
}
return reverseStringVariable;
}
}
Попробуй это:
public static String reverse(String str) {
return (str == null || str.length()==0) ? str : reverseString2(str.substring(1))+str.charAt(0);
}