Рекурсивно меняйте пары букв в строке в Java

Question

Например, если я вызываю exchangePairs ("abcdefg"), я должен получить взамен "badcfeg".

Это для домашнего задания, любой вид псевдокода был бы очень полезен. Я только начинаю изучать рекурсию, и до этой проблемы у меня не было особых проблем.

Answer 1

public String swapPairs(String s) {
     if (s.length() < 2)
          return s;
     else
          return swap(s.charAt(0), s.charAt(1)) + swapPairs(s.substring(2));
}

Answer 2

Вы не только начинаете изучать рекурсию, потому что рекурсия является частью вашей повседневной жизни. Вы просто не замечаете, потому что это так нормально, и никто не называет это рекурсией.

Например, вы смотрите фильм по телевизору, и в одной сцене есть кто-то, кто смотрит фильм по телевизору.

В программировании рекурсия - это способ облегчить сложные вещи. Всегда начинайте с простого случая:

• Каков результат exchangePairs ("")?
• Что является результатом exchangePairs ("x"), где x - любой символ?
• Предположим, что вы уже выполнили exchangePairs (), каков будет результат для "xy ...", где "..." - любая строка? Конечно, "yx +++", где "+++" является результатом exchangePairs ("...").

Теперь оказалось, что мы рассмотрели все случаи! Задача решена! Таково величие рекурсии. Вы просто используете свою функцию, как если бы она была завершена, несмотря на то, что вы еще не завершили ее.

Answer 3

Небольшое добавление к решению Стивена, вы можете использовать StringBuffer / StringBuilder.reverse () для обращения строки.

 public String swapPairs(String s) {
    if (s.length() < 2)
        return s;
    else {
        return new StringBuffer(s.substring(0, 2)).reverse().toString() + swapPairs(s.substring(2));
    }
}

Answer 4

public static String swapPairs(String s) {
    String even = "";
    String odd = "";
    int length = s.length();

    for (int i = 0; i <= length-2; i+=2) {          
        even += s.charAt(i+1) + "" + s.charAt(i);
    }

    if (length % 2 != 0) {          
        odd = even + s.charAt(length-1);
        return odd;
    } else {
        return even;
    }
}

Answer 5

Хорошо. Вот мое решение. Я не имею в своем распоряжении Java, поэтому я сделал это на C #, который очень похож на Java, поэтому должен быть легок для понимания / port;

 public static char[] exchangePairs(char[] charArray, int current)
        {
            if(current >= charArray.Length - 1)
            {
                return charArray;
            }

            char nextChar = charArray[current + 1];
            char currentChar = charArray[current];

            charArray[current] = nextChar;
            charArray[current + 1] = currentChar;

            int i = current + 2;

            return exchangePairs(charArray, i);
        }

Вызов метода:

exchangePairs ("abcdefghij" .ToCharArray (), 0);

Answer 6

Использовать хвостовую рекурсию

String reverse(String input)
{
   if(String.length()==1)
   {
     return input;
   }
   else
   {
      return reverse(input,"");
   }
}

String reverse(String input, String result)
{
   if(input.length == 0) return result;
   else return result(input.substring(1),input.charAt(0) + result);
}

Answer 7

Я бы ввел переменную управления целочисленной рекурсией, которая показывает, какая часть строки уже была обменена.На каждом уровне проверьте управляющую переменную, чтобы узнать, есть ли еще что-то, и, если да, обменяйте следующую пару, увеличивайте на 2 и рекурсивно.

Answer 8

Зачем использовать рекурсию?

for (int i = 0; i + 1 < strlen(str); ++i) {
    char tmp = str[i + 1];
    str[i + 1] = str[i];
    str[i] = tmp;
} 

Если вам нужно использовать рекурсию, я думаю, вы могли бы сделать что-то вроде этого:

char* exchangePairs(char* str) {
    if (strlen(str) >= 2) {
        // if there are characters left, swap the first two, then recurse
        char tmp = str[1];
        str[1] = str[0];
        str[0] = str[1];

        exchangePairs(str + 2);
    }

    return str;
}

Это в C, но это должно дать вамидея (я лучше в C и не хочу просто дать вам решение для копирования / вставки).