За последние 19 дней я обязательно решаю хотя бы проблему в день. Я застрял в оптимизации проблемы с именем Rotate Array вчера. И, в результате, не мог решить проблему, не мог написать. Я все еще застрял в той же проблеме. Между тем я решил новый.
Фон
Это заявление о проблеме является частью карты изучения LeetCode под названием «Двоичный поиск». Под подзаголовкой бинарный поиск шаблона-I.
Постановка задачи
Мы играем в игру угадателя. Игра выглядит следующим образом: я выбираю число от 1 до n. Вы должны догадаться, какой номер я выбрал. Каждый раз, когда вы не тогаете, я скажу вам, стоит ли номер выше или ниже. Вы называете заранее определенный API Guess (INT NUM), который возвращает 3 возможных результата (-1, 1 или 0):
-1 : My number is lower 1 : My number is higher 0 : Congrats! You got it!
Пример
Input: n = 10, pick = 6 Output: 6
Подход решения
- Начать, + 1. (См. Заявление о проблеме. Числа от 1 до n. Следовательно, убедитесь, что оба включены).
- Рассчитайте середину. ((Старт + конец)/2)
- Теперь пропустите MID в качестве параметра к API Угадай.
- Разделите список на основе значения, возвращаемой API.
# The guess API is already defined for you. # @param num, your guess # @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 # def guess(num: int) -> int: class Solution: def guessNumber(self, n: int) -> int: start = 1 end = n+1 while start < end: mid = int((start+end)/2) if guess(mid) == -1: end = mid elif guess(mid) == 1: start = mid + 1 elif guess(mid) == 0: return mid return -1
Учащиеся
- Сложность времени вышеуказанного решения – O (logn).
- Когда в заявлении о проблеме уже упоминается, отсортированная массив думать двоичный поиск.
- Сложность времени двоичного поиска – O (logn). Сложность времени линейного поиска – O (n). Двоичный поиск более эффективен.
Оригинал: “https://dev.to/mridubhatnagar/day-21-guess-number-higher-or-lower-2ofk”