Лучшие алгоритмы для написания кода
Это будет большая статья, оригинал которой можно найти
здесь
Статья содержит ряд задач с типовыми решениями. Для большинства задач даются различные алгоритмы решения, которые мы будем обновлять вместе, ну и, естественно, будем стараться отслеживать на сайте-оригинале дополнения и изменения кода.
Это мой первый перевод, который, как мне кажется, нужно переводить не просто «в лоб», а с некоторыми корректировками текста и дополнением небольшого количества воды, не судите строго.
Пытливый читатель, просто обязан обратить внимание на то, что перевод оглавления статьи уже содержит изменения, относительно оригинала - это объясняется тем, что алгоритмов в статье далеко не 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
11) Math
Предполагается, что эта статья будет прочитана людьми, которые уже знают основы языка и хотят немного расширить свои знания алгоритмики. Общие подходы к решению представленных ниже задач включают в себя: сортировку, бинарный поиск, хэш-таблицы,
хипы, деревья,
поиск в глубину,
динамическое программирование
1. Строка/Массив/Матрица
В Java строки содержатся в виде массива char-символов, что позволяет работать со строкой как с простой последовательностью символов. Дальше в статье приведен список методов, которые нужно помнить без авто-завершения используемых во всех IDE, мне кажется это немного странным, потому что сама статья предполагает, что читатель знает методы классов. Методы класса String можно найти
тут, а методы класса Arrays
тут
Строки в Java очень просты для понимания, но чтобы разобраться с задачами часто требуется использование сложных алгоритмов, таких как динамическое программирование, рекурсия и прочих.
Стандартные задачи по теме:
- Смена порядка в массиве.
- Распознание обратной польской записи.
- Поиск подстроки-палиндрома наибольшей длины
- Распознание слов
- Распознание слов 2
- Поиск совпадений по регулярным выражениям
- Слияние пересекающихся интервалов
- Слияние интервалов по объединяющему интервалу
- Сумма двух чисел массива
- Сумма двух чисел массива 2
- Сумма двух чисел массива 3
- Сумма трех чисел равная 0
- Сумма четырех чисел равная произвольному числу
- Сумма трех чисел близкая к произвольному числу
- Конвертирование строки в число
Classic problems:
0) Rotate Array
1) Evaluate Reverse Polish Notation (Stack)
2) Longest Palindromic Substring (DP)
3) Word Break (DP)
3) Word Break II (DP, DFS)
4) Word Ladder (Queue, BFS)
5) Median of Two Sorted Arrays
6) Regular Expression Matching
7) Merge Intervals
8) Insert Interval
9) Two Sum
9) Two Sum II – Input array is sorted
9) Two Sum III - Data structure design
9) 3Sum
9) 4Sum
10) 3Sum Closest
11) String to Integer
12) Merge Sorted Array
13) Valid Parentheses
14) Implement strStr()
15) Set Matrix Zeroes
16) Search Insert Position
17) Longest Consecutive Sequence
18) Valid Palindrome
19) Spiral Matrix
20) Search a 2D Matrix
21) Rotate Image [Palantir]
22) Triangle
23) Distinct Subsequences Total
24) Maximum Subarray [Palantir, LinkedIn]
24) Maximum Product Subarray [LinkedIn]
25) Remove Duplicates from Sorted Array
26) Remove Duplicates from Sorted Array II
27) Longest Substring Without Repeating Characters
28) Longest Substring that contains 2 unique characters [Google]
29) Palindrome Partitioning
30) Reverse Words in a String
31) Find Minimum in Rotated Sorted Array
31) Find Minimum in Rotated Sorted Array II
32) Find Peak Element
33) Min Stack
34) Majority Element
35) Combination Sum (DFS)
36) Best Time to Buy and Sell Stock
36) Best Time to Buy and Sell Stock II
36) Best Time to Buy and Sell Stock III (DP)
36) Best Time to Buy and Sell Stock IV (DP)
37) Longest Common Prefix [Google]
38) Largest Number
39) Combinations (DFS)
40) Compare Version Numbers
41) Gas Station
42) Candy [Google]
43) Jump Game
44) Pascal's Triangle
45) Container With Most Water
46) Count and Say
47) Repeated DNA Sequences
48) House Robber
49) Dungeon Game (DP)
2. Linked List
The implementation of a linked list is pretty simple in Java. Each node has a value and a link to 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.) If you need a stack or queue to solve problems during your interview, you can directly use them.
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. Each node contains a left node and right node like the following:
class TreeNode{
int value;
TreeNode left;
TreeNode right;
}
Here are some concepts related with trees:
1. Binary Search Tree: for all nodes, left children <= current node <= right children
2. Balanced vs. Unbalanced: In a balanced tree, the depth of the left and right subtrees of every node differ by 1 or less.
3. Full Binary Tree: every node other than the leaves has two children.
4. Perfect Binary Tree: a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children.
5. Complete Binary Tree: a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible
Heap is a specialized tree-based data structure that satisfies the heap property. The time complexity of its operations are important (e.g., find-min, delete-min, insert, etc). In 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 to Linked List
7) Path Sum
8) Construct Binary Tree from Inorder and Postorder Traversal
9) Convert Sorted Array to Binary Search Tree
10) Convert Sorted List to Binary Search Tree
11) Minimum Depth of Binary Tree
12) Binary Tree Maximum Path Sum *
13) Balanced Binary Tree
14) Symmetric Tree
15) Binary Search Tree Iterator
4. Graph
Graph related questions mainly focus on depth first search and breath first search. Depth first search is straightforward, you can just loop through neighbors starting from the root node.
Below is a simple implementation of a graph and breath first search. The key is using a queue to store nodes.
1) Define a 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 = new GraphNode(2);
GraphNode n3 = new GraphNode(3);
GraphNode n4 = new GraphNode(4);
GraphNode n5 = new 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. You can go to wiki to see basic idea of them.
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 and CountSort use different set of assumptions than the rest, and so they are not "general" sorting methods. (Thanks to Fidel for pointing this out)
Here are some implementations/demos, and in addition, you may want to check out how Java developers sort in practice.
1) Mergesort
2) Quicksort
3) InsertionSort.
4) Maximum Gap (Bucket Sort)
6. Recursion vs. Iteration
Recursion should be a built-in thought for programmers. It can be demonstrated by a simple example.
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 before n and n-1.
To get n, there are only two ways, one 1-stair from n-1 or 2-stairs from n-2. If f(n) is the number of ways to climb to n, then 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;
}
The time complexity of the recursive method is exponential to n. There are a lot of 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)
It should be straightforward to convert the recursion to 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 is a technique for solving problems with the following properties:
1. An instance is solved using the solutions for smaller instances.
2. The solution for a smaller instance might be needed multiple times.
3. The solutions to smaller instances are stored in a table, so that each smaller instance is solved only once.
4. Additional space is used to save time.
The problem of climbing steps perfectly fit those 4 properties. Therefore, it can be solve by using dynamic programming.
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<
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ