Це буде велика стаття, оригінал якої можна знайти тут Стаття містить низку завдань із типовими рішеннями. Для більшості завдань даються різні алгоритми рішення, які ми оновлюватимемо разом, ну і, природно, намагатимемося відстежувати на сайті-оригіналі доповнення та зміни коду. Це мій перший переклад, який, як на мене, потрібно перекладати не просто «в лоб», а з деякими коригуваннями тексту та доповненням невеликої кількості води, не судіть суворо. Допитливий читач, просто зобов'язаний звернути увагу на те, що переклад змісту статті вже містить зміни щодо оригіналу - це пояснюється тим, що алгоритмів у статті далеко не 10. Ви скажете, можна було б написати «10 поширених завдань», але їх так вже склалося, теж не 10, тому просто прийміть це і живіть далі. Радий, якщо читачі будуть доповнювати код новими рішеннями та/або коригувати переклад статті.Що ж, почнемо… Нижче наведено загальні розділи, що містять типові завдання та класичні алгоритми вирішення цих завдань. Автор оригінальної статті зазначає, що для глибокого розуміння цих алгоритмів необхідно докласти набагато більше зусиль, ніж просто прочитати або скопіпастити код, а даний електронний підручник служить тільки для загального висвітлення різних варіантів вирішення задач, що найчастіше зустрічаються. Розділи, які ми спробуємо охопити: 1) Рядок/Масив/Матриця, 2) Linked List, 3) Tree & Heap, 4) Graph, 5) Sorting, 6) Recursion vs. Iteration, 7) Dynamic Programming; 8) Bit Manipulation; 9) Probability; 10) Combinations and Permutationsхіпи , дерева, пошук у глибину , динамічне програмування
1. Рядок/Масив/Матриця
Java рядки містяться у вигляді масиву char-символів, що дозволяє працювати з рядком як з простою послідовністю символів. Далі в статті наведено список методів, які потрібно пам'ятати без авто-завершення, що використовуються у всіх IDE, мені здається це трохи дивним, тому що сама стаття припускає, що читач знає методи класів. Рядки в Java дуже прості для розуміння, але щоб розібратися з завданнями часто потрібно використання складних алгоритмів, таких як динамічне програмування, рекурсія та інших . Стандартні завдання на тему:
s Triangle 45) Container With Most Water 46) Count and Say 47) Repeated DNA Sequences 48) House Robber 49) Dungeon Game (DP)2. Всі номери мають значення і посилання на next node. class Node { int val; Node next; Node(int x) { val = x; next = null; } } Two popular applications of linked list are stack and queue. Stack class Stack {Node top; public Node peek(){ if(top != null){ return top; } return null; } public Node pop(){ if(top == null){ return null; } else { Node temp = New Node (top.val); top=top.next; return temp; } } public void push(Node n){ if(n != null){ n.next = top; top = n; } } } Queue class Queue{ Node first, last; public void enqueue (Node n) {if (first == null) { first = n; last=first; } else { last.next = n; last = n; } } public Node dequeue(){ if(first == null){ return null; } else { Node temp = new Node (first.val); first = first.next; return temp; } } } It is worth to mention that Java standard library already contains a class called "Stack", and LinkedListcan be used as a Queue (add() and remove()). (LinkedList implements the Queue interface.) Якщо ви потребуєте stack or queue to solve problems during your interview, ви можете безпосередньо використовувати їх. Classic Problems: 1) Add Two Numbers 2) Reorder List 3) Linked List Cycle 4) Copy List with Random Pointer 5) Merge Two Sorted Lists 6) Merge k Sorted Lists * 7) Remove Duplicates from Sorted List 8) Partition List 9) LRU Cache 10) Intersection of Two Linked Lists 3. Tree & Heap A tree normally refers to a binary tree. Всі ці позначки розміщені в лівому ліці і правому ліці: class TreeNode{ int value; TreeNode left; TreeNode right; } Тут є деякі concepts related with trees: 1. Binary Search Tree: для всіх номерів, лівих дітей <= current node <= right children 2. Balanced vs. Unbalanced: В balanced tree, depth of left and right subtrees of every node differ by 1 or less. 3. Full Binary Tree: всі номери інших тих, що лежать на двох дітей. 4. Perfect Binary Tree: повний binary strom в яких всі листи є на тій самій глибині або самий рівень, і в яких всі parent has два children. 5. Complete Binary Tree: binary tree in which every level, except possibly the last, is completely filled, and all nodes as far left as possible Time complexity of its operations are important (eg, find-min, delete-min, insert, etc). У Java, PriorityQueue is important to know. Classic problems: 1) Binary Tree Preorder Traversal 2) Binary Tree Inorder Traversal [Palantir] 3) Binary Tree Postorder Traversal 4) Word Ladder 5) Validate Binary Search Tree 6) Flatten Binary Tree до Linked List 7) Path Sum 8 Tree від Inorder and Postorder Traversal 9) Конвертований аркадний щит на binary Search Tree 10) Перевірений аркуш List для binary Search Tree 11) Мінімальна частина битви 12) битви трій Maximum Path Sum * 13) Балансована битва 15) 14) Binary Search Tree Iterator 4. Graph Graph пов'язані з питаннями основним фокусом на глибині перших досліджень і breath перших пошуків. Depth first search is straightforward, Ви можете just loop через neighbors starting from the root node. Це являє собою пряму реалізацію графа і breath першої search. Key is using a queue to store nodes. 1) Define GraphNode class GraphNode { int val; GraphNode next; GraphNode[] neighbors; boolean visited; GraphNode(int x) { val = x; } GraphNode (int x, GraphNode [] n) {val = x; neighbors = n; } public String toString(){ return "value: "+ this.val; } } 2) Define a Queue class Queue { GraphNode first, last; public void enqueue(GraphNode n){ if(first == null){ first = n; last=first; } else { last.next = n; last = n; } } public GraphNode dequeue(){ if(first == null){ return null; } else { GraphNode temp = new GraphNode (first.val, first.neighbors); first = first.next; return temp; } } } 3) Breath First Search uses a Queue public class GraphTest { public static void main(String[] args) { GraphNode n1 = new GraphNode(1); GraphNode n2 = новий GraphNode(2); GraphNode n3 = новий GraphNode(3); GraphNode n4 = new GraphNode(4); GraphNode n5 = новий GraphNode(5); n1.neighbors = new GraphNode[]{n2,n3,n5}; n2.neighbors = new GraphNode[]{n1,n4}; n3.neighbors = new GraphNode[]{n1,n4,n5}; n4.neighbors = new GraphNode[]{n2,n3,n5}; n5.neighbors = new GraphNode[]{n1,n3,n4}; breathFirstSearch(n1, 5); } public static void breathFirstSearch(GraphNode root, int x){ if(root.val == x) System.out.println("find in root"); Queue queue = new Queue(); root.visited = true; queue.enqueue(root); while(queue.first != null){ GraphNode c = (GraphNode) queue.dequeue(); for(GraphNode n: c. neighbors){ if(!n.visited){ System.out.print(n + " "); n.visited = true; if(n.val == x) System.out.println("Find "+n); queue.enqueue(n); } } } } } Output: value: 2 value: 3 value: 5 Find value: 5 value: 4 Classic Problems: 1) Clone Graph 5. Sorting Time complexity of different sorting algorithms. Ви можете йти до wiki, щоб дізнатися про те, що основна думка. Algorithm Average Time Worst Time Space Bubble sort n^2 n^2 1 Selection sort n^2 n^2 1 Insertion sort n^2 n^2 Quick sort n log(n) n^2 Merge sort n log(n) n log(n) depends * BinSort, Radix Sort і CountSort use different set of assumptions than rest, and si they not "general" sorting methods. (Танки до Fidel для оцінки цього виходу) Тут є деякі implementations/demos, and in addition, ви можете check out how Java developers sort in practice. 1) Mergesort 2) Quicksort 3) InsertionSort. 4) Maximum Gap (Bucket Sort) 6. Recursion vs. Iteration Recursion повинна бути побудована в тому, що для програмістів. Це може бути продемонстровано як простий приклад. Question: there are n stairs, each time one can climb 1 or 2. How many different ways to climb the stairs? Step 1: Finding the relationship до n і n-1. Для того, щоб отримати n, там є тільки два способи, один 1-stair from n-1 або 2-stairs from n-2. Якщо f(n) є числом способів, щоб перейти до n, тоді f(n) = f(n-1) + f(n-2) Step 2: Make sure the start condition is correct. f(0) = 0; f(1) = 1; public static int f(int n) {if (n <= 2) return n; int x = f(n-1) + f(n-2); return x; } Time complexity of the recursive method is exponential to n. Існує безліч redundant computations. f(5) f(4) + f(3) f(3) + f(2) + f(2) + f(1) f(2) + f(1) + f(2) + f(2) ) + f(1) Вона повинна бути справедливою, щоб перевірити відповідь на iteration. public static int f(int n) { if (n <= 2) { return n; } int first = 1, second = 2; int third = 0; for (int i = 3; i <= n; i++) { third = first + second; first = second; second = third; } return third; } For this example, iteration takes less time. You may also want to check out Recursion vs Iteration. 7. Dynamic Programming Dynamic programming є технологією для вирішення проблем з наступними властивостями: 1. An instance is solveding using the solutions for smaller instances. 2. Вирішення для дрібниць взаємності може бути потрібне кілька разів. 3. Відповідь на дрібниць stanses є запозичений в table, so that each smaller instance is solved only once. 4. Additional space is used to save time. Проблема climbing steps perfectly fit those 4 properties. Там, він може бути вирішений за допомогою динамічного програмування. public static int[] A = new int[100]; public static int f3(int n) { if (n <= 2) A [n] = n; if(A[n] > 0) return A[n]; else A[n] = f3(n-1) + f3(n-2);//store results so only calculate once! return A[n]; } Classic problems: 1) Edit Distance 2) Longest Palindromic Substring 3) Word Break 3) Word Break II 4) Maximum Subarray 4) Maximum Product Subarray 5) Palindrome Partitioning 6) Candy [Google] 7) Jump Game 8) Best Time to Buy and Sell Stock III (DP) 8) Best Time to Buy and Sell Stock IV (DP) 9) Dungeon Game (DP) 8. Bit Manipulation Bit operators: OR (|) AND (&) XOR (^) Left Shift ( <<) Right Shift (>>) Not (~) 1|0=1 1&0=0 1^0=1 0010<<2=1000 1100> >2=0011 ~1=0 Get bit i for a give number n. (i count from 0 and starts from right) public static boolean getBit(int num, int i){ int result = num & (1<
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ