java递归和算法
package class02;import org.junit.Test;import java.util.*;//咱今天继续算法学习
public class Study230612 {//问题1:给你一个字符串s,找出其中最长回文子序列，并返回该序列的长度。//子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。public int question1(String s) {//动态规划---定义:dp[i][j]表示字符串s的下标范围 [i,j]内的最长回文子序列的长度。//思考从[i,j]内的回文串是怎么计算的?//如果s[i]==s[j],可以得知dp[i][j]内的回文字串==dp[i+1][j-1]内的回文字串+2//如果s[i]!=s[j],得知dp[i][j] = Max(dp[i][j-1],dp[i+1][j])内的最大值.注意===>核心//注意点,知道i,j就先知道i+1和j-1,所以i是从n递减,j递增,小技巧int n = s.length();int[][] dp = new int[n][n];for (int i = n - 1; i >= 0; i--) {dp[i][i] = 1;//从i到i默认是1,注意for (int j = i + 1; j < n; j++) {if (s.charAt(i) == s.charAt(j)) {dp[i][j] = dp[i + 1][j - 1] + 2;} else {dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);}}}return dp[0][n - 1];}//问题2:和为k的最短连续子数组,返回子数组的个数//暴力枚举所有的数组,统计和public int question2_1(int[] nums, int k) {int count = 0;for (int i = 0; i < nums.length; i++) {for (int j = i; j < nums.length; j++) {int sum = 0;for (int q = i; q <= j; q++) {sum += nums[q];}if (sum == k) count++;}}return count;}//问题2_2:在2的基础上我们可以优化吗?当然可以//在暴力枚举的第三次我们目的就是求和,完全可以在第二次遍历的时候顺便求和public int question2_2(int[] nums, int k) {int count = 0;for (int i = 0; i < nums.length; i++) { //(i....j)的子数组和int sum = 0;for (int j = i; j < nums.length; j++) {sum += nums[j];if (sum == k) count++;}}return count;}//问题2_3:在2的基础上我们还可以优化吗?//引申出一个定义前缀和:定义 preSum数组，preSum[i]表示第0项到第i项的和//那么问题就变成了:存在一对i,j(i pre(j)-k = pre(i)//那么(i,j)就是一个合适的子数组,将pre(i)放到hash表,统计出现的次数即可public int question2_3(int[] nums, int k) {int count = 0;int pre = 0; //前缀和HashMap map = new HashMap<>(); // map记录：以前缀和pre为键，出现次数为对应的值，记录pre出现的次数,map.put(0, 1); // 初始化for (int num : nums) {pre += num;if (map.containsKey(pre - k)) {count += map.get(pre - k); // 累计次数}map.put(pre, map.getOrDefault(pre, 0) + 1); // 计算新的和放入map}return count;}/**** //暴力递归思路:(从左到右,依次遍历)* //1.将问题转成较小的同类问题* //2.有明确的递归结束条件base case:* //3.有得到子问题的决策过程* //4.忽略记录问题的详细过程*///问题3:汉诺塔//对于n层汉诺塔,借助from to other三个柱子实现//第一步:现在from上面有n个盘子,将from上面的1~n-1个盘子转移到other//第二步:再将from上面编号为N的盘子放到to//第三步:再将other上面的盘子转到from//现在就变成了N-1个盘子从from到to,完成了将问题转成较小的同类问题//base case时N==1,完成了第二步//转移规则时第三步//如何将from->other和other->from转移,这是个实现过程,我们忽略//因此,主函数f(i,from,to,other) 对于第i个盘子,我们的操作过程public void question3(int i, String from, String other, String to) {if (i == 1) {System.out.println(i + "号盘子" + from + "--->" + to);} else {//将i-1个盘子从form->otherquestion3(i - 1, from, to, other);//将第i个盘子从from->toSystem.out.print(i + "号盘子" + from + "--->" + to + " ");//将原来的i-1个盘子从other->to 完成移动question3(i - 1, other, from, to);}}//问题4:打印一个字符串的所有子序列，包括空字符串//思考:对于s的某一个字符i,(0~i-1)中表示已经确定的字符串,index是待确定的,有两个选择,加入list/不加入list//path记录选择过的字符(0~s[i-1])public void question4(String s, int index, HashSet list, String path) {if (index == s.length()) { //base caselist.add(path);return;}question4(s, index + 1, list, path); //如果index不加入path = path + s.charAt(index); //如果index加入list.add(path);question4(s, index + 1, list, path);}//问题5:打印一个字符串全排列//思想:分解为先固定1，求剩下的n-1个数的全排列(for循环实现)，在固定2，固定3……依次类推//对于分别以1到n开头，可以通过交换的思想来实现，在递归前先将待排元素与当前排列的第一个元素进行交换，在递归结束时，交换回来，//思路:求abcd的全排列,先求a开头下,bcd的全排列,再求b开头下,acd的全排列,依次类推public void question5(char[] arr, int index, HashSet list) {if (index == arr.length) {list.add(Arrays.toString(arr));return;}//f(1, 2, ... n) = {第一位是 1, f(n-1)} + {第一位是 2, f(n-1)} +...+{第一位是 n, f(n-1)}for (int j = index; j < arr.length; j++) {swap(arr, index, j);question5(arr, index + 1, list);swap(arr, index, j);}}public void swap(char[] arr, int i, int j) {char temp = arr[i];arr[i] = arr[j];arr[j] = temp;}//问题6:两个人AB,从数组Arr的最左端或者最右端中选择一个数,直到数组结束,求总和最大的策略public int question6_f1(int[] arr, int L, int R) { //先手if (L == R) { //只有一个数的时候先手拿return arr[L];}return Math.max(arr[L] + question6_f2(arr, L + 1, R), arr[R] + question6_f2(arr, L, R - 1));}public int question6_f2(int[] arr, int L, int R) { //后手if (L == R) { //只有一个数的时候后手无return 0;}return Math.min(question6_f1(arr, L + 1, R), question6_f1(arr, L, R - 1));}//问题7:用递归逆序栈//思考:假设我们可以做到获取栈底元素打印并删除,那么原来1~n就变成了1~n-1, 将问题转成较小的同类问题//baseCase:栈空/*** * //暴力递归思路:(从左到右,依次遍历)* * //1.将问题转成较小的同类问题* * //2.有明确的递归结束条件base case:* * //3.有得到子问题的决策过程* * //4.忽略记录问题的详细过程*///f函数获取栈底元素打印并弹出public void f(Stack stack) {
// Stack temp = new Stack<>();
// while (!stack.empty()) {
// temp.push(stack.pop());
// }
// Integer pop = temp.pop();
// System.out.print(pop+" ");
// while (!temp.empty()) {
// stack.push(temp.pop());
// }int result = stack.pop();//取出并弹出当前栈的栈顶元素if (stack.empty()) {System.out.print(result + " ");//如果弹出一个元素后栈为空，说明栈中只有一个元素，就返回result} else {f(stack);stack.push(result);//前面递的过程一依次弹出栈顶元素，现在我们需要把除了原栈底元素压栈//注意压栈的顺序，在归的过程中，是后弹出的元素先压栈}}public void question7(Stack stack) {if (stack.empty()) {return;}f(stack);question7(stack);}//问题8:将A-Z分别对于1-26,现在给一个数字串,判断对应的字符个数//比如:111对应AAA,AK,KA三种情况//思考步骤:1.暴力递归,将问题转成较小的问题 2.baseCase:i到最后//对应数字串i位置(0,i-1) 表示已经转换好的i-1位置,目前针对i做处理//i==0 return 0;转换失败,返回0//i!=0 考虑i+1位置public int question8(char[] num, int index) {//错误分析
// if (index == num.length - 1) {
// return 1;
// } else {
// if (num[index] == 0) {
// return 0;
// } else {
// if (num[i + 1] < 7 && num[i] < 3) {
// return question8(num, i + 1) + question8(num, i + 2);
// } else {
// return question8(num, i + 1);
// }
// }
// }if (index == num.length) {return 1;}if (num[index] == 0) {return 0;}int res = question8(num, index + 1); //index+1肯定是符合的//判断截取两个的时候是否符合条件，如果也符合条件，就截取两个if (index < num.length - 1 && (num[index] == '1' || num[index] == '2' && num[index + 1] <= '6'))res += question8(num, index + 2);return res;}//问题9:在问题8的基础上记录对应的情况//二叉树思想,从nums种从左往后每次选择一个还是2个,在递归Set list = new HashSet<>();public void question9(char[] num, int index, String s, int cd) {if (index == num.length) {list.add(s); //一种情况的结束}
// if (num[index] == 0) {
// return;
// }
// if (index < num.length ) { //选择一个的情况
// s = s + " " + num[index];
// // list.add(s);
// question9(num, 1 + index, s);
// } if (index < num.length-1 ) { //选择一个的情况
// s = s + " " + num[index]+num[1+index];
// // list.add(s);
// question9(num, 2 + index, s);
// }if (index < num.length && cd == 1) {s = s + " " + num[index];question9(num, 1 + index, s, 1);question9(num, 1 + index, s, 2);}if (index < num.length - 1 && cd == 2) {if (num[index] == '1' || num[index] == '2' && num[index + 1] <= '6') {s = s + " " + num[index] + num[index + 1];question9(num, 2 + index, s, 1);question9(num, 2 + index, s, 2);}}// if (index < num.length - 1){
// list.add(String.valueOf(num[index]));
// question9(num, 1 + index, s + num[index]);
// }
// if (index < num.length - 1 && (num[index] == '1' || num[index] == '2' && num[index + 1] <= '6')) {
// list.add(String.valueOf(num[index]) + num[1 + index]);
// question9(num, index + 2, s + num[index] + num[1 + index]);
// }}@Testpublic void Test() {char[] array = "12345".toCharArray();int i3 = question8(array, 0);System.out.println(i3);question9(array, 0, "", 1);question9(array, 0, "", 2);System.out.println("list1" + list);Stack stack = new Stack<>();for (int i = 0; i < 5; i++) {stack.push(i + 1);}question7(stack);System.out.println("====");int[] ints = {1, 3, 5, 7, 9, 8, 6, 4, 2, 0};int i = question6_f1(ints, 0, ints.length - 1);int i2 = question6_f2(ints, 0, ints.length - 1);System.out.println(i + "==" + i2);//前缀和
// int i = question2_3(new int[]{1, 5, 9, 2, 4, 9}, 15);
// System.out.println(i);//前缀和int i1 = question2_3(new int[]{2, 3, -1, 1, 3}, 5);System.out.println(i1);question3(4, "A", "B", "C");int ques1 = question1("cbbbd");System.out.println(ques1);System.out.println("===");HashSet set = new HashSet<>();question4("ABC", 0, set, "");set.forEach(s -> {System.out.print(s + " ");});System.out.println("======");HashSet set1 = new HashSet<>();question5("ABC".toCharArray(), 0, set1);set1.forEach(s -> {System.out.println(s + " ");});}
}
package class02;
import org.junit.Test;
import java.util.*;
//咱今天继续算法学习
public class Study230612 {
//问题1:给你一个字符串s,找出其中最长回文子序列，并返回该序列的长度。
//子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
public int question1(String s) {
//动态规划---定义:dp[i][j]表示字符串s的下标范围 [i,j]内的最长回文子序列的长度。
//思考从[i,j]内的回文串是怎么计算的?
//如果s[i]==s[j],可以得知dp[i][j]内的回文字串==dp[i+1][j-1]内的回文字串+2
//如果s[i]!=s[j],得知dp[i][j] = Max(dp[i][j-1],dp[i+1][j])内的最大值.注意===>核心
//注意点,知道i,j就先知道i+1和j-1,所以i是从n递减,j递增,小技巧
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;//从i到i默认是1,注意
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
}
}
}
return dp[0][n - 1];
}
//问题2:和为k的最短连续子数组,返回子数组的个数
//暴力枚举所有的数组,统计和
public int question2_1(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
int sum = 0;
for (int q = i; q <= j; q++) {
sum += nums[q];
}
if (sum == k) count++;
}
}
return count;
}
//问题2_2:在2的基础上我们可以优化吗?当然可以
//在暴力枚举的第三次我们目的就是求和,完全可以在第二次遍历的时候顺便求和
public int question2_2(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) { //(i....j)的子数组和
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum == k) count++;
}
}
return count;
}
//问题2_3:在2的基础上我们还可以优化吗?
//引申出一个定义前缀和:定义 preSum数组，preSum[i]表示第0项到第i项的和
//那么问题就变成了:存在一对i,j(i
//那么(i,j)就是一个合适的子数组,将pre(i)放到hash表,统计出现的次数即可
public int question2_3(int[] nums, int k) {
int count = 0;
int pre = 0; //前缀和
HashMap
map.put(0, 1); // 初始化
for (int num : nums) {
pre += num;
if (map.containsKey(pre - k)) {
count += map.get(pre - k); // 累计次数
}
map.put(pre, map.getOrDefault(pre, 0) + 1); // 计算新的和放入map
}
return count;
}
/***
* //暴力递归思路:(从左到右,依次遍历)
* //1.将问题转成较小的同类问题
* //2.有明确的递归结束条件base case:
* //3.有得到子问题的决策过程
* //4.忽略记录问题的详细过程
*/
//问题3:汉诺塔
//对于n层汉诺塔,借助from to other三个柱子实现
//第一步:现在from上面有n个盘子,将from上面的1~n-1个盘子转移到other
//第二步:再将from上面编号为N的盘子放到to
//第三步:再将other上面的盘子转到from
//现在就变成了N-1个盘子从from到to,完成了将问题转成较小的同类问题
//base case时N==1,完成了第二步
//转移规则时第三步
//如何将from->other和other->from转移,这是个实现过程,我们忽略
//因此,主函数f(i,from,to,other) 对于第i个盘子,我们的操作过程
public void question3(int i, String from, String other, String to) {
if (i == 1) {
System.out.println(i + "号盘子" + from + "--->" + to);
} else {
//将i-1个盘子从form->other
question3(i - 1, from, to, other);
//将第i个盘子从from->to
System.out.print(i + "号盘子" + from + "--->" + to + " ");
//将原来的i-1个盘子从other->to 完成移动
question3(i - 1, other, from, to);
}
}
//问题4:打印一个字符串的所有子序列，包括空字符串
//思考:对于s的某一个字符i,(0~i-1)中表示已经确定的字符串,index是待确定的,有两个选择,加入list/不加入list
//path记录选择过的字符(0~s[i-1])
public void question4(String s, int index, HashSet
if (index == s.length()) { //base case
list.add(path);
return;
}
question4(s, index + 1, list, path); //如果index不加入
path = path + s.charAt(index); //如果index加入
list.add(path);
question4(s, index + 1, list, path);
}
//问题5:打印一个字符串全排列
//思想:分解为先固定1，求剩下的n-1个数的全排列(for循环实现)，在固定2，固定3……依次类推
//对于分别以1到n开头，可以通过交换的思想来实现，在递归前先将待排元素与当前排列的第一个元素进行交换，在递归结束时，交换回来，
//思路:求abcd的全排列,先求a开头下,bcd的全排列,再求b开头下,acd的全排列,依次类推
public void question5(char[] arr, int index, HashSet
if (index == arr.length) {
list.add(Arrays.toString(arr));
return;
}
//f(1, 2, ... n) = {第一位是 1, f(n-1)} + {第一位是 2, f(n-1)} +...+{第一位是 n, f(n-1)}
for (int j = index; j < arr.length; j++) {
swap(arr, index, j);
question5(arr, index + 1, list);
swap(arr, index, j);
}
}
public void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//问题6:两个人AB,从数组Arr的最左端或者最右端中选择一个数,直到数组结束,求总和最大的策略
public int question6_f1(int[] arr, int L, int R) { //先手
if (L == R) { //只有一个数的时候先手拿
return arr[L];
}
return Math.max(arr[L] + question6_f2(arr, L + 1, R), arr[R] + question6_f2(arr, L, R - 1));
}
public int question6_f2(int[] arr, int L, int R) { //后手
if (L == R) { //只有一个数的时候后手无
return 0;
}
return Math.min(question6_f1(arr, L + 1, R), question6_f1(arr, L, R - 1));
}
//问题7:用递归逆序栈
//思考:假设我们可以做到获取栈底元素打印并删除,那么原来1~n就变成了1~n-1, 将问题转成较小的同类问题
//baseCase:栈空
/**
* * //暴力递归思路:(从左到右,依次遍历)
* * //1.将问题转成较小的同类问题
* * //2.有明确的递归结束条件base case:
* * //3.有得到子问题的决策过程
* * //4.忽略记录问题的详细过程
*/
//f函数获取栈底元素打印并弹出
public void f(Stack
// Stack
// while (!stack.empty()) {
// temp.push(stack.pop());
// }
// Integer pop = temp.pop();
// System.out.print(pop+" ");
// while (!temp.empty()) {
// stack.push(temp.pop());
// }
int result = stack.pop();//取出并弹出当前栈的栈顶元素
if (stack.empty()) {
System.out.print(result + " ");//如果弹出一个元素后栈为空，说明栈中只有一个元素，就返回result
} else {
f(stack);
stack.push(result);//前面递的过程一依次弹出栈顶元素，现在我们需要把除了原栈底元素压栈
//注意压栈的顺序，在归的过程中，是后弹出的元素先压栈
}
}
public void question7(Stack
if (stack.empty()) {
return;
}
f(stack);
question7(stack);
}
//问题8:将A-Z分别对于1-26,现在给一个数字串,判断对应的字符个数
//比如:111对应AAA,AK,KA三种情况
//思考步骤:1.暴力递归,将问题转成较小的问题 2.baseCase:i到最后
//对应数字串i位置(0,i-1) 表示已经转换好的i-1位置,目前针对i做处理
//i==0 return 0;转换失败,返回0
//i!=0 考虑i+1位置
public int question8(char[] num, int index) {
//错误分析
// if (index == num.length - 1) {
// return 1;
// } else {
// if (num[index] == 0) {
// return 0;
// } else {
// if (num[i + 1] < 7 && num[i] < 3) {
// return question8(num, i + 1) + question8(num, i + 2);
// } else {
// return question8(num, i + 1);
// }
// }
// }
if (index == num.length) {
return 1;
}
if (num[index] == 0) {
return 0;
}
int res = question8(num, index + 1); //index+1肯定是符合的
//判断截取两个的时候是否符合条件，如果也符合条件，就截取两个
if (index < num.length - 1 && (num[index] == '1' || num[index] == '2' && num[index + 1] <= '6'))
res += question8(num, index + 2);
return res;
}
//问题9:在问题8的基础上记录对应的情况
//二叉树思想,从nums种从左往后每次选择一个还是2个,在递归
Set
public void question9(char[] num, int index, String s, int cd) {
if (index == num.length) {
list.add(s); //一种情况的结束
}
// if (num[index] == 0) {
// return;
// }
// if (index < num.length ) { //选择一个的情况
// s = s + " " + num[index];
// // list.add(s);
// question9(num, 1 + index, s);
// } if (index < num.length-1 ) { //选择一个的情况
// s = s + " " + num[index]+num[1+index];
// // list.add(s);
// question9(num, 2 + index, s);
// }
if (index < num.length && cd == 1) {
s = s + " " + num[index];
question9(num, 1 + index, s, 1);
question9(num, 1 + index, s, 2);
}
if (index < num.length - 1 && cd == 2) {
if (num[index] == '1' || num[index] == '2' && num[index + 1] <= '6') {
s = s + " " + num[index] + num[index + 1];
question9(num, 2 + index, s, 1);
question9(num, 2 + index, s, 2);
}
}
// if (index < num.length - 1){
// list.add(String.valueOf(num[index]));
// question9(num, 1 + index, s + num[index]);
// }
// if (index < num.length - 1 && (num[index] == '1' || num[index] == '2' && num[index + 1] <= '6')) {
// list.add(String.valueOf(num[index]) + num[1 + index]);
// question9(num, index + 2, s + num[index] + num[1 + index]);
// }
}
@Test
public void Test() {
char[] array = "12345".toCharArray();
int i3 = question8(array, 0);
System.out.println(i3);
question9(array, 0, "", 1);
question9(array, 0, "", 2);
System.out.println("list1" + list);
Stack
for (int i = 0; i < 5; i++) {
stack.push(i + 1);
}
question7(stack);
System.out.println("====");
int[] ints = {1, 3, 5, 7, 9, 8, 6, 4, 2, 0};
int i = question6_f1(ints, 0, ints.length - 1);
int i2 = question6_f2(ints, 0, ints.length - 1);
System.out.println(i + "==" + i2);
//前缀和
// int i = question2_3(new int[]{1, 5, 9, 2, 4, 9}, 15);
// System.out.println(i);
//前缀和
int i1 = question2_3(new int[]{2, 3, -1, 1, 3}, 5);
System.out.println(i1);
question3(4, "A", "B", "C");
int ques1 = question1("cbbbd");
System.out.println(ques1);
System.out.println("===");
HashSet
question4("ABC", 0, set, "");
set.forEach(s -> {
System.out.print(s + " ");
});
System.out.println("======");
HashSet
question5("ABC".toCharArray(), 0, set1);
set1.forEach(s -> {
System.out.println(s + " ");
});
}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！