Можно ли перевернуть строку без циклов и встроенных методов

Question

Можно ли перевернуть строку без циклов и встроенных методов

Рейтинг: -1Ответов: 1Опубликовано: 27.02.2023

Сегодня получил список тестов на вакансию и некоторые показались крайне интересными

Реализовать метод reverse, на входе String, нельзя использовать циклы и встроенные методы.
Реализовать метод для суммирования чисел, на вход получаем Integer, например 1235, необходимо вернуть сумму 1 + 2 + 3 + 5, не используя циклы и операции со строками

java рекурсия

Источник: Stack Overflow на русском

Answer 1

▲ 2

Как правило, если в задании написано сделать что-либо, не используя циклы, это скорее всего толстый намёк на использование рекурсии.
Однако, остаётся открытым вопрос использования встроенных методов, так как в джаве "прямой" доступ к символам строки типа индекса (как в C# char c = str[0];) невозможен и необходимо пользоваться как минимум методами String::charAt / String::substring / String::toCharArray для доступа к символам/подстрокам. Поэтому предположим, что "табу" накладывается только на методы типа StringBuilder::reverse.
Также не будем рассматривать вариант использования Stream API.

Сразу же следует заметить, что рекурсия конечно божественна, но для достаточно больших входных данных (например, длинных строк) вероятность переполнения стека вызовов и выбрасывания StackOverflowError стремится к единице.

Переворот строки.
a) C использованием String::charAt и String::substring:

public static String reverseSub(String str) {
    // фильтрация входных данных / выход из рекурсии
    if (null == str || "".equals(str)) {
        return str;
    }
    return reverseSub(str.substring(1)) + str.charAt(0);
}

Основной недостаток такого решения -- множественная генерация подстрок и конкатенация с одиночным символом.

б) С использованием одного массива символов и перестановкой элементов в начале и конце массива:

public static String reverse(String str) {
    if (null == str || "".equals(str)) {
        return str;
    }
    return new String(reverse(str.toCharArray(), 0, str.length()));
}

private static char[] reverse(char[] arr, int start, int end) {
    if (start >= end) {
        return arr;
    }
    // перестановка символов в конце и начале массива
    char tmp = arr[start];
    arr[start++] = arr[--end];
    arr[end] = tmp;

    return reverse(arr, start, end);
}

Вычисление суммы цифр числа
Это более тривиальная задача, которая решается при помощи целочисленного деления и остатка при делении на 10:

public static int sumDigits(int n) {
    if (n < 0) return sumDigits(-n);

    return n < 1 ? n : n % 10 + sumDigits(n / 10);
}

System.out.println(sumDigits(123456)); // -> 21

(Обновление) Если в качестве входного значения допускается Integer.MIN_VALUE, для которого не существует противоположного положительного целого значения, то следует обработать этот случай особо:

public static int sumDigits(int n) {
    if (n < 0) {
        if (n == Integer.MIN_VALUE)
            return 1 + sumDigits(Integer.MAX_VALUE);
        return sumDigits(-n);
    }
    return n < 1 ? n : n % 10 + sumDigits(n / 10);
}

System.out.println(sumDigits(Integer.MIN_VALUE)); // -> 47

Можно ли перевернуть строку без циклов и встроенных методов

Ответы