【Ежедневный алгоритм проверки】LCS 01. Загрузите плагин

искусственный интеллект
【Ежедневный алгоритм проверки】LCS 01. Загрузите плагин

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

【Ежедневные пробные серии】LeetCode200 простых вопросов

Описание темы

Сяокоу намерен отдать его себеVS codeПосле установки и использования плагинов пропускная способность может загружать 1 плагин в минуту в исходном состоянии. Предположим, что каждую минуту выбирается одна из следующих двух стратегий:

  • Скачать плагин, используя текущую пропускную способность
  • Удвойте пропускную способность (а вместе с ней и количество загруженных плагинов)

Пожалуйста, вернитесь к кнопке, чтобы завершить загрузкуnСколько минут плагин занимает хотя бы.

Примечание. Фактическое количество загруженных плагинов может превышатьnКусок

Пример 1:

Вход: n = 2
выход: 2


объяснять:
Следующие два решения могут загрузить 2 плагина в течение 2 минут.
Вариант 1: удвоить пропускную способность в первую минуту, и пропускная способность позволяет загружать 2 подключаемых модуля в минуту; загружать 2 подключаемых модуля во вторую минуту
Вариант 2. Загрузите 1 плагин в первую минуту и ​​загрузите 1 плагин во вторую минуту.

Пример 2:

Вход: n = 4

выход: 3

объяснять:
На загрузку 4-х плагинов уходит не менее 3 минут, один из вариантов следующий:
Пропускная способность удваивается в течение первой минуты, и пропускная способность позволяет загружать 2 плагина в минуту;
Загрузите 2 плагина на второй минуте;
Загрузите 2 плагина на третьей минуте.

намекать

  • 1 <= n <= 10^5

Идеи решения проблем

Я прочитал вопрос 3 раза, но не понял, что он означает, поэтому проверил самn = 8, результат равен 4, и я это понимаю моментально. Перепишите вопрос еще раз, чтобыn = 8Например:

  • Пропускная способность удваивается в первую минуту, и в настоящее время можно загрузить 2 одновременно.
  • Пропускная способность удваивается на второй минуте, и в настоящее время можно загрузить 4 одновременно.
  • Пропускная способность удваивается на третьей минуте, и в настоящее время он может загружать 8 за раз.
  • Загрузите 8 плагинов за четвертую минуту.

Ключ к решению проблемы - удваивать все время, прежде чем его можно будет загрузить за один раз, пока一次下载数量 >= n, поэтому время минимально, идея понятна, а код очень прост в реализации.

def leastMinutes(self, n):
    """
    :type n: int
    :rtype: int
    """
    res = 0
    while 2**res < n:
        res += 1
    return res + 1

Сегодняшняя регистрация завершена, текущий прогресс — 2/200.

Категории