IP-адрес восстановления алгоритма возврата

Метод поиска с возвратом (метод исследования и возврата) является своего рода методом оптимального поиска, также известным как эвристический метод, который осуществляет поиск вперед в соответствии с оптимальными условиями для достижения цели. Однако, когда исследование достигает определенного шага и обнаруживается, что первоначальный выбор не является оптимальным или не достигает цели, он делает шаг назад и выполняет повторный выбор, называемый «точками возврата».

То, что сказала энциклопедия Baidu, немного неясно, то есть рекурсивный алгоритм, но есть моменты, на которые следует обратить внимание:

• Сохраняйте сцену, сохраняйте последнее состояние при рекурсии и по-прежнему можете вернуться к последнему состоянию после рекурсии.
• Конечное условие, сохранить результат, когда условие выполнено

тема

Получив строку, содержащую только числа, восстановите ее и верните все возможные форматы IP-адресов.

Пример:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

отвечать

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

• большая белая бумага
• рисовать осторожно

Однако рисовать картинки на компьютере может быть удобнее.Давайте сначала подумаем, по какому пути должна идти программа. Как показано на рисунке:

Квалификация:

• Поскольку это IP-адрес, существуют определенные условия и ограничения, число не может быть больше 255 и не может быть меньше 0.
• Как видно на рисунке, IP-адрес находится на уровне 3.

1. Сначала подумайте о приближенных переменных.

• Иерархия
• текущая строка
• оставшаяся строка
• Коллекция сохраненных результатов

2. Напишите условие, завершающее рекурсию

private void restoreAddressNew(String source, String currentStr, Integer currentLevel, Integer offset, List<String> res) {
	if (currentLevel == 3) {
            if (isValidNew(source.substring(offset))
                    ) {
                res.add(currentStr + "." + source.substring(offset));
            }
            return;
     }
     ....
}        

3. Напишите функцию для проверки правильности сегмента в IP.

    private boolean isValidNew(String str) {
        if (str.length() == 0 || str.length() > 3 || Integer.parseInt(str) < 0 || Integer.parseInt(str) > 255
                || (str.startsWith("0") && str.length() > 1)
                ) {
            return false;
        }
        return true;
    }

4. Напишите условие рекурсии

private void restoreAddressNew(String source, String currentStr, Integer currentLevel, Integer offset, List<String> res) {
        if (currentLevel == 3) {

            if (isValidNew(source.substring(offset))
                    ) {
                res.add(currentStr + "." + source.substring(offset));
            }
            return;
        }

    	// 递归段
        for (int i = 1; i <= 3; i++) {
            if (offset > source.length() || (offset + i) > source.length()) {
                return;
            }
            String seg = source.substring(offset, offset + i);
            // 用于保存原先的状态
            String oldStr = currentStr;
            
            // 防止出现以 "."开头的地址
            if (currentStr.length() == 0) {
                currentStr = seg;
            } else {
                currentStr = currentStr + "." + seg;
            }
            if (isValidNew(seg)) {
                restoreAddressNew(source, currentStr, currentLevel + 1, offset + i, res);
                // 处理完之后恢复状态
                currentStr = oldStr;
            }
        }
    }

5. При наличии какой-либо неопределенности в него можно вывести текущее состояние и судить о текущем результате.
6. полная программа

public class RestoreIPAddress {

    public static void main(String[] args) {
        List<String> strings = new RestoreIPAddress().restoreIpAddressesNew("25525511135");
    }

    private List<String> restoreIpAddressesNew(String s) {
        List<String> result = new ArrayList<>();
        restoreAddressNew(s, "", 0, 0, result);
        return result;
    }

    
    private void restoreAddressNew(String source, String currentStr, Integer currentLevel, Integer offset, List<String> res) {
        if (currentLevel == 3) {

            if (isValidNew(source.substring(offset))
                    ) {
                res.add(currentStr + "." + source.substring(offset));

            }
            return;
        }

        for (int i = 1; i <= 3; i++) {
            if (offset > source.length() || (offset + i) > source.length()) {
                return;
            }
            String seg = source.substring(offset, offset + i);
            String oldStr = currentStr;
            if (currentStr.length() == 0) {
                currentStr = seg;
            } else {
                currentStr = currentStr + "." + seg;
            }
            if (isValidNew(seg)) {
                restoreAddressNew(source, currentStr, currentLevel + 1, offset + i, res);
                currentStr = oldStr;
            }
        }
    }

    private boolean isValidNew(String str) {
        if (str.length() == 0 || str.length() > 3 || Integer.parseInt(str) < 0 || Integer.parseInt(str) > 255
                || (str.startsWith("0") && str.length() > 1)
                ) {
            return false;
        }
        return true;
    }
    
}

ошибки в середине

• Первый раз забыл сохранить сцену, будет "бой данных", данные очень странные
• Были адреса, начинающиеся с "."

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

наконец

Рисование — хорошая вещь, чтобы помочь вам прояснить свои мысли, не торопитесь, не торопитесь.

Ссылаться на

• LeetCode 93 вопроса