1. Violent recursion
In layman’s terms, trying out an answer in a radical, exhaustive way is called Force Recursive.
Violent recursion is an attempt to turn a problem into a scale-down subproblem of the same kind. The subproblem generalizes the larger problem through the decision-making process, and the subproblem is broken down into smaller subproblems until the subproblem is broken down to a base case where it can be solved without trying again.
Violent attempts do not record the solution of every sub-problem, only try the most important, how to optimize, there are natural methods.
2. Hannotta problem
Title: Print the entire process of the n layer Hannott tower moving from the left pole to the right pole. As hannott’s tower moves, the small disk can press the big disk, but the big disk cannot press the small disk.
Analysis:
Tell me about a better attempt.
First, we do not consider the absolute position of the rod, the abstract problem, only set from rod, to rod, and other rod. From, to, or other rods can be reused. Specifically, leftmost, rightmost, and middle rods can be used.
Determine the current overall task: move all disks 1~ I on the FROM bar to bar.
Top-down molecular tasks:
Step 1: Move all disks 1 ~ (i-1) on the FROM rod to the other rod.
Step 2: Move the i-th disk from the FROM bar onto the to bar.
Step 3: Move the 1st ~ (i-1) disk on other rod from other rod to to rod.
Note:
How do I keep the big plate under the small plate?
I just have to make sure that when PLATE I moves, the big plate is below the small plate, and then the subprocess of plate I-1 moves is going to keep the same rule. The same rule applies to I minus 2 plates.
In violent recursion, a lot of people try to figure out the big picture, and then they can’t figure it out.
When you’re trying, you don’t have to. An attempt is when you define a standard for all processes, and as long as your parent does not violate the standard, the child does not violate the standard either. As you try, you just have to think about how you’re going to solve the problem in this part. As long as the decision to remove this part is right, then the whole must be right.
Code:
public static void hanoi(int n) {
process(n, "Left"."Right"."In");
}
/** * try method *@paramI 1 to the disk star of I@paramFrom Move starting bar *@paramTo move the destination bar *@paramOther Another bar */
public static void process(int i, String from, String to, String other) {
// Base case When there is only one disk, the disk can be placed on any rod
if (i == 1) {
System.out.println("Move 1 from " + from + " to " + to);
return ;
}
process(i - 1, from, other, to);
System.out.println("Move " + i + " from " + from + " to " + to);
process(i - 1, other, to, from);
}
Copy the code3. Character string subsequence
Print all subsequences of a string, including empty strings.
Analysis:
The classic try method, from left to right, is to make or not make a decision for each positional element.
Code:
public static void printAllSubStr(String str) {
char[] charSequence = str.toCharArray();
process(charSequence, 0.new ArrayList<Character>());
}
/** * try method *@paramCharSequence String Disassembled character sequence *@paramI The subscript * of the current character in a character sequence@paramChars The selected character */ for the current path
public static void process(char[] charSequence, int i, List<Character> chars) {
// When trying to get to the end of the path, directly output the string consisting of all the character sequences of the path
if (i == charSequence.length) {
printList(chars);
return ;
}
// Add the current character down
List<Character> addCurChars = copyList(chars);
addCurChars.add(charSequence[i]);
process(charSequence, i + 1, addCurChars);
// Go down without adding the current character
List<Character> notAddCurChars = copyList(chars);
process(charSequence, i + 1, notAddCurChars);
}
/ / print the List
public static void printList(List<Character> chars) {
for (Character character : chars) {
System.out.print(character);
}
System.out.println();
}
/ / copy List
public static List<Character> copyList(List<Character> chars) {
return new ArrayList<>(chars);
}
Copy the codeSpace saving writing, the idea is to reuse the original character sequence, by modifying the current position of the character, so as to achieve or not the current character.
The time complexity indices are the same for both methods.
public static void printAllSubStr(String str) {
char[] charSequence = str.toCharArray();
process(charSequence, 0);
}
public static void process(char[] charSequence, int i) {
if (i == charSequence.length) {
// When trying to get to the end of the path, directly output the string consisting of all the character sequences of the path
System.out.println(String.valueOf(charSequence));
return ;
}
// Add the current character down
process(charSequence, i + 1);
// Erases the current character from the original character sequence
char tmp = charSequence[i];
charSequence[i] = 0;
// Go down without adding the current character
process(charSequence, i + 1);
// Restore the original character sequence
charSequence[i] = tmp;
}
Copy the code4. String arrangement
Print all permutations of a string, requiring no duplicate permutations.
Analysis:
How to try it: from left to right, swap each subsequent character with the current character to make a decision.
It is also modified on the basis of the original string, using the characteristics of recursive code fragments, reuse the original character sequence, so as to save space.
Code:
public static void printAllArrange(String str) {
char[] charSequence = str.toCharArray();
ArrayList<String> list = new ArrayList<>();
process(charSequence, 0, list);
/ / print
for(String string : list) { System.out.println(string); }}public static void process(char[] charSequence, int i, ArrayList<String> list) {
// If the current character sequence is traversed to the end, the current character sequence is stored and printed
if (i == charSequence.length) {
list.add(new String(charSequence));
return ;
}
// Iterate over every character after the current character
for (int j = i; j < charSequence.length; ++ j) {
// Swaps the character with the current character
swap(charSequence, i, j);
// Recurse to the next character
process(charSequence, i + 1, list);
// Restore the stringswap(charSequence, j, i); }}public static void swap(char[] charSequence, int i, int j) {
char temp = charSequence[i];
charSequence[i] = charSequence[j];
charSequence[j] = temp;
}
Copy the codeIn the code above, if there are no repeating characters in STR, the result will be fine, and if there are, the result will be in a repeating arrangement. Because if STR does not duplicate a character, other characters replace a character only once. If there is a duplicate character, the duplicate character is replaced more than once by another character.
If you want to have no double permutation in a string, there are two ways to think about it.
- Using the code above, wash the data after you have all the results, washing out the duplicate data.
- Using the following code, when attempting to swap characters, determine if the target replacement character has been present at the current location, if so, it cannot be swapped.
The first one is slow because you have to take all the paths, get all the results, and then wash the data.
The second option is better because when you branch, you kill the impossible branch and get the faster method (branch bound).
The time complexity index of the two schemes is the same, because in the worst case, the pruning strategy of the second case may not work, and there is no difference between the first scheme and the second one. However, the second scheme optimizes the constant term under different data conditions.
public static void process(char[] charSequence, int i, ArrayList<String> list) {
if (i == charSequence.length) {
list.add(new String(charSequence));
return ;
}
// Record whether each character (a-z) is tried. Default is all false
boolean[] flag = new boolean[26];
// Iterate over every character after the current character
for (int j = i; j < charSequence.length; ++ j) {
int index = charSequence[j] - 'a';
// Determines whether the string has been tried at that location
if(! flag[index]) { swap(charSequence, i, j); process(charSequence, i +1, list);
swap(charSequence, j, i);
// Record an attempt
flag[index] = true; }}}Copy the code5. Longest increasing subsequence
Find the length of the longest increasing subsequence in an array. For example: [1, 5, 2, 4, 3], the longest increasing subsequence has two, respectively [1, 2, 4], [1, 2, 3], return 3.
Analysis:
How to try it: Start with each element and go back through all the elements, deciding whether to add an increasing sequence.
Code:
public static int longestIncreasingSubSequence(int[] arr, int begin) {
if (begin == arr.length - 1) {
return 1;
}
int longestLength = 1;
for (int i = begin; i < arr.length; i ++) {
if (arr[i] > arr[begin]) {
longestLength = Math.max(longestIncreasingSubSequence(arr, i) + 1, longestLength); }}return longestLength;
}
Copy the code6. Pick up cards
Given an integer array arr, the cards representing different values are arranged in a line. Player A and player B take each card in turn, with player A taking first and player B second, but each player can only take the left or right card at A time. Player A and Player B are extremely smart. Please return the final winner’s score.
Such as:
arr = [1, 2, 100, 4]
At the beginning, player A can only take one or four. If player A takes away 1 at the beginning, the arrangement becomes [2, 100, 4], then player B can take away 2 or 4, and then it is player A’s turn…
If player A takes away 4 at the beginning, the arrangement becomes [1, 2, 100], and then player B can take away 1 or 100, and then player A’s turn continues…
Player A, being the smartest person in the world, is not going to take 4 first, because after 4 player B is going to take 100. So player A will take the 1 first, making the rank [2, 100, 4], and then player B will take the 100 either way. Player A wins with A score of 101. So return 101.
Analysis:
The decision is given that each player can only take the left or right most card at a time.
How to try it: In each round, draw either the leftmost card or the rightmost card.
Code:
public static int win(int[] arr) {
// base case
if (arr == null || arr.length == 1) {
return 0;
}
// The first player is PLAYER A, and the second player is player B
return Math.max(offensive(arr, 0, arr.length - 1), defensive(arr, 0, arr.length - 1));
}
// The first function
public static int offensive(int[] arr, int left, int right) {
// In the case of first hand only one card, directly take
if (left == right) {
return arr[left];
}
// Try to take left card and right card, then back hand
return Math.max(arr[left] + defensive(arr, left + 1, right), arr[right] + defensive(arr, left, right - 1));
}
// Back hand function
public static int defensive(int[] arr, int left, int right) {
// In the case of the back hand, there is only one card, no card to take
if (left == right) {
return 0;
}
// Play first in both cases, choosing the smaller card because my opponent is sure to give me the worse card
return Math.min(offensive(arr, left + 1, right), offensive(arr, left, right - 1));
}
Copy the code7. Reverse stack
You are given a stack, please reverse the stack, do not apply additional data structures, only use recursive functions. How to do that?
Analysis:
This is a recursive technique problem, in the violent recursion, for the recursive technique is relatively high, so you can try to do the problem.
First, we need to implement a function that removes the bottom element from the stack and returns it, leaving the rest of the stack unchanged.
Code:
public static void reverseStack(Stack<Integer> stack) {
// base case
if (stack.isEmpty()) {
return ;
}
// Save the current element at the bottom of the stack
int item = process(stack);
// Proceed to the next processing
reverseStack(stack);
// Push the saved bottom element back onto the stack
stack.push(item);
}
// This function takes out the bottom element of the stack and keeps the position of other elements in the stack unchanged
public static int process(Stack<Integer> stack) {
// pop the stack and save the top element
int item = stack.pop();
// When the stack is empty, the last element at the top of the stack is not pushed and returns directly
if (stack.isEmpty()) {
return item;
}
// Get the last top of the stack element
int lastItem = process(stack);
// Push other top elements back onto the stack
stack.push(item);
// Returns the last element at the top of the stack
return lastItem;
}
Copy the code8. Numeric string conversion
Topic:
1 is A, 2 is B, 3 is C… 26 corresponds to Z. A numeric string such as “111” can be converted to “AAA”, “AK”, or “KA”.
Given a string STR consisting of only numeric characters, find the number of conversion results.
Analysis:
This is also a classic left to right approach.
For example, when it comes to the position I, assuming that the decision of 0 ~ (i-1) has been determined, we only focus on all variants from the I and the I position onwards, and how many effective global decisions there are combined with the previous decision. The specific details are handled by Coding.
Code:
public static int transformStrCount(String str) {
return process(str.toCharArray(), 0);
}
// I indicates that the transformation starts from the ith bit
public static int process(char[] chars, int i) {
// The last bit of STR is also converted, which is a feasible transformation scheme
if (i == chars.length) {
return 1;
}
STR cannot be converted without a corresponding letter. This conversion scheme is not feasible
if (chars[i] == '0') {
return 0;
}
// The character converted to the ith bit is 1
if (chars[i] == '1') {
// Convert the i-th bit separately to form a scheme
int count = process(chars, i + 1);
// Check the existence of the character following the I bit
if (i + 1 < chars.length) {
// If so, the i-th bit can be combined with the following character to form a scheme
count += process(chars, i + 2);
}
return count;
}
// The character converted to the ith bit is 2
if (chars[i] == '2') {
// Convert the i-th bit separately to form a scheme
int count = process(chars, i + 1);
// Check whether the character after the I bit exists, and if so, whether it is small and equal to 6
if (i + 1 < chars.length && chars[i + 1] > ='0' && chars[i + 1] < ='6') {
// If it exists and is less than 6, you can combine the character after the i-th bit to form a scheme
count += process(chars, i + 2);
}
return count;
}
// The characters converted to the i-th bit are 3-9 and can only be converted to the i-th bit alone
return process(chars, i + 1);
}
Copy the code9. Backpack problem
Topic:
Weights [I] and values[I] represent the weights and values of item I, respectively. Given a positive number “bag”, which means a bag with a weight of “bag”, you cannot carry more than this weight.
What is the maximum value of items you can fit in?
Analysis:
Always try left to right, number 0 want or no, number 1 want or no…
Code:
There are two conventional ways of writing this problem, the first being a simplified version of the second.
The first way is good because the first way only has two mutable arguments, I and alreadyWeight; The second version takes three variables I, alreadyWeight, and alreadyValue.
When we build trial methods, we have a principle of “try to build a method with the simplest form of mutable arguments and the fewest number of mutable arguments”. The simplest form of argument can be expressed as a single value, but if you use linked lists, hash tables, etc., as a form of argument, it can get very complicated. This is the basis for the subsequent modification of DP. The simpler the form of variable parameters and the fewer the number, the easier the modification of DP.
The first:
public static int knapsackProblem(int[] weights, int[] values, int bag) {
return process(weights, values, bag, 0.0);
}
/** * Make a decision on the current item I *@paramWeights All items weight *@paramValues All item values *@paramMaximum weight of bag *@paramAlreadyWeight Weight of the bag that was made before the decision *@paramI Current item number I *@returnMaximum value */
public static int process(int[] weights, int[] values, int bag, int alreadyWeight, int i) {
// If all items are tried
if (i == weights.length) {
return 0;
}
If the current bag is overweight
if (alreadyWeight > bag) {
return 0;
}
// Put item I and not put item I generate a large value return
return Math.max(
// Put item no. I into the bag
values[i] + process(weights, values, bag, alreadyWeight + weights[i], i + 1),
// Do not put item I into the bag
process(weights, values, bag, alreadyWeight, i + 1)); }Copy the codeThe second:
public static int knapsackProblem(int[] weights, int[] values, int bag) {
return process(weights, values, bag, 0.0.0);
}
public static int process(int[] weights, int[] values, int bag, int alreadyWeight, int alreadyValue, int i) {
// All items are tried
if (i == weights.length) {
return alreadyValue;
}
If the current bag is overweight
if (alreadyWeight > bag) {
return 0;
}
return Math.max(
// Put item no. I into the bag
process(weights, values, bag, alreadyWeight - weights[i], alreadyValue + values[i], i + 1),
// Do not put item I into the bag
process(weights, values, bag, alreadyWeight, alreadyValue, i + 1)); }Copy the code10. [A]
Topic:
The N Queens problem is that N queens are placed on an N * N chessboard, requiring that any two queens are not in the same row, in different columns, or on the same diagonal line.
Given an integer n, return the number of pendulum ways for the queen of n.
Analysis: Only one Queen can be placed in each row. In each row, try column by column from left to right.
Code:
public static int nQueen(int n) {
if (n < 1) {
return 0;
}
int[] record = new int[n];
return process(n, record, 0);
}
/ * * *@paramN, n row, n column *@paramRecord record[I] = j indicates a Queen in row I and column J *@paramI The row currently making the decision *@returnNumber of placement methods */
public static int process(int n, int[] record, int i) {
// All rows have already made the decision, which is a legal solution
if (i == n) {
return 1;
}
int result = 0;
// select * from 'I'
for (int j = 0; j < n; j ++) {
if (isValid(record, i, j)) {
/ / put queen
record[i] = j;
// Go to the next line to make the decision
result += process(n, record, i + 1); }}return result;
}
// Check whether it is legal to put a Queen in row I and column j
public static boolean isValid(int[] record, int i, int j) {
// All Queen rows from 0 to i-1 are not collars
for (int k = 0; k < record.length; k ++) {
if (record[k] == j || Math.abs(k - i) == Math.abs(record[k] - j)) {
return false; }}return true;
}
Copy the code