#algorithm #search #binary-search
#алгоритм #Поиск #двоичный поиск
Вопрос:
в последнее время я играю с алгоритмом бинарного поиска. Я предпочитаю классический шаблон, начиная с while lo lt; hi .
В этот день я столкнулся с вопросом, который еще больше сбивает меня с толку. Проблема с кодом leet заключается в том, что задан целочисленный массив лент, где ленты[i] представляют длину i-й ленты и целое число k. Вы можете разрезать любую ленту на любое количество сегментов целочисленной положительной длины или вообще не выполнять разрезы. Цель состоит в том, чтобы получить k лент одинаковой целочисленной положительной длины. Вам разрешается выбросить любую лишнюю ленту в результате резки. Возвращает максимально возможную целочисленную положительную длину, из которой вы можете получить k лент, или 0, если вы не можете получить k лент одинаковой длины. Примером ввода и вывода является :
Input: ribbons = [7,5,9], k = 4 Output: 4 Этот код может возвращать желаемый результат, и он использует более высокий средний:
class Solution(object): def maxLength(self, ribbons, k): s = sum(ribbons) if s//k == 0: return 0 lo, hi = 1, s//k def bs(cut): return sum([r//cut for r in ribbons]) gt;= k while lo lt; hi: mid = (lo hi 1)//2 if bs(mid): lo = mid else: hi = mid-1 return lo Этот код также может дать правильный ответ, но используйте нижний средний:
class Solution(object): def maxLength(self, ribbons, k): s = sum(ribbons) if s lt; k: return 0 def bs(cut): return sum([r // cut for r in ribbons]) gt;= k lo, hi = 1, s//k while lo lt;= hi: mid = (lo hi) // 2 if bs(mid): lo = mid 1 else: hi = mid - 1 return hi Мой вопрос в том, как решить, когда использовать верхнюю или нижнюю середину? В каком случае lo или должно hi быть возвращено? Это действительно сбивает меня с толку. Любая помощь будет признательна.
Ответ №1:
Одна из ваших реализаций нарушена 🙂
В конечном счете, выбор округления mid в меньшую или большую сторону зависит от того, есть ли у вас слишком низкий чек или слишком высокий чек.
В вашем случае bs(mid) это слишком высокий чек, поэтому ваш if должен выглядеть так:
if bs(mid): # not too high (correct answer is gt;=) lo = mid else # too high (correct answer is lt;) hi = mid-1 Поскольку у вас слишком высокий чек, возможными следующими границами являются mid и mid-1 . Если бы у вас был слишком низкий чек, то возможности были бы mid 1 и mid .
Чтобы гарантировать, что диапазон уменьшается с каждой итерацией (избегает бесконечного цикла), и это lo lt;= hi всегда, вам это необходимо lo lt;= mid-1 lt; mid lt;= hi . Учитывая это lo lt; hi , это гарантируется mid = lo (hi-lo 1)//2 — округлением.
Если бы у вас был слишком низкий чек, вам бы это потребовалось lo lt;= mid lt; mid 1 lt;= hi . С lo lt; hi , что гарантировано mid = lo (hi-lo)//2 .