Interview Questions for Liver Factory Everyday? Have you mastered these mandatory interview algorithms?

table of Contents

One, recursive method

2. Greedy Method

Three, backtracking method

Fourth, divide and conquer

Five, dynamic programming method


Hello. Hello, I am the little gray ape, a programmer who can write bugs!

After a few days, I finally updated it. Recently, I read a lot of interview questions and related requirements from big companies. Among them, the inspection of commonly used algorithms is almost necessary, but for the learning of common algorithms, only remember a few programs. No, it requires in-depth work on the definition, ideas, principles, and problem-solving of the algorithm.

Today, let’s take a closer look at the basic definitions, ideas, principles, and problem-solving methods of common algorithms.

One, recursive method

Algorithm definition

Recursion refers to a method in which a procedure or function calls itself directly or indirectly in its definition or description. When using a recursive strategy, there must be a clear end condition for recursion, called a recursive exit. In the process of recursive calls, the system opens up a stack to store the return points and local variables of each layer.

Algorithm principle

The ability of recursion lies in the use of a limited language to define an infinite set of objects . Generally speaking, recursion requires boundary conditions, recursive forward segments and recursive return segments. When the boundary conditions are not met, go forward recursively, and return recursively when the boundary conditions are met,

Problem solving steps

Recursive thinking is a typical method of solving problems through reverse thinking. The problem-solving process is mainly divided into two steps:

1. Analyze the recursive relationship. Get recursive.

2. Determine the termination conditions to prevent infinite loops,

Features and typical applications

Too many recursions can easily cause stack overflow, so the scale of the problem should be considered when using recursive algorithms. It has two common application scenarios.

Occasion 1: The definition of data is defined recursively (Fibonacci function)

Scenario 2: The structure of the data is defined recursively (tree traversal, graph search)

Common application cases

Recursively find the factorial of a number, first find the factorial of a number smaller than it, and then multiply the number.

package 典型算法题; public class 递归求阶乘 { 	public static void main(String[] args) {		System.out.println(f(3));	} 	static int f(int n){		if(n==1)   //当n=1的时候,条件终止		return 1;		else 		return n*f(n-1);   //求n-1的阶乘,再次缩小变为n-1*n-2,n就会越来越小	}    }

2. Greedy Method

Algorithm definition

The greedy method is a method that does not pursue the optimal solution, but only hopes to obtain a more satisfactory solution . The greedy method always makes the best choice based on the current situation without considering all possible overall situations, so the greedy method does not require retrospective ,

Algorithm idea

The greedy method is usually carried out in a top-down manner, working in stages, making successive greedy choices in an iterative manner, and each time a greedy choice is made, the problem is reduced to a smaller sub-problem. At each stage, always choose the solution that thinks the current best solution, and then promote the solution from the small solution to the larger solution. It only needs to maintain the current best solution as the process progresses, and adopt the "if it is beneficial, take precedence." 'The greedy man's strategy.

Problem solving steps

The problem-solving process is mainly divided into three steps

Starting from a certain initial solution of the problem, solve it cyclically;

Find a solution element of a feasible solution

A feasible solution of the problem by combining all the solution elements

Features and typical applications

This type of problem generally has two important properties, namely the greedy selection property and the optimal substructure property. The typical applications of the greedy method include the knapsack problem and the activity arrangement problem.

Common application cases

In the general backpack problem, the item is detachable, that is, it can be divided into any parts for loading, and the ultimate goal is that the backpack is full (that is, the remaining capacity is 0), and the total value is as high as possible.

package 典型算法题; import java.util.Arrays; //背包问题(贪心算法)public class GreedyPackage {   private int MAX_WEIGHT = 150;  private int[] weights = new int[]{35,30,60,50,40,10,25};  private int[] values = new int[]{10,40,30,50,35,40,30};   private void packageGreedy(int capacity,int[] weights,int[] values){          int n = weights.length;          double[] r = new double[n]; //性价比数组          int[] index = new int[n];   //按性价比排序物品的下标          for(int i = 0;i < n;i++){              r[i] = (double) values[i] / weights[i];              index[i] = i;//默认排序      }       double temp = 0;    //对性价比进行排序      for(int i = 0;i < n - 1;i++){          for(int j = i + 1;j < n;j++){              if(r[i] < r[j]){                  temp = r[i];                  r[i] = r[j];                  r[j] = temp;                  int x = index[i];                  index[i] = index[j];                  index[j] = x;              }          }      }       //将排序好的重量和价值分别存到数组中      int[] w1 = new int[n];      int[] value1 = new int[n];       for(int i = 0;i < n;i++){          w1[i] = weights[index[i]];          value1[i] = values[index[i]];       }      int[] x = new int[n];      int maxValue = 0;      for(int i = 0;i < n;i++){          if(w1[i] <= capacity){   //表明还可以装得下              x[i] = 1;   //表示该物品被装了              capacity = capacity - w1[i];              maxValue += value1[i];          }      }      System.out.println("总共放下的物品数量:" + Arrays.toString(x));      System.out.println("最大价值为:" + maxValue);  }    public static void main(String[] args){      GreedyPackage g = new GreedyPackage();      g.packageGreedy(g.MAX_WEIGHT,g.weights,g.values);  }}

Three, backtracking method

Algorithm definition

The backtracking method is a kind of optimal search method, which searches forward according to the optimal conditions to achieve the goal. But when you explore a certain step, you find that the original choice is not good or the goal is not achieved, so you go back one step and choose again. This technique of going back and going again if you fail to get through is called the backtracking method, and a certain state that meets the backtracking condition is called As the "backtracking point".

Algorithm principle

The backtracking method is an exhaustive search method that satisfies certain constraints. It requires the designer to find all possible methods and then choose one of them. If the method is not feasible, test and explore the next possible method.

Problem-solving steps,

The problem-solving process is mainly divided into three steps,

For the given problem, define the solution space of the problem;

Determine the solution space structure that is easy to search,

Search the solution space in a depth-first manner, and use a pruning function to avoid invalid searches during the search process

Features and typical application scenarios

Backtracking is a special case of recursion. But it is different from the general recursive method. One of the distinguishing features of using the backtracking method to solve problems is that the solution space of the problem is dynamically generated during the search process. At any time, the algorithm only saves the path from the root node to the current expansion node.

Typical applications include: maze search, N queen problem, knight parade, regular expression matching, etc.

Common application cases

As for the years Blue Bridge Cup tournament Java province Zhenti set "cut grid" is typical of backtracking thought:

package 一三年省赛真题; import java.util.Scanner; public class Year2013_t10 { 	static int[][] g;	static int[][] sign;	static int m;	static int n;	static int s=0;	//记录格子中元素的总和	static int answer = Integer.MAX_VALUE;	//最终格子数	public static void main(String[] args) {		Scanner scanner = new Scanner(System.in);		m = scanner.nextInt();		//输入格子的宽		n = scanner.nextInt();		//输入格子的高		g = new int[n][m];			sign = new int[n][m];		for (int i = 0; i < n; i++) {			for (int j = 0; j < m; j++) {				g[i][j] = scanner.nextInt();	//为格子赋值				s+=g[i][j];			}		}		move(0, 0, 0, 0);		System.out.println(answer);	}		/**	 * 记录格子的遍历过程	 * @param i 移动的横坐标	 * @param j 移动的纵坐标	 * @param step 步数	 * @param sum 格子中元素的总和	 * */	public static void move(int i,int j,int step,int sum) {		//如果该格子坐标不在范围内,或该格子已经走过,则返回		if (i==n||i<0||j<0||j==m||sign[i][j]==1) {			return;		}		// 如果当前数值和是总和的一半		if (sum*2==s) {			answer = Math.min(answer, step);	//对格子数(步数)与符合要求的格子数比较,取出最小值		}		sign[i][j] = 1;		//对走过的格子进行标记,表示格子已经走过		move(i+1, j, step+1, sum+g[i][j]);	//down		move(i-1, j, step+1, sum+g[i][j]);	//up		move(i, j-1, step+1, sum+g[i][j]);	//left		move(i, j+1, step+1, sum+g[i][j]);	//right		sign[i][j] = 0;		//将该格子重新置于未走过的状态(回溯算法)			} }

Fourth, divide and conquer

Algorithm definition

The divide-and-conquer method divides a complex problem into two or more identical or similar sub-problems, and then divides the sub-problems into smaller sub-problems. Until the last sub-problem can be simply solved directly, and the solution of the original problem is the combination of the solutions of the sub-problems.

Algorithm principle

Decompose a large-scale problem into several smaller-scale sub-problems, find the solution of each sub-problem, and then combine the solutions of each sub-problem into the solution of the entire problem. When solving sub-problems, often continue to use the same strategy, that is, continue to decompose the problem, solve one by one, and finally merge the solutions. This kind of continuous use of the same strategy to solve smaller-scale sub-problems, often uses recursion in programming language implementation The method of calling is implemented,

Problem solving steps

The process of divide and conquer is mainly divided into three steps,

Decomposition, decompose the original problem into several smaller, independent sub-problems in the same form as the original problem;

solve. If the sub-problem is small and easy to be solved, solve it directly, otherwise, solve each sub-problem recursively;

merge. Combine the solutions of each sub-problem into the solution of the original problem.

Features and typical applications

The problem can be easily solved if it is reduced to a certain extent, and it can be broken down into several smaller-scale identical problems. The solutions of the sub-problems decomposed by the problem can be combined into the solution of the problem, and the sub-problems decomposed by the problem are independent of each other.

Common application cases

For example, quick sort, find the k-th smallest element from the array a[].

Divide and conquer detailed case

package 一八年省赛真题; import java.util.Random;  public class Year2018_Bt5 { 	public static int quickSelect(int a[],int l,int r,int k) {		Random rand = new Random();		int p = rand.nextInt(r-l+1) + l;		int x = a[p];		int tmp = a[p]; a[p] = a[r]; a[r] = tmp;		int i = l, j = r;		while (i<j) {			while (i<j&&a[i]<x) i++;			if (i<j) {				a[j] = a[i];				j--;			}			while (i<j&&a[j]>x) j--;			if (i<j) {				a[i] = a[j];				i++;			}					}				a[i] = x;		p = i;		if(i - l + 1 == k) return a[i];		if(i - l + 1 < k) return quickSelect(a, i + 1, r, k - i + l - 1);	//填空		else return quickSelect(a, l, i - 1, k);			}		public static void main(String[] args) {		int a[] = {1,4,2,8,5,7};		//1,2,4,5,7,8		//输出5		System.out.println(quickSelect(a, 0, 5, 6));	} }

Five, dynamic programming method

Algorithm definition

The dynamic programming method is used to solve optimization problems containing overlapping sub-problems.

The basic idea is: decompose the original problem into similar sub-problems, and find the solution of the original problem through the solution of the sub-problems in the process of solving. Dynamic programming is actually a technology that exchanges space for time. It is in the process of realization. In the process, various states in the production process have to be stored. So its space complexity is greater than other algorithms.

Algorithm principle

The dynamic programming method usually solves each sub-problem in a bottom-up manner, and makes decisions in multiple stages. The basic idea is to divide the complex problem into several interrelated stages according to the characteristics of time and space. After selecting the direction of the system, the reverse In this direction of travel, calculate from the end to the beginning, and look for a certain decision for each stage one by one, so that the entire process is optimal, so it is also called the reverse decision process.

Problem solving steps

The problem-solving process is mainly divided into two steps,

Divide the stage, divide the problem into several stages according to the time or space characteristics of the problem, pay attention to these stages, they must be in order or sortable (that is, no backwardness);

Choose the state, and express the various objective situations in which the problem develops to various stages in different states,

Features and typical applications

Regardless of the past state and decision, for the state formed by the previous decision, the remaining decisions must constitute the optimal strategy. After the stages are arranged in a certain order, for a given stage state, it has been The state of each stage cannot directly affect its future decision-making, but only through the current state. Finally, the key to considering the use of dynamic programming is to resolve redundancy.

Common application cases

A typical case of dynamic programming is to find the largest common substring of a string

The problem of the maximum common substring length is: What is the maximum length that can be matched among all substrings of two strings. For example: "abcdkkk" and "baabcdadabc", the longest common substring that can be found is "abcd", So the maximum common substring length is 4.

Detailed analysis of the "largest common substring" problem

public class Year2017_Bt6 {		static int f(String s1,String s2) {		char[] c1 = s1.toCharArray();		char[] c2 = s2.toCharArray();				int [][]a = new int[c1.length+1][c2.length+1];//		"abcdkkk" 和"baabcdadabc",		int max = 0;		//利用循环来进行动态规划,模拟矩阵中的匹配过程		for (int i = 1; i < a.length; i++) {			for (int j = 1; j < a[i].length; j++) {				//如果两个字符匹配成功				if (c1[i-1]==c2[j-1]) {					a[i][j] = a[i-1][j-1]+1;	//填空					//判断当前字符的长度是否大于已经匹配到的串的长度					if (a[i][j]>max) max=a[i][j];				}			}		}		return max;	//返回匹配到的最长的字符串	}		public static void main(String[] args) {		int n = f("abcdkkk", "baabcdadabc");		System.out.println(n);	} }

The above are the principles, applications and case studies of our five common basic algorithms. I believe you should be able to have a new understanding of these algorithms after reading them. It is recommended to review them slowly after collecting!

If you don’t understand, you can leave a message in the comment area!

I think it's good, remember three waves in a row!

Little Grey Ape takes you to write bugs together!