Когда мы говорим об алгоритмах, у нас будут общие идеи, такие как рекурсия, динамическое программирование, а также принцип «разделяй и властвуй».

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

разделяй, властвуй, объединяй.

Быстрая сортировка состоит именно из этих трех частей. Если вы забыли быструю сортировку, вот код. Если вы не знаете этот алгоритм, пожалуйста, сначала зайдите на YouTube или Google.

Бинарный поиск состоит всего из двух шагов: разделяй и властвуй. Комбайн не нужен. Здесь приведен пример кода бинарного поиска для угадывания цены товара. В этом примере мы собираемся угадать цену продукта. Нам сказали, что цена находится между 0$ и 1000$. Мы получим обратную связь о том, что наша догадка слишком высока, слишком занижена или верна. Вот код с использованием бинарного поиска.

Сегодня я столкнулся с интересной проблемой от leetcode, он также может использовать идею «разделяй и властвуй». Хочу поделиться решением этой проблемы. Проблема в

1274. Количество кораблей в прямоугольнике.



Вход в учетную запись — LeetCode
Повысьте уровень своих навыков программирования и быстро получите работу. Это лучшее место, чтобы расширить свои знания и подготовиться…leetcode.com



Однако, аналогично бинарному поиску, нам нужно разрезать прямоугольник на 4 части, как показано на рисунке ниже.
Если площадь четверти возвращается как false, что означает отсутствие корабля в этой области, мы можем безопасно вернуть 0
если площадь четверти возвращается как True, мы должны продолжать делить эту область на четыре части для дальнейшего изучения.
В базовом случае верхняя и нижняя точки совпадают, тогда мы можем получить точный результат. Если True, у нас есть один корабль, если False, у нас нет кораблей.

Одна тонкая вещь заключается в том, что для того, чтобы эти четыре части не перекрывались, нам нужно добавить центральную точку на 1, как показано на рисунке.

Вот код

Нетривиальная разделяй и властвуй.

932. Красивый Массив

Говорят, что ее можно решить методом «разделяй и властвуй». Однако это трудно понять. Решение и обсуждение можно найти здесь.



Нечетный + четный шаблон, O(N) — обсуждение LeetCode
Последнее редактирование: 2 августа 2019 г., 5:22, 10,2 тыс. просмотров Попробуйте разделять и властвовать, чтобы у нас было левая часть, правая часть. Один из способов…leetcode.com



Спасибо за чтение.