Please enable JavaScript.
Coggle requires JavaScript to display documents.
sorting and searching, Graphs, BinarySearchTree, Backtracking backtracking…
sorting and searching
binary search
ліва позиція = 0; права = розміру масиву-1
в циклі поки ліва менша за праву
якщо таргет > середину ----
ліва = середина+1
якщо таргет < середину ---
права = середина
шукаємо індекс середини між лівою і правою
маємо масив відсортов
якщо лівий не дорівн довжині масиву і лівий елем == таргету то - поверт - лівий індекс або -1
код -
https://leetcode.com/problems/binary-search/description/
знайти поціцію першого(останнього) входження елементу в масив відсортов
перше - lower bound
код = binary search
останнє - upper bound
код = binary search, але перевірка така якщо таргет >= середину
якщо лівий не дорівн нулю і лівий елем-1 == таргету то - поверт - лівий-1 індекс або -1
код
Minimum Limit of Balls in a Bag
код
в основі бінарний пошук
беремо число - представл його у вигляді масиву від 1 до числа
шукаємо середину - це і буде максимал знач пеналті і підраховуємо скільки дій нам потрібно зробити, щоб отримати це максимал знач
робимо це в циклі і беремо те знач що відповід к-ті макс операцій
є масив(торби з кульками) і є макс к-ть операцій
Kth Largest Element in an Array
код
використ quick sort, але сортуємо не до кінця, постійно перевіряємо чи елемент знаходиться на необхіній нам позиції, якщо так - не продовж сортування
Merge Intervals
код
споч сортуємо
потім запис в новий інтервал - перший, в циклі перевіряємо чи новий[1] > поточнйи[0], якщо так то в новий[1] записуємо макс з нового[1] і поточнйи[1], якщо ні - новий інтервал = поточ
запис в результ арей
додаємо в результ арей останній новий інтервал
конверт арей у матрицю
Graphs
Critical Connections in a Network
code
Tarjan's Bridge-Finding Algorithm (TBFA)
TBFA is a bit like a combination of a depth-first search (DFS) approach with recursion and a union-find. IN TBFA, we do a recursive DFS on our graph and for each node we keep track of the earliest node that we can circle back around to reach. By doing this, we can identify whether a given edge is a bridge because the far node doesn't lead back to any other earlier node.
Reconstruct Itinerary
code
euler path
Path with Maximum Probability
code
dijkstra algorithm
Course Schedule
code
topological sort
connecting cities with minimum cost
code
minimum spaning tree alg
Network Delay Time
code
bellman ford alg
Evaluate Division
code
Flood Fill
code
Number of Provinces
code
BFS is a traversal approach in which we first walk through all nodes on the same level before moving on to the next level. DFS is also a traversal approach in which the traverse begins at the root node and proceeds through the nodes as far as possible until we reach the node with no unvisited nearby nodes.1
BinarySearchTree
Binary Tree Inorder Traversal
code
Binary Tree Preorder Traversal
code
Binary Tree Postorder Traversal
code
Binary Tree Level Order Traversal
code
Maximum Depth of Binary Tree
code
Diameter of Binary Tree
code
Validate Binary Search Tree
code
Balance a Binary Search Tree
code
Implement Trie (Prefix Tree)
code
Stream of Characters
code
Backtracking
permutation
Permutations
code
https://www.youtube.com/watch?v=25alMWqAOLo
combination
subset
comparison
Combinations
code
Subsets
code
Combination Sum II
code
Generate Parentheses
code
Word Search
code
Sliding windows problem
Longest Substring Without Repeating Characters
код
створ мапу <знак, інт> , інт лівий, інт правий, інт резалт = 0
в циклі доки правий<довж строки - якщо мапа містить поточ знак - резалт = макс(резалт, правий-лівий). лівий = макс(лівий, вел'ю +1 від поточ кей)
резалт = макс(резалт, правий- лівий)
Fruit Into Baskets
code
Minimum Size Subarray Sum
code
Maximum Points You Can Obtain from Cards
code
159 Longest Substring With at Most Two Distinct Characters -
code
premium
Max Consecutive Ones III
code
Sliding Window Maximum
code
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
code
LinkedList
Copy List with Random Pointer
код -
створюємо мапу<нода, нода>
ноду резалт з нульовим знач і ноду поінтер, що дорівн резалт
поки хед не нал - перевір чи в мапі є хед, якщо нема додаємо; поінтер некст = мапа.гет(хед); поінтер.некст.рандом = нал; перевір чи хед.рандом = нал, якщо ні - перевір чи є він у мапі, якщо ні - додаємо; встан поінтер.некст.рандом = мап.гет(хед.рандом); після перевірок - хед = хед.некст; поінтер = поінтер.некст
вертаємо - резалт.некст
Reverse Linked List
код -
Link Title
створюємо пріоріті кю з кастомним компаратором, в циклі додаємо ноди з масиву в чергу(ед), створюємо ноду резалт з нульовим значенням і ноду поінтер, що дорівн резалт, в циклі, доки черга не порожня - робимо пол, поінтер некст = пол, поінтер = поінтер некст; далі якщо поінтер некст не нал то додаємо вчергу, вертаємо резалт некст
876.Middle of the Linked List
код -
Link Title
маємо 2 поінтери - повільний - кожну ітерацію+1, швидкий- +2, коли швидкий на ост елем, то повіл на середині
Reorder List
код
-
споч шукаємо середину, потім реверс ліст від середини і до кінця, потім мержимо з голови і реверснуту половину
Remove Nth Node From End of List
код -
карент поінтер на голову і повільний поінтер, цикл поки карент не дорівн нулю, карент. некст, якщо n--==0 то слов = хед, і в кожному витку якщо слов не нал то слов.некст, коли слов != нал слов.некст.некст. вертаємо якщо слов == нал то хед.некст або хед
LRU Cache
код
за допомогою
LinkedHashMap
- It is the same as HashMap with an additional feature that it maintains insertion order. Ліст двохзв'язний
Merge k Sorted Lists
code
Intervals
My Calendar I
code
Interval List Intersections
code
My Calendar II
code
My Calendar III
code
Top K Frequent Words
code
Kth Largest Element in a Stream
code
1167.Minimum Cost to Connect Sticks
Dynamic Programming
Unique Paths
code
Triangle
code
Coin Change II
code
Best Time to Buy and Sell Stock
code
Maximum Score Of Spliced Array
code
Longest Increasing Subsequence
code
