This tutorial provides an overview and explanation of greedy algorithms, along with easy-to-understand code and infographics. You’ll be a professional soon!
1. The prefix tree
1.1 illustrates
Prefix trees are associated with greedy algorithms; Forget about relationships.
The prefix tree, also known as TRIE, word search tree, etc., is a tree structure used to store a large number of strings.
Its characteristic is space for time, using the common prefix of string to reduce the cost of query time, to achieve the purpose of improving efficiency.
1.2 Classic Prefix Tree
The characters of the classic prefix tree are stored on the path, and there is no data at each node.
1.3 Code Definition
1.3.1 Node structure
In order to implement certain functions with TRIE, data items are actually added to the node.
Public class Node {// How many times has this Node been reached while building the prefix tree int pass; // if the node is the end of a string, and if so, how many string end nodes int end; // Node[] nexts; // HashMap<Char, Node> -- TreeMap<Char, Node> public Node() { this.pass = 0; this.end = 0; // Nexts [0]== NULL means that there is no way to store 'a' at the next level // Nexts [0]! Nexts = new Node[26]; }}Note: In the prefix tree, the downward path for each node is achieved by mounting the slave node. In the implementation of the code, the sub-nodes that can be mounted are numbered by the subscript of the array, so that each side can “carry” different character information through the one-to-one correspondence between the subscript and the character.
If you need to store strings containing more than one type of character, you should not use arrays to store mounted nodes. For example, Java supports more than 60,000 characters, so you can’t start with an array with a capacity of 60,000. Therefore, when there are a large number of character types, a hash table can be used instead of an array to store mounted nodes, and the key of the hash table can correspond to characters one to one.
When the hash table is replaced with an array, the overall algorithm does not change and the Coding details do.
However, using hash table storage, the path is unordered. If you want paths organized like array storage, you can use an ordered table instead of a hash table storage.
Stores the above string again using the node with the added data item:
By adding nodes with data items, we can easily solve many problems, such as:
How do I know if the string “BCK” is stored in TRIE?
A: Start at the root node and check if there is a way ‘B’? Yes; Is there a way to ‘c’? Yes; Is there another way to “k”? Yes; Then check the end of the node at the end of the ‘k’ path, if END! = 0, “BCK” is stored, if end = 0, “BCK” is not stored.
How do I know how many of the strings stored in the Trie are prefixed with “ab”?
A: Start at the root node and check if there is a way to get to ‘a’? Yes; Is there a way to ‘b’? Yes; Then check the pass of the node at the end of the ‘b’ path. The value of pass is the number of strings prefixed with “ab”.
How do you know how many strings are stored in the Trie?
Answer: Just check the pass of the root node.
How do I know how many empty strings are stored in the TRIE?
Answer: Just check the end of the root node.
Through the above questions, we can find that each string stored in TRIE can be easily queried by using the data item information of node type, and the cost of querying the string is very low. It only needs to traverse the number of characters in the string to query the number of times.
1.3.2 Tree structure
Public class Trie {// private Node root; public Trie() { this.root = new Node(); } // Related operations... }1.4 Basic operation
1.4.1 Add a String
Start at the root node, increment the node pass along the way, and increment the node at the end of the string by 1.
Code:
public void insert(String word) { if (word == null) { return ; } char[] charSequence = word.toCharArray(); // Start the string with the root Node Node cur = this.root; cur.pass ++; for (int i = 0; i < charSequence.length; i ++) { int index = charSequence[i] - 'a'; If (cur.nexts[index] == null) {cur.nexts[index] = new Node(); } // Cur = Cur. Nexts [index]; cur.pass ++; } // Record the end of the string node cur.end ++; }Note: Adding each string must start at the root, which means that each string is prefixed with an empty string.
1.4.2 Delete string
If the string exists, start at the root node, subtract 1 from the pass of the node along the way, and subtract 1 from the node at the end of the string.
Code:
Public void the delete (String word) {/ / determine whether to store the word if (word = = null | | search (word) = = 0) {return; } char[] charSequence = word.toCharArray(); Node cur = this.root; cur.pass --; for (int i = 0; i < charSequence.length; i ++) { int index = charSequence[i] - 'a'; If (-- cur.nexts[index]. Pass == 0) {cur.nexts[index] == 0 null; return ; } cur = cur.nexts[index]; } cur.end --; }Note: If there is only one target string in the TRIE, all redundant nodes need to be freed after modifying the node data. Because of automatic garbage collection in Java, the first time we walk through a node with a pass of 0, we can simply set it to null, and all of the node’s children will be collected automatically. If implemented in C++, you need to call the destructor to release the node manually at the end of the traversal as you go back along the way.
1.4.3 Query string
Query the node at the end of the string if the string exists.
Code:
Public int search(String word) {if (String word == null) {return 0; } char[] charSequence = word.toCharArray(); Node cur = this.root; For (int I = 0; int I = 0; i < charSequence.length; i ++) { int index = charSequence[i] - 'a'; If (cur.nexts[index] == null) {return 0; } cur = cur.nexts[index]; } // end of the node at the end of the string return cur.end; }1.4.4 Query prefixes
If the string exists, query for the pass that prefixes the node at the end of the string.
Code:
Public int prefixNumber (String pre) {if (pre == null) {return 0; } char[] charSequence = pre.toCharArray(); Node cur = this.root; For (int I = 0; int I = 0; i < charSequence.length; i ++) { int index = charSequence[i] - 'a'; If (cur.nexts[index] == null) {return 0; if (cur.nexts[index] == null) {return 0; } cur = cur.nexts[index]; } // pass the node at the end of the pre substring return cur.pass; }Greedy algorithms
2.1 concept
Under a certain standard, the algorithm that gives priority to the samples that most meet the standard, and finally considers the samples that do not meet the standard and finally gets the answer is called greedy algorithm.
In other words, regardless of global optimality, what you get is a locally optimal solution in some sense.
2.2 illustrates
Greedy algorithm is actually the most common algorithm and the code implementation is very short.
Many greedy algorithms only need to find a good solution, not an optimal solution. In other words, for most everyday greedy algorithms, the process from local optimality to global optimality cannot be proved, or proved wrong, because greed is sometimes subjective. However, all the greedy algorithm problems we have encountered are deterministic, so we can find the global optimal solution. At this time, the investigation of greedy algorithm needs the proof from local optimum to global optimum.
This article will not show the proof, because for each problem, how its locally optimal strategy leads to a globally optimal proof is different. If every greedy algorithmic problem is proven, there isn’t enough time in the interview process. The following is a very useful technique, which is based on preparing many templates, but only once. And get ready, when you do greedy algorithm problems, it’s going to be faster and more accurate, much faster than proof.
2.3 Meeting Issues
Title:
Some projects require a conference room for presentations, and the conference room cannot accommodate two presentations at once. Given all of your projects and the start and end times of each project, you will schedule the presentations and ask for the maximum number of presentations in the conference room. Back to this most sermon meeting.
Analysis:
Greed strategy A: The earlier you start the project, the earlier you schedule it.
The global optimal solution cannot be obtained. For example:
Greedy strategy B: Priority should be given to the shorter project duration.
The global optimal solution cannot be obtained. For example:
Greed Strategy C: Schedule projects that end early.
You can get the global optimal solution.
Counterexample of Strategy A:
Counterexample of Strategy B:
Public class Solution {static class Program {public int begin; Public int end public int end; public Program(int begin, int end) { this.begin = begin; this.end = end; }} / / define the Program Comparator, according to the end of the Program time to compare the static class ProgramComparator implements Comparator < Program > {@ Override public int compare(Program program1, Program program2) { return program1.end - program2.end; } } public int arrangeProgram(Program[] programs, int currentTime) { if (programs == null || programs.length == 0) { return 0; } // Arrange the number of fields for the item int number = 0; Sort (Arrays.sort(programs, new ProgramComparator())); Arrays.sort(Arrays.sort(programs, new ProgramComparator())); Arrays.sort(Arrays.sort()); for (int i = 0; i < programs.length; If (currentTime < Programs [I].begin) {number ++; if (currentTime < Programs [I].begin) {number ++; } currentTime = Programs [I].end; currentTime = Programs [I].end; } return number; }}2.4 Problem Solving Procedure
After reading 2.3, there will be problems. Why does Greedy Strategy C find the optimal solution? Don’t worry about why Greedy Strategy C is right, just blind and skilled blind.
In problems related to greedy algorithms, you always have several greedy strategies. It would be nice if some greedy strategies could be overturned by counterexamples. But if you can’t give a counterexample to a few greedy strategies that seem plausible to you, do you need to prove them with rigorous mathematics? You can ask questions in private, but not in an interview!
The mathematical proof of greedy strategy is different for each problem, because each problem has its own thing, and the method of proof is also incredible, testing the mathematical ability.
So how do you validate your greed strategy? Logarithmic.
2. A problem solving routine:
To implement Solution X, which does not rely on greedy strategies, you can use the most violent attempt. The brain compensates for greedy strategy A, greedy strategy B, greedy strategy C…… Verify each greedy strategy by solving X and logarithms, and use experiments to know which greedy strategy is correct. Don’t worry about proof of greedy tactics. Preparation:
Be ready for brute force attempts or complete arrays of code templates. Prepare the logarithmic code template.
2.5 Interview Situation
Greedy algorithm is not flexible, the interview proportion is relatively low. There are about five questions, one at most.
First, the problem of greedy algorithms does not test the power of Coding because the code is extremely simple.
Second, the problem of greedy algorithms is undiscriminated. As long as you find the greedy strategy, it’s all the same, just the difference between 0 and 1.
3. The logarithmic
3.1 illustrates
Logarithms are very useful, and they can help you solve a lot of problems.
Suppose you want to test Method A, but the same problem can be implemented with many strategies. Regardless of the complexity of the event, I could write a solution to the brute force attempt (for example, list all permutations and combinations). We call this an approach that doesn’t pursue the merits of time complexity, but is thoughtful and easy to write. Method B. Why test Method A? Because it might be hard to think of method A or it might be low in time.
In the past, every exam need to rely on online OJ? If you have to rely on OJ for every topic, do you still need to look for strange topics on OJ? If you can’t find it, don’t you practice it? Secondly, the online test data is what people think, so when he is preparing test cases, will not let your code run wrong, but not let you pass the situation? You’ve passed, but are you sure your code is correct? Not necessarily, this time needs logarithmic method, logarithmic method is foolproof.
3.2 the implementation of
Implement a random sample generator, you can control the sample size, you can control the number of tests, you can generate random data. The generated data is run in method A to get RES1, and then in method B to get RES2. Check that RES1 and RES2 are consistent. You measure tens of thousands of groups and then change the sample size. When RES1 and RES2 are found to be inconsistent, either method A is wrong, or method B is wrong, or both.
The implementation of random number in Java:
Double random = Math.random(); double random = Math.random(); double random = Math.random(); Double random = N * Math.random(); // int random = (int) (N * Math.random());By generating random numbers, you can randomize any part of the test sample, such as sample size, number of tests, test data.
Logarithms are implemented differently for each topic with different business logic. You need to implement it according to the actual situation.
4. Interview questions
4.1 Find the median
Title:
The user uses a structure to store N numbers one by one and requires that the median of all the numbers currently stored in the structure be available at any time.
Rule: The median of odd bits is the middle bit, and the median of even bits is the average of the middle two bits.
Analysis:
This topic has nothing to do with greedy algorithm. It is a classic topic of research reactor application.
Because heaps are widely used in greedy algorithms, you can familiarize yourself with the operation of heaps in this topic.
The time complexity of this algorithm is very low because all operations on the heap are O(logN).
The process is:
Prepare a large pile and a small pile. The first number goes into the big pile. Enter the fixed iteration process: the current input number Cur <= the top number of the big pile, if so, Cur enters the big pile; If not, the CUR enters the small pile. Observe the size of large and small piles. If the larger one is two more than the smaller one, the larger top will pop another one. Stop iterating after storing all the numbers. The smaller N/2 number is in the larger pile, and the larger N/2 number is in the smaller pile. You can find the median by using the highest number of both heaps. Code:
Public class Solution {// static class BigComparator implements Comparator<Integer> {@Override public int compare(Integer num1, Integer num2) { return num2 - num1; } } public static int findMedian(int[] input) { if (input == null || input.length == 0) { return 0; } PriorityQueue<Integer> bigRootHeap = new PriorityQueue<>(new BigComparator()); PriorityQueue<Integer> smallRootHeap = new PriorityQueue<>(); BigRootheAp. add(input[0]); for (int i = 1; i < input.length; i ++) { if (input[i] <= bigRootHeap.peek()) { bigRootHeap.add(input[i]); } else { smallRootHeap.add(input[i]); } if (Math.abs(bigRootHeap.size() - smallRootHeap.size()) == 2) { if (bigRootHeap.size() > smallRootHeap.size()) { smallRootHeap.add(bigRootHeap.poll()); } else { bigRootHeap.add(smallRootHeap.poll()); }}} if (input.length % 2!) {input.length % 2! = 0) { return smallRootHeap.peek(); } return (bigRootHeap.peek() + smallRootHeap.peek()) / 2; }}4.2 Gold bar problem
Title:
Cutting a gold bar in half requires copper plates of the same length. For example, a strip of length 20 would cost 20 coppers to cut in half.
If a group of people want to divide a whole bar of gold, how do they divide the most economical copper?
For example, given an array [10, 20, 30] representing three people, the length of the entire bar is 10 + 20 + 30 = 60. Gold bars are divided into three parts: 10, 20, and 30. If you divide a 60-length bar into 10 and 50 bars, the cost is 60; Then divide 50 bars into 20 bars and 30 bars at a cost of 50; A total of 110 coppers are needed.
But if you divide 60 bars into 30 and 30, you get 60; Then divide 30 bars into 10 bars and 20 bars, and it costs 30 bars; I spent 90 pieces of copper.
Enter an array and return the minimum cost of the split.
Analysis:
This problem is a classic Hoffman coding problem.
The process is:
Put all the elements in the array into the small root heap
Iterative fixed process:
Pop-up two nodes from the top of the small root pile and combine them into new nodes to build the Hoffman tree.
The new node is put back into the small root heap.
Stop iterating until there is only one node in the small root heap.
Code:
public int leastMoney(int[] parts) { PriorityQueue<Integer> smallRootHeap = new PriorityQueue<>(); Int money = 0; int money = 0; For (int I = 0; i < parts.length; i ++) { smallRootHeap.add(parts[i]); } // Stop while (SmallRootheAP.size ()!) until there is only one node in the heap. SmallRootheap.poll () + SmallRootheap.poll (); // SmallRootheap.poll (); money += cur; // Summarize the new nodes into the heap SmallRootheAP.add (cur); } return money; }4.3 Project planning issues
Title:
Your team receives a number of projects, each of which will have a cost and a profit. Since your team is small, you have to work on projects sequentially. Assuming that your team currently has M funds at its disposal and can only work on K projects, what is the ultimate maximum amount of money at its disposal?
Note: casts[I], progress[I], M, and K are positive numbers.
Analysis:
The process is:
Build a small stake and a large one. The classification standard of small piles is cost, while the classification standard of large piles is profit.
Place all items in the small root heap.
Enter the fixed iteration process:
The small root heap pops all items whose cost is less than or equal to M into the large root heap.
The most profitable project appeared.
M plus the profit from the project that was just completed.
Stop iterating until the number of completed items is K.
Code:
public class Solution { static class Project { int cost; int profit; public Project(int cost, int profit) { this.cost = cost; this.profit = profit; } } static class minCostComparator implements Comparator<Project> { @Override public int compare(Project p1, Project p2) { return p1.cost - p2.cost; } } static class maxProfitComparator implements Comparator<Project> { @Override public int compare(Project p1, Project p2) { return p2.profit - p1.profit; } } public static int findMaximumFund(int M, int K, int[] costs, int[] profits) { if (M == 0 || K == 0) { return 0; } // PriorityQueue<Project bb0 costSmallRootheAP = new PriorityQueue<>(new mincostComparator ()); PriorityQueue<Project BB0 ProfilBigRootheAP = new PriorityQueue<>(new MaxProfilitComparator ()); For (int I = 0; int I = 0; i < costs.length; i ++) { costSmallRootHeap.add(new Project(costs[i], profits[i])); } for (int I = 0; i < K; I ++) {// Put the currently doable items from the small root heap into the large root heap while (! costSmallRootHeap.isEmpty() && costSmallRootHeap.peek().cost <= M) { profitBigRootHeap.add(costSmallRootHeap.poll()); } / / not to do the project if (profitBigRootHeap. IsEmpty () {return M; } // select the most profit from the large root heap and do Project cur = profitBigRootheAP.poll (); M += cur.profit; } return M; }}4.4 N queen problem
Title:
The N queen problem refers to placing N queens on an N by N chessboard, requiring any two queens to be on different rows, in different columns, and not on the same diagonal.
Given an integer n, return how many ways queen n can be.
Such as:
N =1, returns 1.
N =2 or 3, returns 0. (2 queens and 3 queens problem won’t work no matter how you play it)
N =8, returns 92.
Analysis:
This problem is a classic problem, the optimal solution is very complex, is a dynamic programming problem with sequelae.
If you’re not writing a paper, the best approach to the interview process is to use depth-first thinking, putting queens in each row in turn, and using force recursion to try every possibility in each column.
The time complexity index of this scheme is still very high.
Because the first row has N choices, the second row has N choices, and the third row has N choices… I have N rows, so my time complexity is order N to the N.
Assume that Record [0] = 2 and Record [1] = 4. When depth-first traversal reaches I = 2, there are 3 reasonable Queen placement positions in the third row of the figure. Then these three positions in turn depthwise traversal and start again and again.
Code:
public static int nQueen(int n) { if (n < 1) { return 0; } int[] record = new int[n]; // start from line 0 return process(0, n, record); ** * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n * @param n Public static int process(int I, int n, int n) */ public static int process(int I, int n, Int [] record) {if (I == n) {return 1; } int result = 0;} int result = 0; // try depth-first traversal for (int j = 0; j < n; J ++) {if (isValid(I, j, record)) {record[I] = j; // result += process(I + 1, n, record); } } return result; Queen public static Boolean isValid(int I, int j, int j, int j, int j) Int [] record) {// For (int k = 0; int k = 0; k < i; K + +) {/ / whether is it the same column or diagonal lines (line during impossible) if (record [k] = = j | | math.h abs (k - I) = = math.h abs (record [k] - j)) {return false. } } return true; }4.5 N queen problem (optimization)
The N-Queen problem cannot be optimized in terms of time complexity, but it can be optimized in terms of constants, and there are many optimizations.
I could say the time complexity is still the same time complexity, but I can make it very low in constant time in my implementation.
How low is it? For example, for the 14 queen problem, the 4.4 solution will run 5s, and the 4.5 optimized solution will run 0.2s. For the 15 queen problem, the 4.4 solution runs for 1 min, and the 4.5 optimal solution runs for 1.5s.
Analysis:
Use bitwise manipulation to speed things up. Bit arithmetic acceleration is a very common technique and it is recommended to master it.
Because of the bitwise operation, it depends on how variables are stored in the code. The type of the variable in this code is a 32-bit int, so it doesn’t solve the problem of 32 queens or more.
If you want to solve a problem with more than 32 queens, you can change the parameter type to long.
Code:
public static int nQueen(int n) { if (n < 1 || n > 32) { return 0; } int limit = n == 32 ? -1 : (1 << n) - 1; return process(limit, 0, 0, 0); } /** * @Param n How many rows in total * @Param Collim Limits: @Param Collim: 0 Collim Limits: @Param LeftDialim: 0 Collim Limits: @Param LeftDialim: 1 Collim: 0 Collim Limits: @Param LeftDialim: 1 Collim: 0 Collim 0 position can be * @param rightDiaLim right slash limit, 1 position can not put queen, Public static int process(int n, int colLim, int leftDialim, int lilim, int lilim, int lilim) Int rightDiaLim) {// if (colLim == n) {return 1; } int mostRightOne = 0; / / all choose the queen's column after the bits in the pos on int pos = n & (~ (colLim | leftDiaLim | rightDiaLim)); int res = 0; while (pos ! = 0) {// Extract the right-most one from the candidate queens moStrightOne = pos & (~ pos + 1); pos = pos - mostRightOne; // update limit; Enter the recursive res + = process (n, colLim | mostRightOne, (leftDiaLim | mostRightOne) < < 1, (rightDiaLim | mostRightOne) > > > 1); } return res; }For more free information add group: 3907814