Niu Guest network left cheng Yun teacher’s algorithm introduction class

Violence recursive

The principle of

Hannotta problem

The problem

  • Print n layers of Hanover tower moving from left to right

thought

There are six processes, left to right, left to center, center to left, center to right, right to left, and right to center, nested within each other

Left to right

  • Move 1- N-1 to the middle bar
  • Move N from the far left to the far right
  • Move 1 “-n-1 to the rightmost bar

In the left to

  • Move 1-n-1 from left to right
  • N moves from left to middle
  • Move 1- N-1 from right to center

.

code

package class08; Public class Code01_Hanoi {public static void Hanoi (int n) {if (n > 0) {func(n, "left "," right ", "middle "); } // 1~ I disk target is from -> to, Public static void func(int N, String from, String to, String other) { if (N == 1) { // base System.out.println("Move 1 from " + from + " to " + to); } else { func(N - 1, from, other, to); System.out.println("Move " + N + " from " + from + " to " + to); func(N - 1, other, to, from); } } public static void printAllWays(int n) { leftToRight(n); } public static void leftToRight(int n) { if(n== 1) { System.out.println("Move 1 from left to right"); return ; } leftToMid(n-1); System.out.println("Move " +n + " from left to right"); midToRight(n-1); } public static void leftToMid(int n) { if(n== 1) { System.out.println("Move 1 from left to mid"); return ; } leftToRight(n-1); System.out.println("Move " +n + " from left to mid"); rightToMid(n-1); } public static void midToRight(int n) { } public static void rightToMid(int n) { } public static void main(String[] args) { int n = 3; hanoi(n); }}Copy the code

example

Prints all subsequences of a string, including empty strings

(Models tried from left to right)

  • Ensure that the characters are in sequence
  • “ABC” = “a, b, c, ab, ac, BC, ABC, null
  • Violence exhaustive

Prints the entire permutation of the string

Train of thought

  • Full permutation, previously selected characters, after can not be selected.

code

package class08; import java.util.ArrayList; import java.util.HashSet; import java.util.List; public class Code03_PrintAllPermutations { public static ArrayList<String> Permutation(String str) { ArrayList<String> res = new ArrayList<>(); if (str == null || str.length() == 0) { return res; } char[] chs = str.toCharArray(); process(chs, 0, res); return res; } // str[i..] // string [0.. I -1] // string [0.. I -1] Public static void process(char[] STR, int I, ArrayList<String> res) { if (i == str.length) { res.add(String.valueOf(str)); } boolean[] visit = new boolean[26]; // visit[0 1 .. 25] for (int j = i; j < str.length; j++) { if (! visit[str[j] - 'a']) { visit[str[j] - 'a'] = true; swap(str, i, j); process(str, i + 1, res); swap(str, i, j); } } } public static void swap(char[] chs, int i, int j) { char tmp = chs[i]; chs[i] = chs[j]; chs[j] = tmp; } public static List<String> getAllC(String s) { List<String> ans = new ArrayList<>(); ArrayList<Character> set = new ArrayList<>(); for (char cha : s.toCharArray()) { set.add(cha); } process(set, "", ans); return ans; } public static void process(ArrayList<Character> list, String path, List<String> ans) { if (list.isEmpty()) { ans.add(path); return; } HashSet<Character> picks = new HashSet<>(); For (int index = 0; int index = 0; int index = 0; index < list.size(); index++) { if (! picks.contains(list.get(index))) { picks.add(list.get(index)); String pick = path + list.get(index); ArrayList<Character> next = new ArrayList<>(list); next.remove(index); process(next, pick, ans); } } } public static void main(String[] args) { String s = "aac"; List<String> ans = getAllC(s); for (String str : ans) { System.out.println(str); }}}Copy the code

Digital transformation

Topic request

Train of thought

  • Enter the original string 111, where 012 follows. For the ith node, I can be converted either by itself or with I +1

  • But we need to determine whether I and I plus 1 exceed 26, because 26 is at most z

  • For example, “102”, if 1 makes a decision on its own, then 0 cannot make a decision on its own, nor can 0 and 2 make a decision, so 0 can only be valid together

code

package class08; public class Code06_ConvertToLetterString { public static int number(String str) { if (str == null || str.length() == 0)  { return 0; } return process(str.toCharArray(), 0); } // if (I...) {// if (I...) { Public static int process(char[] STR, int I) {if (I == str.length) {// base case The previous path represents a valid method return 1; If (STR [I] == '0') {if (STR [I] == '0') {return 0; } / / STR [I] is not '0' character if (STR [I] = = '1') {int res = process (STR, I + 1); If (I + 1 < str.length) {res += process(STR, I + 2); // (I and I +1) as separate parts, how many subsequent methods} return res; } if (str[i] == '2') { int res = process(str, i + 1); // I as a separate part, how many subsequent methods // (I and I +1) as a separate part and does not exceed 26, Then how many ways the if (I + 1 < STR. Length && (STR + 1] [I > = '0' && STR [I + 1] < = '6')) {res + = process (STR, I + 2); // (I and I +1) as separate parts, how many subsequent methods} return res; } // str[i] == '3' ~ '9' return process(str, i + 1); } public static int dpWays(String s) { if (s == null || s.length() == 0) { return 0; } char[] str = s.toCharArray(); int N = str.length; int[] dp = new int[N + 1]; dp[N] = 1; for (int i = N - 1; i >= 0; i--) { if (str[i] == '0') { dp[i] = 0; } else if (str[i] == '1') { dp[i] = dp[i + 1]; if (i + 1 < N) { dp[i] += dp[i + 2]; } } else if (str[i] == '2') { dp[i] = dp[i + 1]; if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) { dp[i] += dp[i + 2]; } } else { dp[i] = dp[i + 1]; } } return dp[0]; } public static void main(String[] args) { System.out.println(number("11111")); }}Copy the code

Knapsack problem

Topic request

code

package class08; public class Code07_Knapsack { public static int getMaxValue(int[] w, int[] v, int bag) { return process(w, v, 0, 0, bag); } // index current item number //w [index] current item weight //v [index] current item value //alreadyW: 0 to index-1 has made the decision, the current weight //bag: Total weight of bag (fixed parameter) //index... Free choice of all subsequent cargo, Public static int process(int[] w, int[] v, int index, int alreadyW, Int bag) {if (alreadyW > bag) {return -1; } if (index == w.length) {return 0; } int p1 = process(w, v, index + 1, alreadyW, bag); Int p2next = process(w, v, index + 1, alreadyW + w[index], bag); // The value of the current goods + the subsequent value int p2 = -1; if (p2next ! = -1) { p2 = v[index] + p2next; } return Math.max(p1, p2); } public static int maxValue(int[] w, int[] v, int bag) { return process(w, v, 0, bag); } // only rest space left, // index... Free choice of goods, Public static int process(int[] w, int[] v, int index, int rest) { if (rest <= 0) { // base case 1 return 0; } // rest >=0 if (index == w.length) { // base case 2 return 0; } int p1 = process(w, v, index + 1, rest); int p2 = Integer.MIN_VALUE; if (rest >= w[index]) { p2 = v[index] + process(w, v, index + 1, rest - w[index]); } return Math.max(p1, p2); } public static int dpWay(int[] w, int[] v, int bag) { int N = w.length; int[][] dp = new int[N + 1][bag + 1]; for (int index = N - 1; index >= 0; index--) { for (int rest = 1; rest <= bag; rest++) { dp[index][rest] = dp[index + 1][rest]; if (rest >= w[index]) { dp[index][rest] = Math.max(dp[index][rest], v[index] + dp[index + 1][rest - w[index]]); } } } return dp[0][bag]; } public static void main(String[] args) { int[] weights = { 3, 2, 4, 7 }; int[] values = { 5, 6, 3, 19 }; int bag = 11; System.out.println(maxValue(weights, values, bag)); System.out.println(dpWay(weights, values, bag)); }}Copy the code

Take a card

Train of thought

  • In the first case, when there’s only one card left, you just take the last card

  • If I take the leftmost card, calculate my score as ARr [L] +S (ARr, L+1, R).

  • If I take the card on the right, calculate my score as ARr [R] +S (ARr, L, R-1).

  • Taking the maximum of the two cases above is my choice

  • Where S is the black box function, because the first hand and the back hand are interchangeable roles, when the first hand draws cards, its role becomes the back hand

code

package class08; public class Code08_CardsInLine { public static int win1(int[] arr) { if (arr == null || arr.length == 0) { return 0; } return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1)); } public static int f(int[] arr, int i, int j) { if (i == j) { return arr[i]; } return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1)); } public static int s(int[] arr, int i, int j) { if (i == j) { return 0; } return Math. Min (f(arr, I + 1, j), f(arr, I, j-1)); / / to make them take the smallest value} public static int win2 (int [] arr) {if (arr = = null | | arr. Length = = 0) {return 0; } int[][] f = new int[arr.length][arr.length]; int[][] s = new int[arr.length][arr.length]; for (int j = 0; j < arr.length; j++) { f[j][j] = arr[j]; for (int i = j - 1; i >= 0; i--) { f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]); s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]); } } return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]); } public static void main(String[] args) { int[] arr = { 1, 9, 1 }; System.out.println(win1(arr)); System.out.println(win2(arr)); }}Copy the code

N Queen problem

Train of thought

  • Assuming that the position of the previous queen is (a, b), then the position of the next queen is (c, d), since it is executed from the top down, it is guaranteed that the queens are not in line with each other

  • By comparing B and D to determine whether the queens are co-listed

  • By comparing | | = = c – a – b | | d to determine whether in a slash

code

package class08; public class Code09_NQueens { public static int num1(int n) { if (n < 1) { return 0; } // record[0] ? record[1] ? record[2] int[] record = new int[n]; Return process1(0, record, n); } // subtext: Record [0.. I -1] queen, any two queen must not be in line, not in line, not colslash // currently came to the I line // record[0.. I -1] said before the line, put the queen position // n represents the whole total number of lines // return value is, put all queen, Public static int process1(int I, int[] record, int n) {if (I == n) {public static int process1(int I, int[] record, int n) { } int res = 0; for (int j = 0; j < n; J ++) {// The current row is in row I, try all columns in row I -> j // the current row queen, put in column j, will not and before (0.. If (isValid(record, I, j)) {record[I] = j; if (record [I] = j; res += process1(i + 1, record, n); } } return res; } // Record [0.. I -1] Public static Boolean isValid(int[] record, int I, int j) {for (int k = 0; k < i; Some k lines k++) {/ / queen if (j = = record [k] | | math.h abs (record [k] - j) = = math.h abs (I - k)) {return false. } } return true; } // Please do not exceed 32 queen questions, if type is changed to long, You can calculate 64 queen problem public static int num2 (int n) {if (n < 1 | | n > 32) {/ / throw new RuntimeException (" problem is too big, difficult to calculate "); // Expected error: use a try catch, for example, to catch an exception and tell the user that the input type is wrong: return 0; } int limit = n == 32 ? -1 : (1 << n) - 1; return process2(limit, 0, 0, 0); } rightDiaLim: rightDiaLim: rightDiaLim: rightDiaLim: rightDiaLim: rightDiaLim: rightDiaLim: rightDiaLim: rightDiaLim: rightDiaLim: rightDiaLim: rightDiaLim: rightDiaLim: rightDiaLim: rightDiaLim I can't put the queen in position one, Public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) { if (colLim == limit) { // base case return 1; } / / all candidate the queen's position, all int pos = limit on the pos & (~ (colLim | leftDiaLim | rightDiaLim)); int mostRightOne = 0; int res = 0; while (pos ! = 0) { mostRightOne = pos & (~pos + 1); pos = pos - mostRightOne; res += process2(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, (rightDiaLim | mostRightOne) >>> 1); } return res; } public static void main(String[] args) { int n = 14; long start = System.currentTimeMillis(); System.out.println(num2(n)); long end = System.currentTimeMillis(); System.out.println("cost time: " + (end - start) + "ms"); start = System.currentTimeMillis(); System.out.println(num1(n)); end = System.currentTimeMillis(); System.out.println("cost time: " + (end - start) + "ms"); }}Copy the code