Writing in the front

  • Full text data structure

recursive

  • Method calls itself, passing in a different variable each time
  • The call mechanism, in turn, can eventually break the cycle of calling itself one by one (last in, first out)

Matters needing attention

  • When a method is executed, a separate protected space (stack space) is created;
  • The local variables of the method are independent and do not affect each other.
  • If a reference type variable is used in a method, the reference type variable is shared (such as a number group).
  • The recursion has to approach the condition that leads to the recursion, otherwise it’s an infinite recursion, an exceptionStackOverFlowError;
  • When a method completes execution, a return is encountered, and the result is returned to the person who called the method. When the method completes execution, this layer of method is also removed from the stack

Maze tracing problem

  • Shortest path out of the maze
  • Through the way of hypothesis, continue to try the next point, until there is a return value, in reverse order backtracking, affecting the original point
  • For example,AThe point has four directions, and after each of these directions is tried, then theAThe result of itself is returned toAThe last one, andAIn the attempt, also includesAThe next attempt to contain
  • Each point tries four directions in its own position and affects the previous point
/** * rule I,j indicates the starting point 6,5 indicates the end point * mazeArr[I][j] = 0 indicates that there is no walk, 1 indicates that there is a wall, 2 indicates that there is a wall, 3 indicates that there is a walk, but there is no walk * in the maze, to determine the strategy, down -> right -> up -> left; @param j * @return Return true */ public static Boolean getWay(int[][] mazeArr, int i, int j) { if(mazeArr[6][5] == 2) { return true; } else {if (mazeArr[I][j] == 0) {// If (mazeArr[I][j] == 0) {// If (mazeArr[I][j] == 0) {// If (mazeArr[I][j] == 0) {// If (mazeArr[I][j] == 0) {// If (mazeArr[I][j] == 0) {// If (mazeArr[I][j] == 0); If (getWay(mazeArr, I + 1, j)) {return true; } else if (getWay(mazeArr, I, j + 1)) {return true; } else if (getWay(mazeArr, i-1, j)) {return true; } else if (getWay(mazeArr, I, j-1)) {return true; [I][j] = 1; return false; } } else { //mazeArr[i][j] ! =0 //1 indicates that the wall cannot be walked through //2 indicates that it was walked through, so return false, and make the previous point choose another path //3 indicates dead path return false; }}}Copy the code

The shortest path

  • By adjusting the strategy, there are actually4 * 4 = 16There are only four stupid ways to do it
  • The call,countAndShowAndRecoverMethodRecord the number of 2's, map output and restore; I’m going to store the number of strategies 2 toArrayList, and then output the smallest, which can also exist better map
Int [] up = new int[]{-1, 0}; int[]{-1, 0}; int[] down = new int[]{1, 0}; int[] right = new int[]{0, 1}; int[] left = new int[]{0, -1}; List<int[]> Strategy1 = Array. asList(up, Down, right, left); List<int[]> Strategy2 = Array. asList(Down, Up, left, right); List<int[]> Strategy3 = Array. asList(left, Up, right, down); List<int[]> Strategy4 = Array. asList(Right, down, up, left); HashMap<String, List<int[]>> strategies = new HashMap<>(); strategies.put("strategy1", strategy1); strategies.put("strategy2", strategy2); strategies.put("strategy3", strategy3); strategies.put("strategy4", strategy4); Set<String> set = strategies.keySet(); ArrayList<Integer> counts = new ArrayList<>(); for (String s : set) { List<int[]> strategy = strategies.get(s); System.out.println("--------" + s + "---------"); GetWay (mazeArr, 1, 1, strategy); counts.add(countAndShowAndRecover(mazeArr)); } counts.sort((o1, o2) -> o1 - o2); System.out.println(" count. Get (0));Copy the code
  • getWayMethods to modify
public static boolean getWay(int[][] mazeArr, int i, int j, List<int[]> strategy) { .... If (mazeArr[I][j] == 0) {// If (mazeArr[I][j] == 0) {// If (mazeArr[I][j] == 0) {// If (mazeArr[I][j] == 0) {// If (mazeArr[I][j] == 0) {// If (mazeArr[I][j] == 0) {// If (mazeArr[I][j] == 0); if (getWay(mazeArr, i + strategy.get(0)[0], j + strategy.get(0)[1], strategy)) { return true; } else if (getWay(mazeArr, i+ strategy.get(1)[0], j + strategy.get(1)[1], strategy)) { return true; } else if (getWay(mazeArr, i + strategy.get(2)[0], j+ strategy.get(2)[1], strategy)) { return true; } else if (getWay(mazeArr, i+ strategy.get(3)[0], j + strategy.get(3)[1], strategy)) { return true; }... }Copy the code

Eight Queens problem

  • No two queens can be on an 8 by 8 squareSame column, same row, same slash

  • Each recursion changes the position of the current queen to determine the position of the queen below;
  • For instance1 2 3 4To permutation and combination, first fix1Fixed again2, modify3, 4,The location of the; fixed1Fixed again3Modify the2, 4Only the eight queens problem has additional requirements
  • Call, starting with the 0th queen
eq.check(0);
Copy the code
  • Placement method
Private void check(int n) {if (n == Max) {//n == Max = 8 print(); return; } for (int i = 0; i < max; Arr [n] = I; arr[n] = I; If (judge(n)) {// Check (n+1); // When n= 7 starts to return, n= 6 starts I ++, try the following possibility // when n=1, n=1 of I ++, start the next loop, until n=1 completes the Max loop} // If the conflict occurs, place it in the next I +1 column, } // Check exits only if n=8 or if Max loop is completed // If Max loop is completed return; }Copy the code
  • Conditions for testing
Private Boolean judge(int n) {private Boolean judge(int n) {private Boolean judge(int n) {for (int I = 0; i < n; I ++) {if (arr[I] == arr[n] // if (arr[I] == arr[n] // if (arr[I] == arr[n]) |x1 - x2| = |y1 - y2| || Math.abs(n-i) == Math.abs(arr[n] - arr[i])) { return false; } } return true; }Copy the code
Private void print() {count ++; for (int i : arr) { System.out.print(i + " "); } System.out.println(); }Copy the code