1. Binary search (non-recursive)
  2. Divide and conquer algorithm
  3. Dynamic programming
  4. KMP algorithm
  5. Greedy algorithm
  6. Backtracking algorithm

The following ideas and key methods are only given. The source code of the algorithm is put in Git, and you need to take it yourself

leidl97/algorithm-src

Binary search (non-recursive)

If you’re not recursing, you would definitely use while

The difficulties in

Note the boundary condition, which only breaks out of the loop if the value on the left is greater than the value on the right

If the target value is less than mid, we should set right = mid + 1, we need to add 1,

And likewise, the opposite case requires minus 1.

Method implementation

Private static void search3(int[] a, int act) {int left = 0; int right = a.length-1; while (left <= right) { int mid = (left + right) / 2; If (a[mid] == act) {// if (a[mid] == act) {// If (a[mid] == act); return; } if (act < a[mid]) { right = mid - 1; continue; } left = mid + 1; } system.out.println (" the value was not found "); }Copy the code

Divide and conquer algorithm

Divide and conquer, decompose a big problem into small problems to solve, and then merge the solutions of sub-problems into the solution of the original problem.

Classic applications are: merge sort, quicksort, Fourier transform (Fast Fourier transform), Hannott tower and so on

Take hannoiTower, for example

Their thinking

If there is only one disk, move it directly from A to C

If two disks

① Then consider the uppermost part as a whole and move to auxiliary pillar B first (recursion)

② Move the last disk to C

③ Finally, move the disk on B to C, with A as the auxiliary pillar (recursion)

Code implementation

Public void merge(int n, char a, char b, char b, char b, char b, char b, char b, char b, char b, char b, char b, char b, char b, char b) Char c) {if (n = = 1) {System. Out. Println (" the first dish from "+ a +" to "+ c); return; } if (n >= 2) { merge(n-1,a,c,b); System.out.println(" a+" to "c"); merge(n-1,b,a,c); }}Copy the code

Dynamic programming

Take the classic 01 knapsack problem

(Dynamic Programing) you can see a video of station B, which is very clear

【 dynamic programming 】 knapsack problem _bilibili _bilibiliwww.bilibili.com

introduce

It is a step cache, reduce the process of double calculation, increase operation efficiency, find the optimal solution

Continue to return to the backpack problem, and divided into 01 backpack and complete backpack, 01 backpack means that things can not be repeated, can be put into more than one

Dp problem involving two dimensions, directly consider building a two-dimensional array to solve (size +1, row 0 and column 0 values are not included)

Construct a 5 x 4 table based on weight and price

Train of thought

1. Set the first column and column to 0

You can’t let anything of value in a backpack when it’s zero, and when it’s zero, it doesn’t matter how much weight you carry

Why would you want to create an array of zeros if they’re all zeros? What’s the point?

For later calculations

2. The for loop iterates, filling the array from the first row to the first column

Each cell in a two-dimensional array has two choices, one to load items and one not to

(1) If not fit, can only choose not to fill the item, train of thought

1, the first row and column are set to 0, because when the backpack capacity is 0, you can not let anything of value, when the value is 0, how much weight is 0

Why would you want to create an array of zeros if they’re all zeros? What’s the point?

For later calculations

2. The for loop iterates, filling the array from the first row to the first column

Each cell in a two-dimensional array has two choices, either to fill in items or not to fill in items

First, judge if it can’t fit, then you can only choose not to fill the item

① When we choose to fill in the use of the item, the value of this box is the value of the current item + the value after removing the weight [1]

Explanation [1] : First, the total capacity of the backpack – the weight of the current item to obtain a value. Then take the maximum value for that weight of the previous item

② If you do not select the item, the value of the item is the same as the value of the previous item

Finally take the bigger of the two

Code thinking

Define a weight array w[], a price array V [], a two-dimensional record array result[] [] with rows representing weight and columns representing price

// value int[] v = {1500,3000,2000}; Int [] w = {1,4,3}; Int [][] result = new int[v.length + 1][4 + 1];Copy the code

Result [0] [j] = 0, result[I] [0] = 0

Result [I] [j] = result[i-1] [j] = result[i-1]

③ You can choose: the current value of goods + backpack capacity to remove the current maximum value of the weight of the goods.

result[i][j] = Math.max(result[i-1][j], v[i-1] + result[i-1][j – w[i-1]]);

How is the maximum value calculated?

For example, in the last cell of this example, the value should be 2000+1500=3500

max(result[3-1] [4] , v[2] + result[3-1] [4 – w[3-1]])

Result [3-1] [4] = 1500

result[3-1] [4 – w[3-1]] = result[2] [4 – 3] =

The upward weight is 4-3, i.e., the maximum value at result[2] [1] 1500 + the current item value v[2]2000 = 3500

The key code

for (int i = 1; i < result.length; i++) { for (int j = 1; j < result[0].length; J++) {/ / judgment weight if [I - 1] > j (w) {/ / is greater than the given weight, then can not choose, adopt the above result [I] [j] = result [I - 1) [j]; } else {/ / do not choose and select larger values result in [I] [j] = math.h Max (result [j], [I - 1] v [I - 1) + result [I - 1) [j] [I - 1 - w]); }}}Copy the code

Now we can only get the maximum value, but we don’t know the specific scheme, so we need to backtrack

Start with the last number of the two-dimensional array and compare it to the value of the previous line. If the value is equal, the item is not added to the backpack (line –).

If it is not equal, the item is added to the backpack, then line –,

To determine the weight of the previous item, subtract the weight of the current item from the total weight, so column = column – weight of the current item

Method implementation

int i = result.length-1; int j = result[0].length-1; while (i > 0 && j > 0) { if (result[i][j] ! Println (result[I -1][j]) {if (result[I -1][j]) {if (result[I -1][j]) {if (result[I -1][j]) {if (result[I -1][j]) {if (result[I -1][j]) {if (result[I -1][j]) { j -= w[i-1]; i--; } else { i--; }}Copy the code

The results are as follows

KMP algorithm

Origin of name

The string search algorithm developed by three people is knuth-Morris-Pratt, abbreviated as KMP algorithm

Stem what of

Matching string with high efficiency compared to traditional brute force cracking efficiency

Brute force cracking: Refers to the comparison of one by one, and the mismatch is moved one by one until the match is successful or fails

Anyway, THE KMP algorithm is not rigid, unlike brute force which always mismatches by moving backwards one and then one by one.

Instead, it uses its own algorithm to move multiple bits to reduce the number of matching and improve the operation efficiency

Focus on

Find the maximum length of the common part of the prefix and suffix

What is a prefix and what is a suffix

A prefix is head without tail, and a suffix is tail without head

APPLE, for example

Prefixes are: A | | AP APP | APPL

Suffixes are: | E LE | PLE | PPLE

You need to find partial matching values for the pattern string and store them in the next table

What is a partial match

The maximum length of a string whose prefix and suffix are equal is a partial match

As is shown in

A is zero without A prefix or suffix

AB is prefix A, suffix B, and none of the same parts are 0

ABC is prefixed with A,AB is suffixed with C,BC, and none of the same parts are 0

I’m not going to do the same thing with 0

ABCDA the prefix A, AB,ABC,ABCD, the suffix A,DA,CDA,BCDA, has A common A and is 1 in length, so the value is 1

Move digit = number of matched characters (subscript of current target string) – Next table match value (value of subscript in unmatched table)

The difficulties in

1, how to create a partial match table, easy to understand, how to implement the write out

The first array is 0, if the second number is equal to the first character, the match value is +1, and next[the subscript of the second number] = the match value. So AAA gets an array of [0,1,2]

What if it’s not equal

The first idea is to set the match to zero and iterate.

But the essence of the KMP algorithm is that the match value = next[current match value subscript -1] rather than 0

while (j > 0 && str.charAt(i) ! = str.charAt(j)) { // j = result[j - 1]; j = 0; }Copy the code

For example, “AACDAAA”

If it is j=0, the result is [0, 1, 0, 0, 1, 2, 1], which is the wrong value

If j = result[j-1], result[0, 1, 0, 0, 1, 2, 2]

2. How to match target string with pattern string

Process thinking

Assume that the target string is “BBC ABCDAB ABCDABCDABDE” and the mode string is “ABCDABD”.

Next = [0, 0, 0, 0, 1, 2, 0]

If the pattern string pointer bit is 0, the target string pointer is always moved back one bit when the first digit of the target string never matches

The position of the first start match is as follows:

If D does not match space, then the pointer to pattern string is space -next [pattern string subscript -1]

Next [6-1] = move 2 bits as follows

Next [2-1] = 0 bits. If it is 0 bits, move it back one bit to the next matching position

Find D! =C, move next[6-1] = 2 bits, then compare one by one and find a perfect match, return the subscript of the first position

The key code

Public static int CAL (String str1, String str2) {static int CAL (String str1, String str2); // create mode string pointer int j = 0; Int [] next = next(str2); while (i < str1.length()) { if (j == str2.length()) { // return i - str2.length(); // return i-j; } if (str1.charAt(i) == str2.charAt(j)) { i++; j++; } else if (j == 0){// If (j == 0); } else {I = i-next [j-1];} else {I = i-next [j-1]; j = 0; } } return -1; Public static int[] next(String STR) {int[] result = new int[str.length()]; result[0] = 0; for (int i = 1, j = 0; i < str.length(); i++) { while (j > 0 && str.charAt(i) ! = str.charAt(j)) { j = result[j - 1]; j = 0; } if (str.charAt(i) == str.charAt(j)) { j++; } result[i] = j; } return result; }Copy the code

Greedy algorithm

What is a greedy algorithm

When solving the problem, each step chooses to use the best or optimal way, so as to achieve the best result of an algorithm

But the result is not necessarily the optimal solution, is relatively close to the optimal solution. Find the most suitable solution, but not necessarily the optimal solution

Here’s a scenario

As is shown in the figure, there are 5 radio stations, and a scheme is developed so that the least number of stations can be selected to cover all areas

The difficulties in

1. How to traverse to obtain the radio stations with the most coverage area

Every time, we find the radio station with the largest coverage, and then remove it from the total set. We continue in this way until the total radio station is found out. This is also greedy thinking, always looking for a relatively large or relatively good one. Why is it relative? For example, in this case, there are three radio stations covering three cities, so the selected stations may not be the best, but they are always higher in priority than those covering two cities

2. Under what circumstances should the largest radio station be covered

When the radio station has uncovered regions (size>0) and (when the Max defined has no initial value or the number of regions covered by the current traversal is greater than the previous number of stations)

The current radio station is the optimal choice, which is also the idea of greedy algorithm

The key code

while (allArea.size()>0) { String max = null; for (Map.Entry<String,String> entry : radio.entrySet()) { String k = entry.getKey(); String v = entry.getValue(); String[] ss = v.split(", "); for (String str : ss) { temp.add(str); } temp.retainAll(allArea); If (temp. The size () > 0 && (Max = = null | | temp. The size () > radio. Get (Max). The split (", "). The length)) {Max = k; } temp.clear(); } // Add the schema to the result set result.add(Max); For (String STR: radio.get(Max).split(", ")) {allarea.remove (STR); } // radio.remove(max); }Copy the code

Backtracking algorithm

Scenario, for example,

The chessboard is a classic backtracking problem

Small game address: horse step fly chess

Problem description

If given a board of m x N, given the initial position of a horse’s pieces, according to the rule of the horse’s move day, how can you move the whole board with only one entry for each square?

Of course, there are checkerboards or some starting points where the horse can’t walk the entire board.

Problem resolution

The horse always has a choice at any point. If it can, it takes a point. If it can’t, it goes back to the previous step and tries again at the next point

How do I get the next optional point of the current point?

If the distance of the original point {1,2} is satisfied, and the currently available point is returned according to the horse day rule

// List< orphi > next(int[][] act, int I, int j) {int size = act.length; List<Luozi> ls = new ArrayList<>(); / / four quadrant the if (I + 1 < size & j + 2 < size && act [I + 1) = = 0) [m + 2] {the ls. The add (new Luozi (I + 1, j + 2)); } if (i+2 < size && j+1 < size && act[i+2][j+1] ==0) { ls.add(new Luozi(i+2,j+1)); } / / three quadrants if (I + 1 < 2 > the size & & j - = 0 && act [I + 1] [j - 2] = = 0) {ls. The add (new Luozi (I + 1, j - 2)); } if (i+2 < size && j-1 >= 0 && act[i+2][j-1] ==0) { ls.add(new Luozi(i+2,j-1)); } / / a quadrant of the if (I - 1 > = 0 && j - 2 > = 0 && act [I - 1] [j - 2] = = 0) {ls. The add (new Luozi (j - I - 1, 2)); } if (i-2 >= 0 && j-1 >= 0 && act[i-2][j-1] ==0) { ls.add(new Luozi(i-2,j-1)); } / / second quadrant the if (I - 1 > = 0 && j + 2 < size && act] [I - 1 + 2 [j] = = 0) {ls. The add (new Luozi (I - 1, j + 2)); } if (i-2 >= 0 && j+1 < size && act[i-2][j+1] ==0) { ls.add(new Luozi(i-2,j+1)); } return ls; }Copy the code

Once you have a rule, you write code using that rule

1. First set the horse’s current coordinate point to step (current step number).

2. Use the next method to get the optional coordinate points

3. Iterate over all coordinate points and recursively call the current method to continue operation 12

4. If the number of steps is not reached after traversal, the current coordinate point is set to 0 (unused) for backtracking

5, if the number of steps reached the predetermined number of steps or the program execution (for loop can be executed, there is an exit) end of the program. (Because there is not necessarily only one solution, it takes a long time to go through all of them)

void DFS(int[][] act,int i, int j,int step) { act[i][j] = step; If (step == act.length * act.length) {// Print (act) if (step == act.length * act.length); } // We get the set of coordinates for the orphorphic particles, List< orphi > ls = next(act, I, j); Sort (ls,act); //sort(ls,act); For (orphi l: ls) {// DFS(ACT, L.I, L.j,step+1); If (step < act.length * act.length) {act[I][j] = 0; if (step < act.length * act.length) {act[I][j] = 0; }}Copy the code

Existing problems

The disadvantage of this algorithm is that the list returned will be different and the path taken will be different because everyone is writing rules in different order. The resulting execution time is often very long. The above algorithm can be obtained by the counter, in the 6 x 6 checkerboard, starting point {1,3} case, to find the first solution, need to execute the method 11195506 times! If I use an 8 x 8 board, I can’t get all the way.

So how to improve efficiency?

Greedy thought

As shown in the figure, which point is more appropriate among the six points is the point to improve the efficiency of the algorithm. The algorithm was not defined before, and was only obtained in accordance with the order of judgment in the rules

The next available point of these 6 points can be directly obtained to see which of these 6 points has the least next available point and which point is the relative best choice. Selecting the least “exit” points for the search in this way is local tuning and reduces the amount of backtracking. The test showed that the number of times the method was executed with greedy thoughts became 36 times! The 8 x 8 was only used 64 times!

What does the number of backtracking have to do with finding a point?

I’m going to have fewer and fewer points to traverse, and I’m going to have more and more success, right?

In fact, I think its traversal mode should be from the outer circle to the inner circle, which is a step-by-step traversal process, with less backtracking. Imagine that if you leave yourself to jump, you will often keep backtracking to adjust the previous position at the last stage, which may be the advantage brought by less backtracking.

// Incrementing sort, Void sort(List<Luozi> ls,int[][] act) {ls. Sort (new Comparator<Luozi>() {@override public int compare(Luozi o1, Luozi o2) { int a = next(act, o1.i, o1.j).size(); int b = next(act, o2.i, o2.j).size(); if (a < b) { return -1; } else if(a == b) { return 0; } else { return 1; }}}); }Copy the code

Finally, we just need to sort the ls that we got before

List<Luozi> ls = next(act, i, j); // Open the comment sort(ls,act); For (orphi l: ls) {// DFS(ACT, L.I, L.j,step+1); }Copy the code