LeetCoding

Материал из DISCOPAL
Перейти к: навигация, поиск

Выбрав задау, подпишите сбоку четыремя тильдами «~~~~», это раскроется в вашу подпись (ссылку на вашу страницу) и будет означать, что вы ее застолбили за собой. Когда будет решение — добавьте вместо него ссылку. Решение оформлять на подстраницах личной страницы.

Обычно, за решение дается 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


«Word Ladder II»

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


«Create Maximum Number»

Larin.dv 11:24, 30 апреля 2020 (MSK)

«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


«Trips and Users»

Froyg/trips and users 20:08, 24 апреля 2020 (MSK)

«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


«Count The Repetitions»

Лукьянов Кирилл 22:11, 19 марта 2020 (MSK)

«Largest Component Size by Common Factor»

S1td1kov 02:59, 24 апреля 2020 (MSK)



«Largest Palindrome Product»

S1td1kov 02:59, 24 апреля 2020 (MSK)

«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»

Froyg/top 3 salaries 20:49, 24 апреля 2020 (MSK)

«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


«Candy» Проверено StasFomin 17:15, 25 октября 2019 (MSK)
Alvant/TaskCandy


«Cat and Mouse»

Larin.dv 11:28, 30 апреля 2020 (MSK)

«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


«Create Maximum Number»

Rashit Abdullin 02:04, 24 апреля 2020 (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»

Froyg/IPO 16:20, 24 апреля 2020 (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


«Jump Game» Проверено StasFomin 12:24, 9 декабря 2019 (MSK)
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»

Участник:Лукьянов_Кирилл/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)


«Reorganize String»

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


«Way to Form String»

S1td1kov 02:09, 24 апреля 2020 (MSK)



«Largest Values From Labels»

PinkHedgehog 20:28, 23 апреля 2020 (MSK)



«Queue Reconstruction by Height»

Larin.dv 11:32, 30 апреля 2020 (MSK)

«Maximum Nesting Depth of Two Valid Parentheses Strings»

Larin.dv 11:32, 30 апреля 2020 (MSK)

«Score After Flipping Matrix»

Участник:Лукьянов Кирилл/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»

Larin.dv 11:33, 30 апреля 2020 (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



«Is Graph Bipartite?»

Larin.dv 11:37, 30 апреля 2020 (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