Directory
Topic 1: Give you a string and ask to print out all the subsequences of the string (subsequences cannot be repeated)
Question 2: Print all permutations of a string.
Topic 3: For topic 2, it is required to remove repeated elements
Question 4: Given a string, it is required to print all the subsets that can be formed by the characters in the string, and the subset has no repeated values.
Question 5: Give you a stack, please reverse the order of this stack, you cannot apply for additional data structures, only recursive functions can be used.
Recursion is a transition in preparation for dynamic programming. After the recursion is written, the code structure can be optimized a lot, but the disadvantage is that the logic is not easy to understand. For a good recursion, parameter design is particularly important.
Topic 1: Give you a string, ask to print out all subsequences of this string (subsequences cannot be repeated)
What needs to be noted in this question is that a string is given, and the string must be in order. For example, if the string is abc, then cba will definitely not appear in its suborder. Because this order is completely reversed. Therefore, the suborder cannot change the overall order of the original string, and can be combined freely while maintaining the overall order.
package code03. recursion_06;
import java.util.ArrayList;
import java.util.List;
/**
* Give you a string, ask to print out all subsequences of this string (subsequences cannot be repeated)
*/
public class StringSequence_02
{
public static List<String> getChildSuquence(String str)
{
char[] chars = str. toCharArray();
List<String> result = new ArrayList<>();
//path parameter is very important, it is a complete string spliced layer by layer
//According to the number of layers of recursive traversal, different strings are formed, very smart
String path = "";
func(chars, result, 0, path);
return result;
}
/**
* The string is ordered, so the subsequence must follow the overall sequence of the string. For example, abc, the subsequence must not
* In case of ba or ca.
*
* The current recursive logic is from back to front, that is, to find the last element. The subscripts are:
* N-2... N
*N-3...N
*N-4...N
* 0...N
* N represents the subscript of the last element of the array. And N + 1 represents the length of the array,
* At this point, there is no corresponding subscript, so it is considered to be an export
*
* Suppose the string is abc, then its subset is
* 1. empty string
* 2.c
* 3.b
* 4.bc
* 5.a
* 6. 52 combination to get ac, 53z combination to get ab, 54 combination to get abc
*/
static void func (char[] chars, List<String> list, int index, String path)
{
/**
* Recursive exit.
* index is the subscript of the last character. And index + 1 is the length of the array
* So you need to jump out of recursion
*/
if (index == chars. length) {
// exclude duplicate elements
if (!list. contains(path)) {
list. add(path);
}
return;
}
// Keep looking down until the end of the array, an empty string is given by default
func(chars, list, index + 1, path); //here index + 1 is very clever, because the index value itself has not changed
//The value of path will be changed here, it is very smart to use
//Each method plays against a method stack, and the variable path has a local variable table. When the method ends, the local variable table is destroyed
//Therefore, the path changed here only takes effect in the current method. Will not affect the path value of the same name in other methods
path = path + String. valueOf(chars[index]);
//Start splicing according to the path here.
func(chars, list, index + 1, path);
}
public static void main(String[] args) {
String test = "abc";
//String test = "abcc";
List<String> result = getChildSuquence(test);
for (String str : result) {
System.out.println(str);
}
}
}
Explain this question:
The design idea is based on the subscript index of the array, and the recursion is until the last element of the subscript is found.
At this point, if the last element is c. If c is not included, then path is an empty string and func collects an empty string. If c is included, what func collects is the concatenation of the empty string and c. That is c. Recursion ends, return to the previous layer
At this time, return to the element b, and the elements not including b are collected at this time. That is, the empty string and c are collected. path reassembled. At this time, path is a combination of an empty string and b. Func operation again. The inside of func is divided into two logics: not including path and including path. At this time, it is aimed at c. If c is not included, then b is collected. If c is included, the combination of b and c is collected, ie bc
And so on…….
The whole flow chart is as follows:
The collection results are: empty string, c, b, bc, a, ac, ab, abc
Topic 2: Print all permutations of a string.
The sorting of this string refers to the order that the string can be changed arbitrarily, not the substring. For example: abc, one of which is cba, but ab a ac, etc. do not belong to all sorts
package code03. recursion_06;
import java.util.ArrayList;
import java.util.List;
/**
* Given a string, ask to print all sorts of this string.
* Note: The sorting of this string refers to the order in which the string can be changed arbitrarily, not the substring
* For example: one of abc is cba, but ab a ac, etc. do not belong to all sorts
*/
public class PrintAllFullStr_03
{
public static List<String> getAllStr(String str)
{
List<String> result = new ArrayList<>();
String path = "";
char[] chars = str. toCharArray();
List<Character> list = new ArrayList<>();
for (char cha : chars) {
list. add(cha);
}
func(list, result, path);
return result;
}
static void func (List<Character> chars, List<String> result, String path)
{
if (chars. isEmpty()) {
result. add(path);
}
else {
for (int i = 0; i < chars. size(); i ++ ) {
char cur = chars. get(i);
//clear scene
chars. remove(i);
func(chars, result, path + cur);
// restore scene
chars. add(i, cur);
}
}
}
public static void main(String[] args) {
String test = "abc";
//String test = "acc";
List<String> result = getAllStr(test);
for (String str : result) {
System.out.println(str);
}
}
}
In fact, there is another more general solution to this question, and the idea is basically the same as that of question 1.
package code03. recursion_06;
import java.util.ArrayList;
import java.util.List;
/**
* Given a string, ask to print all sorts of this string.
* Note: The sorting of this string refers to the order in which the string can be changed arbitrarily, not the substring
* For example: one of abc is cba, but ab a ac, etc. do not belong to all sorts
*/
public class PrintAllFullStr_03_opt
{
public static List<String> getAllStr(String str)
{
char[] chars = str. toCharArray();
List<String> result = new ArrayList<>();
String path = "";
func(chars, result, 0, path);
return result;
}
static void func (char[] chars, List<String> result, int index, String path)
{
if (index == chars. length) {
result. add(path);
}
else {
for (int i = index; i < chars. length; i ++ ) {
swap(chars, index, i);
func(chars, result, index + 1, path + chars[index]);
swap(chars, index, i);
}
}
}
public static void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
public static void main(String[] args) {
String test = "abc";
//String test = "acc";
List<String> result = getAllStr(test);
for (String str : result) {
System.out.println(str);
}
}
}
For the general solution, we found that since chs is always sorted dynamically, the internal elements will not decrease. Therefore, the parameters can be optimized a little:
package code03. recursion_06;
import java.util.ArrayList;
import java.util.List;
/**
* Given a string, ask to print all sorts of this string.
* Note: The sorting of this string refers to the order in which the string can be changed arbitrarily, not the substring
* For example: one of abc is cba, but ab a ac, etc. do not belong to all sorts
*/
public class PrintAllFullStr_03_opt2
{
public static List<String> getAllStr(String str)
{
char[] chars = str. toCharArray();
List<String> result = new ArrayList<>();
func(chars, result, 0);
return result;
}
static void func (char[] chars, List<String> result, int index)
{
if (index == chars. length) {
result. add(String. valueOf(chars));
}
else {
for (int i = index; i < chars. length; i ++ ) {
swap(chars, index, i);
func(chars, result, index + 1);
swap(chars, index, i);
}
}
}
public static void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
public static void main(String[] args) {
String test = "abc";
//String test = "acc";
List<String> result = getAllStr(test);
for (String str : result) {
System.out.println(str);
}
}
}
In fact, the idea of solving this problem is to gradually determine each position, and the parameter to record the position is index. Then the for loop fills the current position with the remaining array elements in turn. By analogy, a typical depth-first traversal algorithm. The flowchart is as follows:
Question 3: For question 2, it is required to remove repeated elements
Removing duplicate elements is actually divided into result filtering and condition filtering. Result filtering is to go through all the processes, and deduplicate through the result set when the results are finally collected. The conditional filter is excluded from the source, and the performance is higher. Take question 2 as an example. If the string is acc. When the subscript is 1, c appears once, and when the next c appears again, it is directly excluded.
Result filtering:
package code03. recursion_06;
import java.util.ArrayList;
import java.util.List;
/**
* Given a string, ask to print all sorts of this string, and
* These sorted strings have no duplicate data
*
* Result filtering: After the process is executed, it is judged whether to repeat the filtering when it is put into the collection.
* The disadvantage is obvious, regardless of whether it is repeated or not, all processes will go through again, and the performance is low
*
*/
public class PrintAllFullStrNoRepeat_04
{
public static List<String> getAllStr(String str)
{
char[] chars = str. toCharArray();
List<String> result = new ArrayList<>();
String path = "";
func(chars, result, 0);
return result;
}
static void func (char[] chars, List<String> result, int index)
{
if (index == chars. length) {
/**
* Result filtering, you can use set directly
* The list is used here, and it is necessary to determine whether there are duplicate elements in the set
*/
if (!result. contains(String. valueOf(chars))) {
result. add(String. valueOf(chars));
}
}
else {
/**
* index represents the beginning of the current position.
* For example, if the index is 0, it is the beginning array that locks the 0 position. for loop
* is to find a b c respectively occupying the position of 0 as the beginning. For example a**. b**, c**
*
* When the index is 1, it means that all data are found as the beginning of the subscript position of 1. ie *a*, *b*, *c*
*
*/
for (int i = index; i < chars. length; i ++ ) {
swap(chars, index, i);
func(chars, result, index + 1);
swap(chars, index, i);
}
}
}
public static void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
public static void main(String[] args) {
//String test = "abc";
String test = "acc";
List<String> result = getAllStr(test);
for (String str : result) {
System.out.println(str);
}
}
}
Condition filter:
package code03. recursion_06;
import java.util.ArrayList;
import java.util.List;
/**
* Given a string, ask to print all sorts of this string, and
* These sorted strings have no duplicate data
*
* Result filtering: After the process is executed, it is judged whether to repeat the filtering when it is put into the collection.
* The disadvantage is obvious, regardless of whether it is repeated or not, all processes will go through again, and the performance is low
*
*/
public class PrintAllFullStrNoRepeat_04_opt
{
public static List<String> getAllStr(String str)
{
char[] chars = str. toCharArray();
List<String> result = new ArrayList<>();
String path = "";
func(chars, result, 0);
return result;
}
static void func (char[] chars, List<String> result, int index)
{
if (index == chars. length) {
result. add(String. valueOf(chars));
}
else {
//The range of ASCII code is 0-255, it can represent all characters
//Each recursion is a new one, which is very clever. Need to figure out carefully
boolean[] visited = new boolean[256];
for (int i = index; i < chars. length; i ++ ) {
/**
* index is the current position. The first entry is definitely a pass. occupy current position
*
* The original character array is a b c The original array is acc
* 1. a b c a c c The original c c position has not changed. That is to say, the second position is occupied by the first c
* 2. a c b a c c At this time, c c is the position after exchange. That is, the second c wants to occupy the second position again as the beginning of the subsequent array, occupy this position repeatedly, and pass it directly
* 3. b a c c a c
* 4. b c a c c a
* 5. c a b c a c in the same way
* 6 c b a c c a in the same way
*/
if (!visited[chars[i]]) {
visited[chars[i]] = true;
swap(chars, index, i);
func(chars, result, index + 1);
swap(chars, index, i);
}
}
}
}
public static void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
public static void main(String[] args) {
//String test = "abc";
String test = "accb";
List<String> result = getAllStr(test);
for (String str : result) {
System.out.println(str);
}
}
}
Title 4: Given a string, it is required to print all the subsets that can be formed by the characters in the string, and the subset has no repeated values.
After understanding Question 2, this question is actually very simple.
package code03. recursion_06;
import java.util.ArrayList;
import java.util.List;
/**
* Given a string, ask to print all sorts of this string.
* Note: The sorting of this string refers to the order in which the string can be changed arbitrarily, not the substring
* For example: one of abc is cba, but ab a ac, etc. do not belong to all sorts
*/
public class PrintAllStr_05_opt
{
public static List<String> getAllStr(String str)
{
char[] chars = str. toCharArray();
List<String> result = new ArrayList<>();
String path = "";
func(chars, result, 0, path);
return result;
}
static void func (char[] chars, List<String> result, int index, String path)
{
if (index == chars. length) {
result. add(path);
}
else {
boolean[] visited = new boolean[256];
for (int i = index; i < chars. length; i ++ ) {
visited[chars[i]] = true;
swap(chars, index, i);
func(chars, result, index + 1, path + chars[index]);
if (index < chars. length-1) {
result. add(path + chars[index]);
}
swap(chars, index, i);
}
}
}
public static void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
public static void main(String[] args) {
String test = "abc";
//String test = "acc";
List<String> result = getAllStr(test);
System.out.println("length is " + result.size());
for (String str : result) {
System.out.println(str);
}
}
}
Question 5: You are given a stack, please reverse the order of this stack, you cannot apply for additional data structures, you can only use recursive functions.
package code03. recursion_06;
import java.util.Stack;
/**
* Title:
* Give you a stack, please reverse the stack,
* cannot apply for additional data structures,
* Only recursive functions can be used. How to achieve?
*/
public class StackReverse_06 {
public static void reverse (Stack<Integer> stack)
{
if (stack == null || stack.isEmpty()) {
return;
}
// Get the bottom element of the stack
int result = func(stack);
/**
* Continue to reverse the remaining elements in the stack
* For example, from top to bottom in the stack is 3 2 1
* Get result 1 for the first time
* The second time get result 2
* Get result 3 for the third time
*/
reverse(stack);
/**
* Then after the last recursion ends, put the element
* The order is put in 1 2 3. The order becomes 1 2 3
*/
stack. push(result);
}
/**
* Current recursion, every time the bottom element is found at the end of the stack
* @param stack
* @return
*/
public static int func(Stack<Integer> stack)
{
//If cur is the bottom element of the stack, then the stack will be empty after the current pop
//directly return cur
int cur = stack. pop();
if (stack. isEmpty()) {
return cur;
}
else {
//Stack bottom element
int last = func(stack);
//Put the penultimate one to the bottom of the stack
stack.push(cur);
return last;
}
}
public static void main(String[] args) {
Stack<Integer> test = new Stack<Integer>();
test. push(1);
test. push(2);
test. push(3);
test. push(4);
test. push(5);
System.out.println("The order before reversal is: 5 4 3 2 1");
reverse(test);
System.out.print("The reverse order is: ");
while (!test.isEmpty()) {
System.out.print(test.pop());
System.out.print(" ");
}
}
}
This question is difficult, and it is difficult to use other structures to assist. You can only toss by yourself in the stack. Since it is in reverse order, the order of placement must be reversed. The characteristic of the stack is first-in-last-out, which makes it complicated. Let’s look at the whole process below:
