Ага, и по этой же причине в разных языках 11 и 12 отдельные слова, а не teens
Разве по этой?
Порридж В Ко-ливинге
Viktor
А, древний Научпоп? 🤣
Типа того. Там есть и довольно хардкорные вещи, но стиль изложения именно такой как и должно быть построено все образование.
Порридж В Ко-ливинге
Ага, и по этой же причине в разных языках 11 и 12 отдельные слова, а не teens
Eleven and twelve come from the Old English words endleofan and twelf, which can be traced back further to a time when they were ain+lif and twa+lif.
Порридж В Ко-ливинге
Просто дань традициям 🤣
Viktor
Но пальцев десять, так что нет в итоге.
Viktor
В шведском, вон пишут, что для 70 есть отдельное слово которое дословно значит «полпути до 140»
Viktor
И в разных языках полно подобных примеров
Viktor
Дань традициям. Это верно.
Порридж В Ко-ливинге
Всяко лучше чем французское four twenty ten nine
Viktor
А, ну прикольно как развлечение, но думаю 46 немного старовато для математики. 70ые хотя бы 😆
В этом прелесть математики. Что правильно, то правильно и не может устареть 😊
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Делаете сайт, а клинет жалуется на “семь десят”, ЧТО ТАКОЕ Семь десят, где Шесть десят десять!?
Порридж В Ко-ливинге
https://leetcode.com/problems/find-peak-element/
Порридж В Ко-ливинге
Почему столько дизлайков?
V
Порридж В Ко-ливинге
Я в шоке
Порридж В Ко-ливинге
m = l + (r - l) // 2
Dmitry
Тебя какой из вариантов возмущает?)
Порридж В Ко-ливинге
Только RAM
Evgeniy
Если тип числа позволяет, то можно и второй вариант использовать
Evgeniy
с динамической типизацией об этом не задумываешься
Evgeniy
в джаве до какой-то версии даже был баг в реализации бинарного поиска
Evgeniy
потом поправили
Порридж В Ко-ливинге
Ну у меня щас тесты прошли на литкоже
Evgeniy
с каким вариантом?
Порридж В Ко-ливинге
Я думал что может единичка теряться
Evgeniy
Тесты литкода не очень
Порридж В Ко-ливинге
Ну там 1 // 2 + 3 // 2 == 1 а не 2
Evgeniy
Для нечетных чисел может потеряться
Порридж В Ко-ливинге
Для нечетных чисел может потеряться
Да, но это не страшно, т.к. бесконечного loop не будет, а для бинарного поиска не важно, число левее или число правее проверять, главное O(log N)
Evgeniy
В случае поиска да
Порридж В Ко-ливинге
В случае поиска да
В таком варианте не страшно
while l < r:
m = l // 2 + r // 2
if nums[m] < target:
l = m + 1
else:
r = m
Порридж В Ко-ливинге
В случае поиска да
А в таком будет бесконечный loop
while l < r:
m = l // 2 + r // 2 # надо добавить + 1 чтобы не было endless loop
if nums[m] <= target:
l = m
else:
r = m - 1
Evgeniy
Поэтому лучше, чтобы не ошибиться, использовать тот вариант
Порридж В Ко-ливинге
Поэтому лучше, чтобы не ошибиться, использовать тот вариант
Ну, да. но он плохо читаемый 😅
Порридж В Ко-ливинге
l+(r-l)//2
Порридж В Ко-ливинге
Кстати, я делаю список задач со сложностями их оптимального решения, где это оптимальное решение сложно найти. Ну, как будто для олимпиандного программирования
Порридж В Ко-ливинге
Кому нибудь интересно что я пока накопал?
Viktor
Конечно. Выкладывай в паблик.
Порридж В Ко-ливинге
Ну вот пока предварительный список
Порридж В Ко-ливинге
O(N) O(N) https://leetcode.com/problems/implement-strstr/
O(N) O(N) https://leetcode.com/problems/longest-palindromic-substring/
O(log N) O(1) https://leetcode.com/problems/find-peak-element/
O(N) O(1) https://leetcode.com/problems/kth-largest-element-in-an-array/
Порридж В Ко-ливинге
Ну, наверное с peak-element я погоречился
Порридж В Ко-ливинге
Оно немного очевидное решение
Viktor
заведи публичный гугл спредшит, можно потихоньку там собирать
Порридж В Ко-ливинге
O(N) O(N) https://leetcode.com/problems/implement-strstr/
O(N) O(N) https://leetcode.com/problems/longest-palindromic-substring/
O(log N) O(1) https://leetcode.com/problems/find-peak-element/
O(N) O(1) https://leetcode.com/problems/kth-largest-element-in-an-array/
@vitkarpov посмотрите 3ю задачку, она же вроде не сложная за O(log N)?
Порридж В Ко-ливинге
Ну, когда у вас время будет
Порридж В Ко-ливинге
https://docs.google.com/spreadsheets/d/1A7vhMkIpr7a0334X36Weon0pOdtuFsuMdLvP1RJVIQo/edit?usp=sharing
Viktor
@vitkarpov посмотрите 3ю задачку, она же вроде не сложная за O(log N)?
Да, это классический двоичный поиск. По идее, это изи.
Порридж В Ко-ливинге
Да, это классический двоичный поиск. По идее, это изи.
А что бы вы в проверну поставили бы там?
Порридж В Ко-ливинге
Ну, по какому параметру определять, налево или вправо
Viktor
М? Там функция либо возрастает либо убывает
Viktor
Отсюда возможность сравнивать: попал в возрастающий интервал — иди направо, в убывающий — налево.
Viktor
Или о чем вопрос? 😃
Viktor
Я кажись делал разбор этой задачи ещё в первом цикле разборов. В ноушене который.
Viktor
Никто не читает разборы задач 🤣
Viktor
https://www.notion.so/Peak-Index-in-a-Mountain-Array-de355555babb4d63898aa70e05ed20a6
Viktor
хотя это другая задачка
Viktor
но что-то мне подсказывает, по условию, что решается она так же
Evgeny