LeetCoding — различия между версиями
(Студент выбрал задачу) |
(→Medium) |
||
Строка 265: | Строка 265: | ||
{{leetcode|minimum-add-to-make-parentheses-valid|Minimum Add to Make Parentheses Valid|[[Участник:StasFomin|StasFomin]] 13:02, 9 декабря 2019 (MSK)}} [[Участник:Danillich/MinimumAddToMakeParenthesisValid|Danillich/MinimumAddToMakeParenthesisValid]] | {{leetcode|minimum-add-to-make-parentheses-valid|Minimum Add to Make Parentheses Valid|[[Участник:StasFomin|StasFomin]] 13:02, 9 декабря 2019 (MSK)}} [[Участник:Danillich/MinimumAddToMakeParenthesisValid|Danillich/MinimumAddToMakeParenthesisValid]] | ||
− | [[Участник:PinkHedgehog|PinkHedgehog]] 11:17, 20 апреля 2020 (MSK){{leetcode|partition-labels|Partition Labels|}} | + | [[Участник:PinkHedgehog|PinkHedgehog]] 11:17, 20 апреля 2020 (MSK){{leetcode|partition-labels|Partition Labels|}}[[Участник:PinkHedgehog/partition-labels-in-rust]] |
== Вероятностные алгоритмы == | == Вероятностные алгоритмы == |
Версия 18:25, 23 апреля 2020
Выбрав задау, подпишите сбоку четыремя тильдами «~~~~», это раскроется в вашу подпись (ссылку на вашу страницу) и будет означать, что вы ее застолбили за собой. Когда будет решение — добавьте вместо него ссылку. Решение оформлять на подстраницах личной страницы.
Обычно, за решение дается 4 очка, но внутри одной темы, все они суммируются по «очень научной формуле» , где — эти самые 4 очка, но возможно будут и более легкие задачи по 3 очка. Т.е. выгодно решить несколько задач в каждой из тем, вместо того, чтобы выгрызать только одну тему, насобачившись решать определенные задачи.
Зеленой строчкой покрашено проверенное и учтенное решение (проверяю регулярно).
Обратите внимание — решение должно проходить все тесты, т.е. вы должны нажать кнопку «Submit», а не только кнопку «Run Code» которая запускает один тест (или выбранные вами входные данные). Ну и в коде не должно быть адовых хаков в духе
if input = UglyTestCaseICannotHandleButIKnowAnswer: return KnownAnswerForThisCase
Содержание
Динамическое программирование
Gerakir 16:09, 27 февраля 2020 (MSK)
«Shortest Subarray with Sum at Least K»
Участник:Лукьянов_Кирилл/Shortest_Subarray_with_Sum_at_Least_K 12:34, 20 марта 2020 (MSK)
«Best Time to Buy and Sell Stock IV»
Froyg 04:15, 4 апреля 2020 (MSK) http://discopal.ispras.ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Froyg/_ds
Лукьянов Кирилл 22:11, 19 марта 2020 (MSK)
«Largest Component Size by Common Factor»
«Word Break II» Rashit Abdullin 19:18, 4 марта 2020 (MSK)
«Department Top Three Salaries»
«Numbers At Most N Given Digit Set» Plague rat 13:57, 5 декабря 2019 (MSK)
Alvant/TaskCandy
Жадные алгоритмы
Vkozin 17:17, 11 ноября 2019 (MSK)
«IPO»
Vkozin 19:27, 11 ноября 2019 (MSK)
Medium
По два балла за.
Danillich/Jumpgame
Участник:Лукьянов_Кирилл/Gas_Station 02:31, 21 марта 2020 (MSK)
StasFomin 20:23, 20 декабря 2019 (MSK): «Time Limit Exceeded». Похоже у вас там квадратичная сложность, а тут жадный, наверняка ждут сортировку и линейное (nlogn) время.
«Reconstruct a 2-Row Binary Matrix»
Участник:Лукьянов Кирилл/Reconstruct a 2-Row Binary Matrix 12:38, 20 марта 2020 (MSK)
«Split Array into Consecutive Subsequences»
Участник:Лукьянов_Кирилл/Split_Array_into_Consecutive_Subsequences 14:54, 20 марта 2020 (MSK)
DChulkov 02:07, 19 марта 2020 (MSK)
«Minimum Domino Rotations For Equal Row»
Участник:Лукьянов Кирилл/Minimum Domino Rotations For Equal Row 12:38, 20 марта 2020 (MSK)
«Queue Reconstruction by Height» Alexander Denisenko/reconstruct_queue
«Maximum Nesting Depth of Two Valid Parentheses Strings»
Участник:Лукьянов Кирилл/Score After Flipping Matrix 12:38, 20 марта 2020 (MSK)
PinkHedgehog 11:17, 20 апреля 2020 (MSK)----
«Partition Labels» Участник:PinkHedgehog/partition-labels-in-rust
Вероятностные алгоритмы
Графы
«Redundant Connection II» Участник:Hellhoundmipt/redundant-connection-ii
- StasFomin 09:12, 27 ноября 2019 (MSK): Гм. тесты не проходит. Нужна отладка... Напишите ниже, когда будет готово к проверке.
"abcdefabcdefabcdef" "edcfbebceafcfdabad"
приезжает в ответ 11 вместо 10. Баг ли это движка LeetCode или где-то незаметная рандомизация? Все еще интересно.
Да, Стас, похоже, дело в движке. Рандомизация может возникать из-за того, что при нахождении циклов из символов строк буквы строки А перебираются как элементы множества:
vertices = set(A) <...> for v in vertices: <...>
Запустил у себя на машине 1000 раз поиск решения для тех двух строк выше, на которых в LeetCode иногда падает, и все 1000 раз решение оказывалось верным (k = 10). Если же сделать порядок перебора символов однозначным
for v in sorted(vertices): <...>то ни разу из 1000 запусков не удаётся получить ответ 10 — всегда 11.
В общем, выходит, это не баг, а особенность Питона, который там в LeetCode — или, наоборот, того, который у меня :).
Элементы ведь во множестве не упорядочены, поэтому в принципе может получаться от раза к разу по-разному.
Хм. Да, странно. Элементы могут по-разному упорядочиваться в зависимости от Питона, но на одной и той же машине порядок должен получаться всегда одинаковый.
А на LeetCode когда как.
Или тогда дело в системе запуска тестов: у них, наверно, много машин, где всё запускается, и тест прогоняется на той, что ему достанется.
Получается, случайность может быть не только в коде :)
Medium
По два бала за.
«Shortest Path with Alternating Colors»
Plague rat 19:00, 4 декабря 2019 (MSK)
Hellhoundmipt 22:20, 16 декабря 2019 (MSK)
«Number of Connected Components in an Undirected Graph»