Leetcode-playground
September 21, 2020 · View on GitHub
Leetcode 👨💻
Leetcode-playground
Leetcode url: https://leetcode.com/nikiforovall/
| # | Title | Solution | Basic idea (One line) |
|---|---|---|---|
| 1 | Two Sum | C# | 1. Hash O(n) and O(n) space. 2. Sort O(n * log n) and search with two points O(n) and O(1) space. |
| 2 | AddTwoNumbers | C# | Traverse single-linked list and do modulo 10 sum |
| 15 | 3Sum | C# | Sort initial array, loop over array and pick current element, solve two-sum problem based on two pointers method for array to the right of current element with target equals to negated value of current element |
| 26 | RemoveDuplicatesFromSortedArray | C# | 1. Two pointers, slow/fast runner approach |
| 27 | RemoveElement | C# | Two pointers, skip element at the end and swap at the start. |
| 35 | SerachInsertPosition | C# | 1. Two pointers, skip element at the end and swap at the start. 2. Two pointers, both start at the beginning result-sub-list pointer and full-scan pointer |
| 69 | SqrtX | C# | Bisection, lazy curr element calculation f(mid) < x < f(mid+1), use division instead of multiplication to speed up calculation |
| 75 | SortColors | C# | Two pointers approach, fill the rest of the array with 1 |
| 88 | MergeSortedArray | C# | 1. Two pointers solution, store pointers to latest not processed in nums1, nums2 (=p,q). Shift nums1[pos..pos+m-p]->1 when item from nums2 is written and update p,q 2. Two pointers solution, start from the end to avoid shift operation |
| 96 | UniqueBinarySearchTrees | C# | Dynamic programming based on catalan number calculation. The goal is to fix one number as root element and calculate number of unique binary trees based on multiplied combinations of subtrees T[i]*T[i - j -1] |
| 130 | SurroundedRegions | C# | Traverse inner part of board and use dfs to check potential candidates for checking, commit if it is a valid group |
| 189 | RotateArray | C# | 1. Shifting with additional O(k) memory 2. Reverse in-place based on pivot element 3. Cyclic replacement |
| 200 | NumberOfIslands | C# | In-place uncheck of not visited islands via DFS/BFS |
| 222 | CountCompleteTreeNodes | C# | Usage of property of complete tree, depending on height of subtree we could determine the part of tree under construction |
| 231 | PowerOfTwo | C# | Bit manipulation |
| 275 | HIndexII | C# | Binary search for first A[mid] >= N - mind, return number of elements to the right of the pointer |
| 278 | FirstBadVersion | C# | Bisection |
| 380 | InsertDeleteGetRandom1 | C# | Maintain map(val -> ind in array) + list, removal is based on swap of last element |
| 414 | ThirdMaximumNumber | C# | Three consecutive counters, stored element shift |
| 485 | ValidateIPAddress | C# | Validation pipeline with the list of heuristics |
| 485 | MaxConsecutiveOnes | C# | Sliding window for non-zero part of array and current sum calculation as index diff |
| 518 | CoinChange2 | C# | Classic DP problem, cache total combinations of previous subproblems in a list |
| 547 | FriendCircles | C# | Checked DFS nodes |
| 904 | FruitIntoBaskets | C# | Sliding window, a bunch of pointers to store consecutive sequence of previous latest element |
| 977 | SquaresOfASortedArray | C# | 1. Merge sort, array with negative numbers is traversed in a reversed manner 2. Two pointers |
| 1004 | MaxConsecutiveOnesIII | C# | Sliding window, remove elements from the tail |
| 1004 | TwoCityScheduling | C# | Greedy solution based on costs difference heuristic + sorting |
| 1114 | DuplicateZeros | C# | Implement array shift starting from the end for each zero element, don't forget to skip updated zero |
| 1114 | FirstInOrder | C# | Event-based blocking ManualResetEventSlim |
| 1115 | PrintFooBarAlternately | C# | Event-based blocking ManualResetEventSlim |
| 1295 | FindNumbersWithEvenNumberOfDigits | C# | Reduce arr item to double digit by dividing by 100 and count |