Writing in the front

  • Full text of data structure and algorithm

Binary search algorithm (non-recursive)

  • Only for lookups from an ordered queue
  • The core is to change the value of mid
/** * @param arr the array to be searched * @param target number of targets * @return the corresponding subscript, */ public static int binarySearch(int[] arr, int target) {int left = 0; int right = arr.length - 1; int mid; while (left <= right) { mid = (left + right) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] > target) { right = mid - 1; mid = (left + right) / 2; } else { left = mid + 1; mid = (left + right) / 2; } } return -1; }Copy the code

Hannotta (divide-and-conquer algorithm)

  • The divide-and-conquer algorithm divides a complex problem into two or more sub-problems, then divides the sub-problems into smaller sub-problems, and then merges the solutions of all the smaller problems, which is the original solution

  • A,B,C ->A tower,B tower,C tower; Num for number
  • Three disks for example
For example, if you want to move 3 disks, the goal of the above two disks is to move to tower B and enter the second layer. In this recursion, ABC ->ACB is the first step and enter the third layer, ABC ->ABC, the first disk A->C is the second step and exit the third layer, ABC ->ACB, the second disk A->B is the third step, Step 4, jump out of the third layer, jump out of the second layer, and return to the first layer. Step 5, enter the second layer. The goal of the two disks of B is to move to tower C, after entering the recursion, step 6, enter the third layer. At this time, ABC ->BCA, the first disk B->A step 7, jump out of the third layer, return to the second layer, ABC ->BAC, the second disk B->C step 8, enter the third layer, ABC ->ABC, the first disk A->C, complete step 9, jump out of layer 3, 2 and 1Copy the code
public static void hanoitower(int num, char a, char b, Char c) {// Only if (num == 1) {system.out.println (" first disk from "+ a + "->" + c); If (num - 1, A, C, B); if (num - 1, A, C, B); if (num - 1, A, C, B); if (num - 1, A, C, B); / / put the tray on the bottom of the System. A - > C out. The println (" first "+ num +" A dish from "+ A +" - > "+ C); Hanoitower (num -1, B, A, C); hanoitower(num -1, A, C); }}Copy the code

summary

Transformation of the tower, for example, if there are four plates on the top three plate as A set of the ultimate goal is to B tower, but at this time for the top two stage goal is C plate tower, because only the two plate moved to the top of the tower C, to ensure that the third tower tray to B, then that means the first two dish to begin with A – > C, then from C – > B; Hanoitower (num -1, a, C, B); hanoitower(num -1, a, C, B); hanoitower(num -1, a, C, B); Entering the final layer of recursion, after completion of the first mobile disk is about to move the second dish A – > C, and then the first dish – > B, C, achieve the aim of the second set, the hanoitower (num 1, B, A, C), and completes the four examples of the plate, the top two plate of the first phase of the mission A – > C

According to the passage above, can be summarized, Hanoi decomposition, is to the number of different plates, each dish has different tasks, according to different plate, has A different order to ABC tower, for example, four dish in the top of the two plates of mobile, A – > C the first stage, the order of ABC, B is the middle tower, let the first plate moves to B; However, in the second stage, when the top three disks all reach B, the top two disks need to go from B->A in the sequence of BCA. The first disk needs to reach C first, and the second disk can reach A. However, for the movement of the top two disks of the three disks, the first stage is A->B, the order is ACB, C is the middle tower, the first disk needs to move to C first; In the second phase, B->C. For the two disks on B, the sequence is BAC. A is the middle tower

In fact, the above specific steps can not explain the two recursive processes clearly, but it can be sure that for different numbers of disks and disks of different layers, the target is different, the tower is also different, by passing parameters to adjust the corresponding order of different disks

Divide a pile of disks into two pieces, the first is all the disks on the top, the second is the bottom disk, the task of the first as a parameter is A -> B, B -> C, and the task of the last is a-> C, so through continuous recursion, ABC will naturally correspond to different towers for different disks

Knapsack problem (Dynamic programming)

  • Dynamic programming, the problem to be solved into a number of problems, first to solve the sub-problem, the solution of the next sub-stage is based on the solution of the previous sub-stage; Fill out a form and work your way up
Int [] w = {1, 3}; Int [] val = {1500, 3000, 2000}; Int m = 4; Int n = val. Length; Two / / / / item number two dimensional array, by completing this form deduction int [] [] v = new int [n + 1] [m + 1]; Int [][] path = new int[n+1][m+1]; //v[0][j] = 0 v[i][0] = 0 for (int i = 0; i < v.length; i++) { v[i][0] = 0; } for (int i = 0; i < v[0].length; i++) { v[0][i] = 0; } // for (int I = 1; i < v.length; i++) { for (int j = 1; j < v[i].length; J ++) {if (w[i-1] > j) {// if (w[i-1] > j) {// If (w[i-1] > j) {v[I] = v[i-1][j]; } else {// If the added part of the weight w[i-1] <= j, can be filled with multiple //val index starting from 0, V [i-1][j] val[i-1] + v[i-1][J-w [i-1]] // For example, If the items weight backpack weight of 4 to 3 / / there are two possibilities, so on the first round for the pack of 4 value / / second, items backpack weight for weight of the value of 3 + 1, the sum of the value of the weight of 1 refers to the value of the weight of the last round of / / because, every time to calculate the position, can compare, //v[I][j] = math.max (v[i-1][j], val[i-1] + v[i-1][j-w[i-1]]); / / in order to track pack, to use the if - else handling the if (v [I - 1) [j] > (val [I - 1) + v [I - 1) [j] [I - 1 - w]]) {v [I] [j] = v [I - 1) [j]; V [I][j] = val[i-1] + v[i-1][j-w[i-1]]; v[I] = val[i-1] + v[i-1][j-w[i-1]]; path[i][j] = 1; } } } } for (int i = 0; i < v.length; i++) { for (int j = 0; j < v[i].length; j++) { System.out.print(v[i][j] + " "); } System.out.println(); } for (int i = 0; i < path.length; i++) { for (int j = 0; j < path[i].length; j++) { System.out.print(path[i][j] + " "); } System.out.println(); } int i = path.length - 1; int j = path[0].length - 1; While (I > 0 && j > 0) {if (path[I][j] == 1) {// If (path[I][j] == 1) { If path[3][4]==1 is found, then item 3 has been put into the backpack // But there is still backpack weight 1 left, then we need to go through the backpack weight 1 // Find the backpack weight 1, find path[1][1], find the backpack weight 1, then item 1 has been put into the backpack. System.out.println(I); system.out.println (I); j -= w[i-1]; } I --;} I --;} I --;} I --;} I --; }Copy the code