暴力递归
暴力递归就是尝试
1,把问题转化为规模缩小了的同类问题的子问题
2,有明确的不需要继续进行递归的条件(basecase)
3,有当得到了子问题的结果之后的决策过程
4,不记录每一个子问题的解
●打印n层汉诺塔从最左边移动到最右边的全部过程
1---N-1 左--》右
N-- 左---》右
1-----N-1 中---》右
解题思路:from:圆盘所在位置;to:圆盘要去的地方;help:用于辅助
- n-1 个圆盘从 from 到 help;
- 第 n 个圆盘从 from 到 to;
- 把那 n-1个圆盘从 help 移动到 to 上面来。
public class Code_02_Hannoi {
public static void process(int N,String from,String help,String to){
if(N == 1){
System.out.println("Move " + N + " from " + from + " to "+ to);
}else {
process(N-1,from,to,help);//第一步:把1到n-1从from移动到help组上去
System.out.println("Move " + N + " from " + from + " to "+ to);
process(N-1,help,from,to);//第三步:把1到n-1从help上移动到to上去
}
}
public static void main(String[] args) {
int N = 3;
process(N,"左边","中间","右边");
}
}
●打印一个字符串的全部子序列,包括空字符串
- 区分子串和子序列: 给定 “pwwkew”
- 子串是pww,wwk等很多个子串 是连在一起的
- 子序列是 pwk,pke等很多个子序列 ,但是子序列中的字符在字符串中不一定是连在一起的。
public class Code_03_PrintSubString {
public static void printSubStr(char[] chs,int i,String res){
if(i == chs.length){
System.out.println(res);
return;
}
printSubStr(chs,i + 1,res);//不需要当前的字符的
printSubStr(chs,i + 1,res + chs[i]);//需要当前的字符的
}
public static void main(String[] args) {
String s = "abc";
printSubStr(s.toCharArray(),0,"");
}
}
//输出
(包含一个空字符串)
c
b
bc
a
ac
ab
abc
●打印一个字符串的全部子序列,要求不要出现重复字面值的子序列
输出前,加入set去重
●打印一个字符串的全部排列
举个栗子:
字符不重复的情况下:
输入:abc
输出:abc acb bac bca cab cba
字符重复的情况下:
输入:acc
输出:acc acc cac cca cca cac
解题思路:把一个字符串看成由两部分组成:第一部分是它的第一个字符;第二部分是后面的所有字符。而我们求整个字符串的排列,可以看成两步。
求所有可能出现在第一个位置的字符,即把第一个字符和后面所有的字符交换。
固定第一个字符,求后面所有字符的排列。
这时候我们仍把后面的所有字符分成两个部分:后面字符的第一个字符,以及这个字符之后的所有字符。然后把第一个字符和它后面的所有字符交换。(重复1、2步骤)
printAllPermutations2 为分治限界方法,可以减少递归次数
public class Code_04_Print_All_Permutations {
public static void printAllPermutations1(String str) {
char[] chs = str.toCharArray();
process1(chs, 0);
}
public static void process1(char[] chs, int i) {//交换的是当前位置之后的元素
if (i == chs.length) {
System.out.println(String.valueOf(chs));
}
//如果i没有终止,i... 都可以来到位置
for (int j = i; j < chs.length; j++) {//这个的理解是难点
swap(chs, i, j);
process1(chs, i + 1);
swap(chs, i, j);
}
}
// 在选择位置时就利用set ,减少递归次数,时间换空间
public static void printAllPermutations2(String str) {
char[] chs = str.toCharArray();
process2(chs, 0);
}
public static void process2(char[] chs, int i) {
if (i == chs.length) {
System.out.println(String.valueOf(chs));
}
HashSet<Character> set = new HashSet<>();
for (int j = i; j < chs.length; j++) {
if (!set.contains(chs[j])) {
set.add(chs[j]);
swap(chs, i, j);
process2(chs, i + 1);
swap(chs, 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 void main(String[] args) {
String test1 = "abc";
printAllPermutations1(test1);
System.out.println("======");
printAllPermutations2(test1);
System.out.println("======");
String test2 = "acc";
printAllPermutations1(test2);
System.out.println("======");
printAllPermutations2(test1);
System.out.println("======");
}
}
[[1,2,3],
[4,5,6],
[7,8,9]
]
打印一个字符串的全部排列,要求不要出现重复的排列
-
举个栗子:
输入:acc
输出:acc cac cca
思路同上,加入了HashSet来去重。
public class PrintAllSort {
public static void printAllSort(String string){
if(string == null){
return;
}
char[] chars = string.toCharArray();
if(chars.length > 0){
func2(0, chars);
}
}
// 对i及i以后的字符进行全排序
public static void func2(int i, char[] chars){
if(i == chars.length){
System.out.println(String.valueOf(chars));
}
// 用于保证每次交换的字符不存在重复字符
HashSet<Character> set = new HashSet<>();
for(int j = i; j < chars.length; j++){
// 只有之前没有交换过这个字符才会交换
if(!set.contains(chars[j])) {
set.add(chars[j]);
swap(i, j, chars); // 第i个位置有i~n-1这些选择
func2(i + 1, chars); // 搞第i+1的位置
swap(i, j, chars);
}
}
}
public static void swap(int i, int j, char[] chars){
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
// 测试
public static void main(String[] args) {
printAllSort("acc");
}
}
给你一个栈,请你逆序这个栈,不能申请额外的数据结构,只能使用递归函数。如何实现?
实现得到栈中最后一个元素并返回的递归调用过程:
实现逆序当前栈的功能:
public class Code_06_ReverseStackUsingRecursive {
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
int i = getAndRemoveLastElement(stack);
reverse(stack);
stack.push(i);
}
public static int getAndRemoveLastElement(Stack<Integer> stack) {
int result = stack.pop();
if (stack.isEmpty()) {
return result;
} else {
int last = getAndRemoveLastElement(stack);
stack.push(result);
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);
reverse(test);
while (!test.isEmpty()) {
System.out.println(test.pop());
}
}
}
从左往右的尝试模型1
我当年面Facebook原题----左神
规定1和A对应、2和B对应、3和C对应...
那么一个数字字符串比如"111"就可以转化为:
'AAA"、 "KA"和"AK"
给定一个只有数字字符组成的字符串str,返回有多少种转化结果
注意:
10 这个用例,只有 J 一种转化结果
public static int number(String str) {
if (str == null II str.1ength() == 0) {
return 0;
}
return process(str .toCharArray(), 8);
}
// str[0...i-1]已经转化定了, 固定川
// i之z前的他置, 如何转化已经做过决定了,不用脚关心
// i...们名少种转化的结果.
public static int process(char[] str, int i) {
if (i == str.length) { // base case
return 1;
}
// i没有到终止位置
if (str[i] == '0') {
return 0;
}
// str[i]字符不足‘日’
if (str[i] == '1') {
int res = process(str, i + 1); //自己作为单独的部分。后续有名少种方法
if (i + 1<str.1ength) {
res += process(str, i + 2); //1 (i和i+1)作为单独的部分。后续有名少种方法
}
return res;
}
if (str[i] == '2') {
int res = process(str, i + 1); // ii已作为单独的部分。后续有多少神方法
// (i利1+1)作为单独的部分并扎没有超:26.行使有名少种万法
// (1和i+1)作为单独的部分非且没有超上26.看续有名少种为法
if (i + 1< str.1ength && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
res += process(str, i + 2); // (i和1+1)作:为单独的部分,i续有名少种方法
}
return res;
}
// str[i] == '3’~ '9' 3_ 无法转换
return process(str, i + 1);
}
从左往右的尝试模型2
给定两个长度都为N的数组weights和values,
weights[i]和values[]分别代表i号物品的重量和价值。
给定一个正数bag,表示--个载重bag的袋子,
你装的物品不能超过这个重量。
返回你能装下最多的价值是多少?
递归:
public static int getMaxValue(int[] W, int[] v, int bag) {
return process(W, V, 0, 0, bag);
}
//不变: w[] v[] bag
// index... 最大价值
// 0..index-1上做了货物的选择,使得你L上经达到的中量是名少alreadyw
//如果返川-1.认为没有万案
//如果不返叫-1. 认为眍间的值是真实价值
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);
int p2 = -1;
if (p2next != -1) {
p2 = v[index] + p2next;
}
return Math . max(p1, p2);
}
范围上尝试的模型
给定一个整型数组arr,代表数值不同的纸牌排成一条线,
玩家A和玩家B依次拿走每张纸牌,
规定玩家A先拿,玩家B后拿,
但是每个玩家每次只能拿走最左或最右的纸牌,
玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
public static int win1(int[] arr) {
if (arr == nu11|I arr.length == 0) {
return 0;
}
return Math . max(f(arr,0, arr.length - 1), s(arr, 0, arr .1ength - 1));
}
//先手
public static int f(int[] arr, int L, int R) {
if(L==R){
return arr[L];
}
return Math. max(
arr[L]+ s(arr, L + 1, R),arr[R] + s(arr, L, R - 1));
}
// 后手
public static int s(int[] arr, int i, int j) {
if (i=j) {
return 0;
}
return Math .min(f(arr, i + 1, j) //arr[i]
,f(arr, i, j - 1)); //arr[j]
}
N皇后
N皇后问题是指在N*N的棋盘.上要摆N个皇后,
要求任何两个皇后不同行、不同列,也不在同一 条斜线上
给定一个整数n,返回n皇后的摆法有多少种。
n=1,返回1
n=2或3,2皇后和3皇后问题无论怎么摆都不行,返回0
n=8,返回92
public static int num1(int n) {
if(n<1){
return 0;
}
// record[0] ? record[1] ? record[2]
int[] record = new int[n]; // record[i] -> i行的早,收在I
return process1(0, record, n);
}
//潜台训: record[0..i-1]的皇后。 任何两个皇后一定都不共行、不共列。
// 目前前来到了第i行
// record[0..i-1]表示之前的行, 放了皇后的位置
// n代表整体共有名少行
//返回值为。摆定所有的皇后。合理的摆法有多少种
public static int process1(int i, int[] record, int n) {
if(i==n){//终止行
return 1;
}
int res = 0;
for (int j = 0; j < n; j++) { //“前行在i行。类试i行断有的列
//当前行i行的皇后。放在j列。会不会和之前(0..i-1)的皇后 满足要求
//如果是。认为有效
//如果不是,认为无效
if (isValid(record, i, j)) {
record[i] = j;
res += process1(i + 1,record, n);
}
return res;
}
// record[0..i-1]需要看。 record[i...]不需要看
//返回i行皇后,放在了j列,是否有效
public static boolean isValid(int[] record, int i, int j) {
for(intk=e;k<i;k++){//之前的某个k行的里后
if (j == record[k] | Math. abs(record[k] - j) == Math. abs(i . k)) {
return false;
}
}
return true ;
}
位运算优化
//请不要超过32皇后问题
public static int num2(int n) {
if(n<1|n>32){
return 0;
}
//如果你是13皇后问题,limit最右13个1, 其他都是0
intlimit=n==_32?-1:(1<<n)-1;
return process2(limit, 0, 0, 0);
}
// limit 划定了问题的规模->固定
// colLim列的限制,1的位置不能放皇后,0的位置可以
// leftDiaLim 左斜线的限制,1的位置不能放皇后,0的位置可以
// rightDiaLim 右斜线的限制,1的位置不能放皇后,0的位置可以
public static int process2(
int limit,
int colLim,
int leftDialim,
int rightDiaLim) {
if (colLim == limit) { // base case
return 1;
}
//所有候选皇后的位置,都在pos上
//(colLim | leftDiaLim | rightDialim) 总限制
//~(colLim | leftDiaLim | rightDialim) 右侧是有效的每个1是可以尝试放皇后的位置
int pos = limit & ( ~(colLim | leftDiaLim | rightDialim) );
int mostRightOne = 0;
int res = 0;
while (pos != 0) {
//提取出最右侧的1
mostRightOne = pos & (~poS + 1);
pos = pos - mostRightOne ;
res += process2(limit,
// 新的列限制
colLim| mostRightOne,
// 左斜线限制
(leftDiaLim| mostRightOne) << 1,
// 右斜线限制
(rightDialim | mostRightOne) >>> 1);
}
return res ;
}