LeetCoding — различия между версиями
Материал из DISCOPAL
(Студент выбрал задачу) |
(→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
Содержание
Динамическое программирование
«Valid Number»
Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
Alexryabov/TaskValidNumber 03:28, 28 ноября 2019 (MSK)
«Max Points on a Line»
Проверено StasFomin 16:58, 31 октября 2019 (MSK)
F.Nikitin/MaxPointsOnLine
«Strong Password Checker»
Проверено StasFomin 18:34, 7 ноября 2019 (MSK)
Danillich/StrongPasswordChecker
«Find the Closest Palindrome»
Проверено StasFomin 16:05, 22 ноября 2019 (MSK)
Alex.Galtseva/findTheClosestPalindrome
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)
«Wildcard Matching»
Проверено StasFomin 21:57, 12 декабря 2019 (MSK)
Alexander Denisenko/Wildcard_matching
«Longest Duplicate Substring»
Проверено StasFomin 17:02, 31 октября 2019 (MSK)
F.Nikitin/LongestDuplicateSubstring
«Reverse Pairs»
Проверено StasFomin 08:35, 20 декабря 2019 (MSK)
D.feldman/reverse-pairs
«Substring with Concatenation of All Words»
Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
F.Nikitin/FindSubstring
«Text Justification»
Проверено StasFomin 16:57, 13 декабря 2019 (MSK)
ArthurSamuelyan/Text_Justification
«Integer to English Words»
Проверено StasFomin 16:05, 22 ноября 2019 (MSK)
Участник:Polina Potapova/integerToEnglishWords
«Split Array With Same Average»
Проверено StasFomin 22:00, 12 декабря 2019 (MSK)
Alexander Denisenko/split_array_same_average
«Decode Ways II»
Проверено StasFomin 17:02, 13 декабря 2019 (MSK)
ArthurSamuelyan/Decode_Ways_II
«Super Egg Drop»
Проверено StasFomin 19:04, 7 ноября 2019 (MSK)
Alvant/TaskSuperEggDrop
«Regular Expression Matching»
Проверено StasFomin 16:05, 22 ноября 2019 (MSK)
Danillich/RegularExpressionMatching
«Nth Magical Number»
Проверено StasFomin 16:05, 22 ноября 2019 (MSK)
Alexryabov/TaskNthMagicalNumber
«Longest Valid Parentheses»
Проверено StasFomin 19:04, 7 ноября 2019 (MSK)
Danillich/LongestValidParentheses
«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
«Self Crossing»
Проверено StasFomin 17:24, 31 октября 2019 (MSK)
Lenaermakova/Self Crossing
«K-th Smallest in Lexicographical Order»
Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
Участник:Plague_rat/K-th_Smallest_in_LexOrder
«Median of Two Sorted Arrays»
Проверено StasFomin 17:04, 31 октября 2019 (MSK)
F.Nikitin/FindMedianSortedArrays
Лукьянов Кирилл 22:11, 19 марта 2020 (MSK)
«Largest Component Size by Common Factor»
«Reaching Points»
Проверено StasFomin 16:05, 22 ноября 2019 (MSK)
Danillich/ReachingPoints
«Dungeon Game»
Проверено StasFomin 20:23, 20 декабря 2019 (MSK)
Участник:Polina Potapova/dungeon-game 15:20, 17 декабря 2019 (MSK)
«Shortest Palindrome»
Проверено StasFomin 17:21, 31 октября 2019 (MSK)
Lenaermakova/Shotest Palindrome
«Palindrome Partitioning II»
Проверено StasFomin 22:03, 12 декабря 2019 (MSK)
Участник:Plague_rat/Palindrome_Partitioning_II
«Word Break II» Rashit Abdullin 19:18, 4 марта 2020 (MSK)
«Department Top Three Salaries»
«Perfect Rectangle»
Проверено StasFomin 17:08, 31 октября 2019 (MSK)
F.Nikitin/PerfectRectangle
«Jump Game II»
Проверено StasFomin 19:04, 7 ноября 2019 (MSK)
Alexander Denisenko/jump_game_ii Alexander Denisenko 16:22, 1 ноября 2019 (MSK)
«Interleaving String»
Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
Alexryabov/TaskInterleavingString
«Numbers At Most N Given Digit Set» Plague rat 13:57, 5 декабря 2019 (MSK)
«Bricks Falling When Hit»
Проверено StasFomin 17:30, 25 октября 2019 (MSK)
Участник:ArthurSamuelyan/Bricks_Falling_When_Hit
Alvant/TaskCandy
«K Inverse Pairs Array»
Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
Участник:Plague rat/K Inverse Pairs Array
«First Missing Positive»
Проверено StasFomin 20:23, 20 декабря 2019 (MSK)
Участник:Polina Potapova/first-missing-positive 15:23, 19 декабря 2019 (MSK)
«Find K-th Smallest Pair Distance»
Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
Участник:Plague_rat/K-th_Smallest_Pair_Distance
«Sum of Subsequence Widths»
Проверено StasFomin 17:01, 25 октября 2019 (MSK)
Alvant/TaskSumOfSubsequenceWidths
«Minimum Number Of Refueling Stops»
Проверено StasFomin 17:15, 25 октября 2019 (MSK).
Alexryabov/TaskMinimumNumberOfRefuelingStops
«Last Substring in Lexicographical Order»
Проверено StasFomin 17:01, 25 октября 2019 (MSK)
Alvant/TaskLastSubstringInLexicographicalOrder
Жадные алгоритмы
«Wildcard Matching»
Проверено StasFomin 16:14, 22 ноября 2019 (MSK)
F.Nikitin/IsMatch
Vkozin 17:17, 11 ноября 2019 (MSK)
«Jump Game II»
Проверено StasFomin 08:11, 27 ноября 2019 (MSK)
Alexryabov/Taskjumpgameii
«Three Equal Parts»
Проверено StasFomin 08:16, 27 ноября 2019 (MSK)
Alvant/TaskThreeEqualParts
«Course Schedule III»
Проверено StasFomin 08:28, 27 ноября 2019 (MSK)
Alexryabov/TaskCourseScheduleiii Alexryabov 14:26, 12 ноября 2019 (MSK)
«Remove Duplicate Letters»
Проверено StasFomin 09:12, 27 ноября 2019 (MSK)
Alvant/TaskRemoveDuplicateLetters
«Patching Array»
Проверено StasFomin 09:12, 27 ноября 2019 (MSK)
Alexander Denisenko/patching_array
«Stamping The Sequence»
Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
F.Nikitin/MovesToStamp
«Intersection Size At Least Two»
Проверено StasFomin 09:12, 27 ноября 2019 (MSK)
Alexryabov/TaskIntersectionSizeAtLeastTwo
«IPO»
Vkozin 19:27, 11 ноября 2019 (MSK)
«Minimum Number of K Consecutive Bit Flips»
Проверено StasFomin 09:12, 27 ноября 2019 (MSK)
F.Nikitin/MinKBitFlips
«Couples Holding Hands»
Проверено StasFomin 09:12, 27 ноября 2019 (MSK)
Alexryabov 11:47, 10 ноября 2019 (MSK)
Alexryabov/TaskCouplesHoldingHands
Medium
По два балла за.
«Smallest Range II»
Проверено StasFomin 16:29, 16 декабря 2019 (MSK)
D.Feldman/smallest-range-ii
«Remove K Digits»
Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
Danillich/RemoveKDigits
«Delete Columns to Make Sorted II»
Проверено StasFomin 16:29, 16 декабря 2019 (MSK)
ArthurSamuelyan/Delete_Columns_To_Make_Sorted_II
Danillich/Jumpgame
«String Without AAA or BBB»
Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
Alex.Galtseva/StringWithoutAAAandBBB
«Split Array into Fibonacci Sequence»
Проверено StasFomin 16:29, 16 декабря 2019 (MSK)
ArthurSamuelyan/Split_Array_Into_Fibonacci_Sequence
Участник:Лукьянов_Кирилл/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)
«Dota2 Senate»
Проверено StasFomin 20:23, 20 декабря 2019 (MSK)
Участник:Polina Potapova/dota2-senate 23:52, 18 декабря 2019 (MSK)
«Wiggle Subsequence»
Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
Danillich/WiggleSubsequence
«Bag of Tokens»
Проверено StasFomin 16:29, 16 декабря 2019 (MSK)
D.Feldman/bag-of-tokens
«Non-overlapping Intervals»
Проверено StasFomin 16:29, 16 декабря 2019 (MSK)
D.Feldman/non-overlapping-intervals
«Split Array into Consecutive Subsequences»
Участник:Лукьянов_Кирилл/Split_Array_into_Consecutive_Subsequences 14:54, 20 марта 2020 (MSK)
«Monotone Increasing Digits»
Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
Danillich/MonotoneIncreasingDigits
«Broken Calculator»
Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
Danillich/BrokenCalculator
«Advantage Shuffle»
Проверено StasFomin 12:47, 9 декабря 2019 (MSK)
F.Nikitin/AdvantageCount
«Boats to Save People»
Проверено StasFomin 20:23, 20 декабря 2019 (MSK)
Участник:Polina Potapova/boats-to-save-people 18:20, 19 декабря 2019 (MSK)
DChulkov 02:07, 19 марта 2020 (MSK)
«Task Scheduler»
Проверено StasFomin 12:51, 9 декабря 2019 (MSK)
Lenaermakova/Task_Scheduler
«Previous Permutation With One Swap»
Проверено StasFomin 12:53, 9 декабря 2019 (MSK)
Участник:Plague_rat/Previous_Permutation_With_One_Swap
«Minimum Number of Arrows to Burst Balloons»
Проверено StasFomin 12:53, 9 декабря 2019 (MSK)
Участник:Plague_rat/Minimum_Number_of_Arrows_to_Burst_Balloons
«Minimum Domino Rotations For Equal Row»
Участник:Лукьянов Кирилл/Minimum Domino Rotations For Equal Row 12:38, 20 марта 2020 (MSK)
«Best Time to Buy and Sell Stock with Transaction Fee»
Проверено StasFomin 12:56, 9 декабря 2019 (MSK)
Участник:Plague_rat/Best_Time_to_Buy_and_Sell_Stock_with_Transaction_Fee 19:13, 4 декабря 2019 (MSK)
«Car Pooling»
Проверено StasFomin 12:57, 9 декабря 2019 (MSK)
Участник:Plague_rat/Car_Pooling
«Minimum Swaps to Make Strings Equal»
Проверено StasFomin 12:59, 9 декабря 2019 (MSK)
Участник:Plague_rat/Minimum_Swaps_to_Make_Strings_Equal
«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)
«Minimum Add to Make Parentheses Valid»
Проверено StasFomin 13:02, 9 декабря 2019 (MSK)
Danillich/MinimumAddToMakeParenthesisValid
PinkHedgehog 11:17, 20 апреля 2020 (MSK)----
«Partition Labels» Участник:PinkHedgehog/partition-labels-in-rust
Вероятностные алгоритмы
«Random Pick with Blacklist»
Проверено StasFomin 09:12, 27 ноября 2019 (MSK)
F.Nikitin/RandomPickWithBlacklist
«Implement Rand10() Using Rand7()»
Проверено StasFomin 19:04, 7 ноября 2019 (MSK)
Alvant/TaskImplementRand10UsingRand7
«Random Pick with Weight»
Проверено StasFomin 09:12, 27 ноября 2019 (MSK)
F.Nikitin/RandomPickWithWeight
«Random Flip Matrix»
Проверено StasFomin 09:12, 27 ноября 2019 (MSK)
Alvant/TaskRandomFlipMatrix
«Random Point in Non-overlapping Rectangles»
Проверено StasFomin 19:04, 7 ноября 2019 (MSK)
Random Point in Non-overlapping Rectangles Lenaermakova 01:09, 7 ноября 2019 (MSK)
«Generate Random Point in a Circle»
Проверено StasFomin 13:10, 9 декабря 2019 (MSK)
Alex.Galtseva/GenerateRandomPointsInCircle
Графы
«Redundant Connection II» Участник:Hellhoundmipt/redundant-connection-ii
- StasFomin 09:12, 27 ноября 2019 (MSK): Гм. тесты не проходит. Нужна отладка... Напишите ниже, когда будет готово к проверке.
«K-Similar Strings»
Проверено StasFomin 19:04, 7 ноября 2019 (MSK)
Alvant/TaskKSimilarStrings Там же нет вероятностных алгоритмов, интересно. +4 бала за ресерч.
Конкретно, иногда на
"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 когда как.
Или тогда дело в системе запуска тестов: у них, наверно, много машин, где всё запускается, и тест прогоняется на той, что ему достанется.
Получается, случайность может быть не только в коде :)
«Minimize Malware Spread II»
Проверено StasFomin 09:12, 27 ноября 2019 (MSK)
F.Nikitin/MinMalwareSpread
«Sort Items by Groups Respecting Dependencies»
Проверено StasFomin 13:13, 9 декабря 2019 (MSK)
Danillich/SortItemsbyGroupsRespectingDependencies
«Number of Squareful Arrays»
Проверено StasFomin 09:12, 27 ноября 2019 (MSK)
F.Nikitin/NumSquarefulPerms
«Couples Holding Hands»
Проверено StasFomin 09:12, 27 ноября 2019 (MSK)
F.Nikitin/MinSwapsCouples
Medium
По два бала за.
«Clone Graph»
Проверено StasFomin 13:15, 9 декабря 2019 (MSK)
F.Nikitin/CloneGraph
«Minimum Height Trees»
Проверено StasFomin 13:23, 9 декабря 2019 (MSK)
F.Nikitin/FindMinHeightTree
«Reconstruct Itinerary»
Проверено StasFomin 20:23, 20 декабря 2019 (MSK)
Участник:Polina Potapova/reconstruct-itinerary 21:20, 19 декабря 2019 (MSK)
«Shortest Path with Alternating Colors»
Plague rat 19:00, 4 декабря 2019 (MSK)
«Course Schedule II»
Проверено StasFomin 13:26, 9 декабря 2019 (MSK)
Участник:Plague_rat/Course_Schedule_II
«Course Schedule»
Проверено StasFomin 13:26, 9 декабря 2019 (MSK)
Участник:Plague_rat/Course_Schedule
«As Far from Land as Possible»
Проверено StasFomin 20:23, 20 декабря 2019 (MSK)
Участник:Polina Potapova/as-far-from-land-as-possible 02:50, 18 декабря 2019 (MSK)
«Satisfiability of Equality Equations»
Проверено StasFomin 16:29, 16 декабря 2019 (MSK)
Участник:D.feldman/satisfiability-of-equality-equations
«Network Delay Time»
Проверено StasFomin 13:26, 9 декабря 2019 (MSK)
Участник:Plague_rat/Network_Delay_Time
Hellhoundmipt 22:20, 16 декабря 2019 (MSK)
«Find Eventual Safe States»
Проверено StasFomin 16:53, 26 декабря 2019 (MSK)
Участник:Alexander Denisenko/Eventual safe states
«Evaluate Division»
Проверено StasFomin 16:29, 16 декабря 2019 (MSK)
Участник:Alexander Denisenko/evaluate-division
«Number of Connected Components in an Undirected Graph»
«Redundant Connection»
Проверено StasFomin 20:23, 20 декабря 2019 (MSK)
Участник:Polina Potapova/redundant-connection 20:10, 18 декабря 2019 (MSK)
«Count Servers that Communicate»
Проверено StasFomin 13:28, 9 декабря 2019 (MSK)
Участник:Plague_rat/Count_Servers_that_Communicate
«Keys and Rooms»
Проверено StasFomin 13:30, 9 декабря 2019 (MSK)
Участник:Plague_rat/Keys_and_Rooms
«Partition Array for Maximum Sum»
Проверено StasFomin 17:14, 13 декабря 2019 (MSK)
ArthurSamuelyan/Partition_Array_For_Maximum_Sum
«Regions Cut By Slashes»
Проверено StasFomin 17:14, 13 декабря 2019 (MSK)
ArthurSamuelyan/Regions_Cut_By_Slashes
«Maximum Level Sum of a Binary Tree»
Проверено StasFomin 13:33, 9 декабря 2019 (MSK)
Lenaermakova/_Maximum_Level_Sum_of_a_Binary_Tree