предисловие
Контент, которым поделились на этот раз, представляет собой классическую идею алгоритма - разделяй и властвуй, вы можете назвать это идеей, или вы можете назвать это алгоритмом разделяй и властвуй, Чтобы лучше различать, мы будем использовать"разделяй и властвуй"назвать это.
Если вы не знаете, что такое разделяй и властвуйте, или знаете что-то, но как это реализовать回溯, то эта статья может быть полезной для вас.
❝Мое понимание алгоритма разделяй и властвуй:
Его основная идея состоит в том, чтобы разложить проблему размера N на K меньших подзадач, которые независимы друг от друга и имеют те же свойства, что и исходная задача.
Решение исходной задачи может быть получено путем нахождения решения подзадачи, которую можно понимать как алгоритм, дополняющий программу подзадачами.
Дихотомия часто представляет собой идею «разделяй и властвуй».
❞
Затем мы введем алгоритм «разделяй и властвуй» вокруг следующих точек👇
- Основная идея
- Применимые ситуации и какие классические задачи решать
- классический пример
Свяжитесь с 👉TianTianUp, если у вас возникнут проблемы, вы можете связаться с автором, я готов сопровождать вас, чтобы вместе изучить и обсудить проблему.
Основная идея разделяй и властвуй
Одним словом, резюмируя его по методу разделяй и властвуй👇
Разделите исходную проблему на n меньших подзадач со структурой, аналогичной исходной задаче, рекурсивно решите эти подзадачи, а затем по очереди объедините результаты и, наконец, получите решение исходной задачи.
Так что конкретно мы, кажется, можем разделить его на три шага👇
- Декомпозиция: Разделите проблему, которую нужно решить, на несколько более мелких задач того же типа.
- Решение: Когда подзадачи достаточно малы, решайте их более простым способом.
- Слияние: в соответствии с требованиями исходной проблемы решения подзадач объединяются слой за слоем, чтобы сформировать решение исходной проблемы.
На самом деле идея все та же: разделить большую проблему, которую трудно решить напрямую, на несколько мелких одинаковых задач, чтобы каждую можно было разбить, разделить и победить.
Применение разделяй и властвуй
Использование метода «разделяй и властвуй» для решения проблемы зависит от того, сможем ли мы понять некоторые характеристики метода «разделяй и властвуй»:
- Проблема может быть сужена до определенной степени и решена в более мелкие проблемы.
- После декомпозиции на несколько небольших задач масштаб меньше, а задачи однотипны, в этом случае задача должна быть оптимальной подструктурой.
- Используйте решения подзадач, разложенных по задаче, и объедините их в решение задачи.
- Разложенные подзадачи независимы друг от друга, то есть подзадачи не содержат общих подзадач.
Итак, давайте поговорим об этих особенностях.
❝Первая особенность: вычислительная сложность задачи обычно увеличивается с размером задачи, поэтому большинство задач удовлетворяются.
Вторая особенность: предпосылка применения метода «разделяй и властвуй» состоит в том, чтобы удовлетворить его Вы можете понять, что он в некоторой степени отражает применение рекурсивного мышления.
Третья особенность: это должно быть ключом к методу "разделяй и властвуй". Можно ли использовать проблему, полностью зависит от того, имеет ли проблема третью особенность. Если у нее есть первая и вторая функции, у нее нет третьей функции. Если признаков много, можно рассмотреть жадный метод или метод динамического программирования.
Четвертая особенность связана с эффективностью метода «разделяй и властвуй».Если подзадачи не являются независимыми, метод «разделяй и властвуй» будет выполнять много ненужной работы и многократно решать общие подзадачи.Хотя метод «разделяй и властвуй» может использоваться в настоящее время, он обычно используется.Динамическое программирование лучше.
❞
Чтобы понять особенности метода «разделяй и властвуй», давайте посмотрим, какие классические проблемы решаются с помощью этой идеи👇
Классическая проблема
При каких обстоятельствах вы можете использовать эту идею для ее решения, следующее из контента, собранного в Интернете👇
(1) Бинарный поиск
(2) Умножение больших целых чисел
(3) Умножение матриц Штрассена
(4) Наложение шахматной доски
(5) Сортировка слиянием
(6) Быстрая сортировка
(7) Выбор линейного времени
(8) Задача о паре ближайших точек
(9) Расписание круговой системы
(10) Ханойская башня
Что я хочу отметить, так это сортировку слиянием (слиянием), которая завершает идею метода разделяй и властвуй,分解大问题，解决各个规模小问题，最后合并, то давайте взглянем на код сортировки слиянием (слиянием)👇
Что касается идеи сортировки слиянием, то как она реализована?Как упоминалось в предыдущей главе о сортировке, принята идея разделяй и властвуй.Вы можете посмотреть, как она реализована.Здесь подробно описывать не буду.
2 примера
Далее давайте возьмем три темы в качестве примеров, чтобы увидеть, как использовать идею «разделяй и властвуй» для решения проблем👇
Максимальная сумма субзаказа ⭐
❝Связь:максимальная сумма подзаказа
❞
Учитывая целочисленный массив nums, найдите непрерывный подмассив с наибольшей суммой (подмассив содержит хотя бы один элемент) и верните его наибольшую сумму.
Пример:
❝Ввод: [-2,1,-3,4,-1,2,1,-5,4] Выход: 6
Объяснение: максимальная сумма последовательных подмассивов [4,-1,2,1] равна 6.
❞
❝Передовой:
Если вы уже реализовали решение O(n), попробуйте более тонкое решение «разделяй и властвуй».
❞
Источник: LeetCode Ссылка: https://leetcode-cn.com/problems/maximum-subarray Авторские права принадлежат Lingkou Network. Для коммерческих перепечаток, пожалуйста, свяжитесь с официальным авторизацией, а для некоммерческих перепечаток, пожалуйста, укажите источник.
Во-первых, давайте посмотрим, сможем ли мы решить эту задачу со сложностью O(n).На самом деле, если мы хорошенько об этом подумаем, мы можем использовать простой
Что еще более важно, давайте попробуем решить эту проблему с помощью метода «разделяй и властвуй». Для максимальной суммы подпорядков массива его вклад в ответ может быть только в следующих ситуациях👇
- появиться слева
- появляется в правой половине
- Появитесь в середине, пройдите через середину.
Так можем ли мы обрабатывать его рекурсивно? Для ответов, которые появляются слева и справа, мы можем рассматривать их как ситуацию, а затем обрабатывать их рекурсивно. Конечно, рекурсивный выход, очевидно, когда рекурсивный массив Когда длина равно 1, нам нужно закончить рекурсию.
Для случая, который появляется в среднем ответе, мы можем вычислить ответ через вычисление, так что идея ясна, далее, давайте посмотрим, как писать👇
Конечно, эта проблема лучше решается с динамическими программированными идеями, и это легче понимать👇
❝//dp[i] представляет наибольшую сумму подзаказа, оканчивающуюся на nums[i] в nums
❞
Поиск 2D Matrix II⭐⭐
❝Связь:Поиск 2D Matrix II
❞
Напишите эффективный алгоритм для поиска в матричной матрице m x n целевого значения. Эта матрица обладает следующими свойствами:
Элементы каждой строки расположены в порядке возрастания слева направо. Элементы каждого столбца располагаются в порядке возрастания сверху вниз. Пример:
Существующая матричная матрица выглядит следующим образом:
❝[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
❞
заданная цель =5,вернутьtrue.
заданная цель =20,вернутьfalse.
Источник: LeetCode Ссылка: https://leetcode-cn.com/problems/search-a-2d-matrix-ii Авторские права принадлежат Lingkou Network. Для коммерческих перепечаток, пожалуйста, свяжитесь с официальным авторизацией, а для некоммерческих перепечаток, пожалуйста, укажите источник.
Название этого вопроса очень понятно 👉 Каждая строка матрицы находится в порядке возрастания слева направо, и каждый столбец также в порядке возрастания сверху вниз Найдите определенное число в матрице.
Конечно, у нас есть простая идея👇
- Поддерживать два указателя (строка, столбец), когда целевой элемент найден, мы возвращаем значение true
- Когда значение текущего элемента, на который указывает, меньше целевого, мы выполним col++ и переместимся на одну строку вверх.
- Если текущее значение больше, чем текущая цель, мы строим-- и перемещаем один столбец влево.
- Зная строку col > matrix или строку
Временная сложность: O(n+m)
- Ключ к анализу временной сложности заключается в том, чтобы заметить, что на каждой итерации (мы не возвращаем true) строка или столбец уменьшаются/увеличиваются ровно один раз.
- Поскольку строки могут быть уменьшены только m раз, а столбцы могут быть увеличены только n раз, цикл не может выполняться более n+m раз, прежде чем цикл while завершится.
- Поскольку вся остальная работа постоянна, общая временная сложность линейна по сумме размеров матрицы.
Согласно приведенному выше псевдокоду, мы можем в принципе решить эту проблему👇
Это решение простое и понятное, на самом деле это не дихотомия в прямом смысле, а просто особый метод поиска для выполнения матричного поиска в соответствии с особенностями данных.
Поскольку одномерный массив ищет определенное значение, мы можем уменьшить сложность доlogУровневая временная сложность, так что в двумерном случае мы тоже можем рассматривать это так?
Эту идею можно почерпнуть из 👇
- Мы можем перебрать диагональ матрицы, выполнить бинарный поиск по этим строкам и столбцам, разрезать их.
- Итерировать по диагонали, строкам и столбцам бинарного поиска, пока элементы итерации по диагонали не будут израсходованы (на этот раз вы можете вернуть true или false)
Проще говоря, идея бинарного поиска заключается в поиске строк и столбцов по диагонали.
Вы можете узнать из кода, и вы поймете, как использовать диагональ матрицы, чтобы разделять и властвовать.
Если вы имеете четкое представление о методе «разделяй и властвуй», имеете определенное представление о его особенностях и понимаете, как использовать его для решения практических задач, то, возможно, в этом и заключается смысл этой статьи~
Резюме тем
Тем не так много, но для базового метода входа разделяй и властвуй это должно быть хорошим выбором👇
❤️ Всем спасибо
Если вы считаете этот контент полезным:
- Поставьте лайк и поддержите его, чтобы больше людей увидело этот контент
- Обратите внимание на публичный аккаунт"Интерфейс UpUp", свяжитесь с автором 👉"DayDay2021", мы учимся вместе и прогрессируем вместе.
- Если вы считаете, что это хорошо, вы также можете прочитать последние статьи TianTian (спасибо за вашу поддержку и поддержку 🌹🌹🌹):
- «Алгоритмы и структуры данных» Карта мозга показывает красоту алгоритмов динамического программирования.(370+👍)
- «Алгоритмы и структуры данных» Красота алгоритмов DFS и BFS(240+👍)
- "Алгоритмы и структуры данных" разобраться 6 алгоритмов сортировки(220+👍)
- «Алгоритмы и структуры данных» покажут вам красоту хеш-алгоритмов (210+👍)
- «Алгоритмы и структуры данных» покажут вам красоту алгоритмов поиска с возвратом (190+👍)
В этой статье используетсяmdniceнабор текста