Как подойти к сложной на первый взгляд задаче программирования?

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

Первый шаг — внимательно прочитать и понять проблему.

Убедитесь, что мы идентифицируем -

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

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

Ниже приведены некоторые распространенные методы, о которых вы наверняка слышали:

Скользящее окно — фиксированное/переменное
Два указателя — указатель вперед/назад
Двоичный поиск
Разделяй и властвуй
Динамическое программирование
Жадный алгоритм
Возврат
Поиск в ширину (BFS) и Поиск в глубину (DFS)
Хеширование
Ветвь и граница
Алгоритм KMP: Алгоритм Кнута-Морриса-Пратта (KMP)
Алгоритм Дейкстры

Есть еще несколько менее известных:

Союз-Найти
Предварительная сумма
Топосорт
моностек
Мемоизация и табуляция
Топологическая сортировка
Битовые манипуляции и бит-маскирование
Три (дерево префиксов):
Скалолазание
Эвристика
Техника катания снежного кома
Имитация отжига
Рандомизированные алгоритмы
Моделирование Монте-Карло

Практикуя эти методы, мы можем с уверенностью подходить даже к самым сложным проблемам программирования и находить эффективные решения.

Для демонстрации попробуем решить следующую задачу —

Вопрос. Найдите самую длинную подстроку, содержащую все неповторяющиеся символы.

Анализ проблемы

1. Ввод — строка (это может быть параметром нашего метода).

        String input = "aababcdefabcdefgbebe";

2. Вывод — строка — это самая длинная подстрока из заданной строки, содержащая все неповторяющиеся символы.

String output = "abcdefg";

3. Шаблон. Из нашей задачи мы видим, что нам нужно найти непрерывную подстроку (переменной длины), которая соответствует заданному условию (неповторяющиеся символы).

Техника скользящего окна. Этот метод позволяет найти непрерывную подстроку или подмассив из заданного элемента/массива с заданным условием.

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

Техника скользящего окна

Терминология

start(самый левый элемент окна),
end(самый правый элемент окна),
window — будет окно конечного размера (конец-начало)

Формат решения

Код, вероятно, будет выглядеть примерно так:

while(end<length)
{
if() //condition where we get the required output and update the output variable

//for fixed size sliding window
else if() //condition where we can't get required output from out current window also condition where we move the window forward

//for variable size sliding window
else if() //condition where we can't get required output from out current window also the condition where we decrease window size by start++
}

Используйте карту/список для сохранения вывода и проверки состояния

Фактическое решение (на Java)

import java.util.HashMap;
import java.util.Map;

public class SlidingWindowUtil {

    public static void main(String[] args) {
        String input = "aababcdefabcdefgbebe";
        String out = findLongestSubstringWithNonRepeatingCharacters(input);
        System.out.println(out);
    }

    private static String findLongestSubstringWithNonRepeatingCharacters(String input) {
        String output = "";
        int length = input.length();
        int start = 0, end = 0;
        Map<Character, Integer> mapCharacterCount = new HashMap<>();
removed, 
        while (end < length) {
            char currentChar = input.charAt(end);
            mapCharacterCount.put(currentChar, mapCharacterCount.getOrDefault(currentChar, 0) + 1);
            int windowSize = (end - start) + 1;

            if (mapCharacterCount.size() == windowSize && mapCharacterCount.size() >= output.length()) {
                output = input.substring(start, end + 1);
            } else if (mapCharacterCount.size() < windowSize) {

                mapCharacterCount.put(input.charAt(start), mapCharacterCount.get(input.charAt(start)) - 1);

                if (mapCharacterCount.get(input.charAt(start)) == 0) {
                    mapCharacterCount.remove(input.charAt(start));
                }
                start++;
            }
//            else if (mapCharacterCount.size()>windowSize) {
//                System.out.println("This condition should never be reached");
//
//            }


            end++;
        }

        return output;
    }

}

Ниже приводится статья, в которой перечислены некоторые проблемы, которые можно решить с помощью техники раздвижного окна —
https://medium.com/techie-delight/top-problems-on-sliding-window-technique-8e63f1e2b1fa

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

Следуйте и подписывайтесь, чтобы получать больше таких статей.

Как подойти к сложной на первый взгляд задаче программирования?