数据结构与算法学习笔记（基础班十一）---暴力递归

暴力递归就是尝试

  1. 把问题转化为规模缩小了的同类问题的子问题
  2. 有明确的不需要继续进行递归的条件(base case)
  3. 有当得到了子问题的结果之后的决策过程
  4. 不记录每一个子问题的解
  • 汉若塔问题,n层圆盘从左移到右打印移动过程。
// 2^n-1
public class HanNuoTa {
    public static void hanNuoTa(int n){
        if(n < 1){
            return;
        }
        process(n,"左","右","中");
    }

    // 把n层圆盘从from 移动到 to上去
    public static void process(int n,String from,String to,String other){
        if(n ==  1){
            // 如果只剩一层圆盘那么直接移动就行了
            System.out.println("Move 1 from"+from+"to"+to);
        }else{
            // 把n-1层圆盘从from移动到other上去，
            process(n-1,from,other,to);
            // 把第n层圆盘移动到to上去
            System.out.println("Move"+n+"from"+from+"to"+to);
            // 在从other上把n-1层圆盘移动到to上去
            process(n-1,other,to,from);
        }
    }
    public static void main(String[] args) {
        hanNuoTa(100);
    }
}
  • 给你一个栈请你逆序这个栈不能申请额外数据结构，只能用递归函数。
// 逆序栈，用递归
public class ReverseStack {
    public static void reverse(Stack<Integer> stack) {
        if(stack.isEmpty()){
            // 如果栈已经为空什么也不做
            return;
        }else{
            int cur = process(stack);
            reverse(stack);
            stack.push(cur);

        }

    }
    
    // 给定一个栈，返回栈底元素，且保持栈为去掉栈底元素后其他位置不变的栈
    // 如栈 1，2，3 则返回3，且栈变为1,2
    private static int process(Stack<Integer> stack){
        // 弹出栈顶元素
        Integer cur = stack.pop();
        if(stack.isEmpty()){
            // 弹出元素后如果此时栈为空，那么向上返回结果
            return cur;
        }else{
            // 如果栈不为空，继续执行子过程
            int res = process(stack);
            // 把当前元素压回栈中
            stack.push(cur);
            // 向上返回栈底元素
            return res;
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(3);
        stack.push(2);
        stack.push(1);
        System.out.println("调用前"+stack);
        reverse(stack);
        System.out.println("调用后"+stack);
    }
}
  • 打印一个字符串的全部子序列
public class StrSub {
    public static List<String> strSub(String str){
        if(str == null){
            return null;
        }
        List<String> res = new ArrayList<>();
        process(str.toCharArray(),0,"",res);
        return res;
    }

    // 打印一个字符串的全部子序列
    // 返回c[index]开始的全部子序列，index - 1以前的都已经生成好了
    // 0~index - 1形成的字符串
    private static void process(char[] c,int index,String path,List<String> res){
        if(index == c.length){
            // 当index == 终止位置时，说明path已经形成了一条完整的路径
            res.add(path);
            return;
        }
        // 不选当前的位置,path不变
        process(c,index + 1,path,res);
        // 选择当前的位置
        path = path + String.valueOf(c[index]);
        process(c,index + 1,path,res);
    }
    public static void main(String[] args) {
        System.out.println(strSub("aaa"));
    }
}
  • 打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
// 打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
public class StrSub02 {
    public static Set<String> strSub02(String str){
        if(str == null){
            return null;
        }
        Set<String> res = new HashSet<>();
        process(str.toCharArray(),0,"",res);
        return res;
    }

    // 打印一个字符串的全部子序列
    // 返回c[index]开始的全部子序列，index - 1以前的都已经生成好了
    // 0~index - 1形成的字符串
    private static void process(char[] c,int index,String path,Set<String> res){
        if(index == c.length){
            // 当index == 终止位置时，说明path已经形成了一条完整的路径
            res.add(path);
            return;
        }
        // 不选当前的位置,path不变
        process(c,index + 1,path,res);
        // 选择当前的位置
        path = path + String.valueOf(c[index]);
        process(c,index + 1,path,res);
    }

    public static void main(String[] args) {
        System.out.println(strSub02("aaa"));
    }
}
  • 全排列字符串
// 打印一个字符串的全部排列
public class AllArrangement {

    public static List<String> allArrangement(String str){
        if(str == null){
            return null;
        }
        List<String> res = new ArrayList<>();
        process(str.toCharArray(),0,res);
        return res;
    }

    // 从index开始的字符否有可能来到index位置 ,从0 - index-1 都应经做好决定
    private static void process(char[] c,int index,List<String> res){

        if(index == c.length){
            // 此时数组数组中已经是一组有效的排列,收集结果
            res.add(String.valueOf(c));
            return;
        }

        for(int i = index;i < c.length;i ++){
            // 交换
            swap(c,index,i);
            // indexd + 1位置继续排列组合
            process(c,index + 1,res);
            // 后续过程结束后要把元素还原
            swap(c,i,index);
        }
    }

    public static List<String> allArrangement2(String str){
        if(str == null){
            return null;
        }
        List<String> res = new ArrayList<>();
        process2(str.toCharArray(),0,res);
        return res;
    }

    // 不能重复的全排列
    private static void process2(char[] c,int index,List<String> res){

        if(index == c.length){
            // 此时数组数组中已经是一组有效的排列,收集结果
            res.add(String.valueOf(c));
            return;
        }
        // 默认都是false,判断后续字符在当前index位置是否已经放置过
        boolean[] b = new boolean[26];
        for(int i = index;i < c.length;i ++){
            if(!b[c[i] - 'a']){
                // 当前位置没有放过的元素才能放进来继续后续过程，此位置已经放过的字符不用再放
                // 交换
                swap(c,index,i);
                // indexd + 1位置继续排列组合
                process(c,index + 1,res);
                // 后续过程结束后要把元素还原
                swap(c,i,index);
                b[c[i] - 'a'] = true;
            }

        }
    }

    // 交换数组中两个元素
    private static void swap(char[] arr,int i,int j){
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        System.out.println(allArrangement2("abc"));
    }
}

从左往右的尝试模型

  • 规定1和A对应、2和B对应、3和C对应...那么一个数字字符串比如"111”就可以转化为:
    "AAA"、"KA"和"AK"给定一个只有数字字符组成的字符串str，返回有多少种转化结果。
/**
 * 规定1和A对应、2和B对应、3和C对应...那么一个数字字符串比如"111”就可以转化为:
 * "AAA"、"KA"和"AK"给定一个只有数字字符组成的字符串str，返回有多少种转化结果。
 */
public class NumberToString {

    public static int numberToString(String str){
        if(str == null){
            return 0;
        }
        return process(str.toCharArray(),0);

    }

    // 从index开始返回后面的转化可能数，index - 1以前的已经转化好了。
    private static int process(char[] c,int index){
        if(index == c.length){
            // index已经来到了结束位置,说明前面index - 1上的转换都是有效的,那么久收集到一种有效转化
            return 1;
        }

        if(c[index] == '0'){
            // 如果当前位置是'0'字符那么没有对应的大写字母和他对应，因此前面index - 1上的转换无效
            return 0;
        }

        // 由于只有26个大写字母，所以数字组合最多是两位数，且最大的两位数为26 其他数字都不符合要求
        int res = 0;
        // 如果当前位置是1
        if(c[index] == '1'){
            // 1.就以当前字符为转换字符，给我收集后续转换可能
            int p1 = process(c,index + 1);
            // 2.当前index字符和index + 1位置字符为转换字符，收集index + 2后续结果
            int p2 = 0;
            if(index + 1 < c.length){
                p2 = process(c,index + 2);
            }
            res = p1 + p2;

            return res;

        }

        if(c[index] == '2'){
            // 1.就以当前字符为转换字符，给我收集后续转换可能
            int p1 = process(c,index + 1);
            int p2 = 0;
            if(index + 1 < c.length && c[index + 1] >='0' && c[index + 1] <= '6'){
                p2 = process(c,index + 2);
            }
            res = p1 + p2;
            return res;
        }
        return process(c,index + 1);
        // return 0;
    }

    public static void main(String[] args) {
        System.out.println(numberToString("24112"));
    }
}
  • 背包问题：给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少?
public class Bag {
    // 返回最多装下物品的价值总价
    public static int bag(int[] weight,int[] values,int bag){
        return process(weight,values,0,bag);
    }

    // weight values 为固定不变参数
    // index 表示从weight[index...]开始的货物中给我选取使得价值最大，0~index-1上已经选择好了
    // rest表示此时还剩余的背包空间
    private static int process(int[] weight,int[] values,int index,int rest){
        if(rest <= 0){
            // 如果此时背包已经没有空间了，那么返回此时价值0(选不了货物价值自然是0)
            return 0;
        }
        if(index == weight.length){
            // 背包有空间但是已经没有货物了，返回价值0
            return 0;
        }

        // 背包既有空间，并且也有货物

        // 不选当前货物
        int value1 = process(weight, values, index + 1, rest);

        // 选择当前的货物
        int value2 = 0;
        if(rest - weight[index] >= 0){
            value2 = process(weight,values,index + 1,rest - weight[index]) + values[index];
        }
        int res = Math.max(value1,value2);
        return res;
    }
 // 动态规划
    public static int bag2(int[] weight,int[] values,int rest){
        if(weight.length <= 0 || values.length <=0 || rest <=0){
            return 0;
        }
        int N = weight.length;
        // 定义二维表
        int[][] dp = new int[N+1][rest+1];
        // 当rest==0时,第一列都等于0,初始化时数组中都是0，不用重新设置
        // 第N行全是0也不用设置
        // 普遍index位置都会依赖下一行，因此从下往上填表
        for(int i = N-1;i >= 0;i--){
            for (int j = 0; j <= rest; j++) {
                dp[i][j] = dp[i + 1][j];
                // 选择当前的货物
                int value2 = 0;
                if(j - weight[i] >= 0){
                    value2 = dp[i + 1][j - weight[i]] + values[i];
                }
                dp[i][j] = Math.max(dp[i][j],value2);
            }
        }
        return dp[0][rest];

    }

    public static void main(String[] args) {
        int[] weight = new int[]{2,3,4,6,3,80};
        int[] values = new int[]{2,5,46,7,9,80};
        System.out.println(bag(weight, values, 84));
    }
}

范围上尝试的模型

  • 给定一个整型数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
public class WinSum {
    public static int winSum(int[] arr){
        if(arr == null){
            return 0;
        }

        return Math.max(f(arr,0,arr.length-1),s(arr,0,arr.length-1));
    }


    // 在R - L上返回先手获得的最大分数
    private static int f(int[] arr,int L,int R){
        if(R == L){
            // 如果只剩下一张牌，且是先手，那么直接选这个牌就行了
            return arr[L];
        }

        // 如果先手选了左边,那么后手能选的最大分数加上先手选的
        int p1 = arr[L] + s(arr,L + 1,R);
        int p2 = arr[R] + s(arr,L,R - 1);

        // 取最大值
        return Math.max(p1,p2);
    }

    // 在L - R 后手取得的最大值(后手是被动的，永远都是先手留给他的最坏情况)

    private static int s(int[] arr,int L,int R){
        if(L == R){
            // 应为是后手所以当剩一张是，被先手选了所以后手没得选
            return 0;
        }

        // 因为先手已经选了，所有后手就在剩下的中先选
        int p1 = f(arr,L + 1,R);
        int p2 = f(arr,L,R -1);
        // 先后只会留给后手最差的选择
        return Math.min(p1,p2);
    }
 // 动态规划
    public static int winSum2(int[] arr){
        if(arr == null){
            return 0;
        }
        int N = arr.length;
        // L的范围 L可以从0到L，
        // R的范围R可以从0到R
        // 定义dp表,是一张正方形表
        int[][] f = new int[N][N];
        int[][] s = new int[N][N];
        // 由于在L - R 的范围上L都是小于R的所有表的左下部分都是不用填写的
        // f表当L == R是值都是 L
        for(int i = 0;i < N;i++){
            f[i][i] = arr[i];
        }
        // s表当L == R时值都是0，不用填写
        // 普遍位置
        for(int i = 1;i < N;i++){
            int L = 0;
            int R = i;
            while(L < N && R < N){
                f[L][R] = Math.max(arr[L] + s[L+1][R],arr[R] + s[L][R-1]);
                s[L][R] = Math.min(f[L+1][R],f[L][R-1]);
                L ++;
                R ++;
            }


        }
        return Math.max(f[0][N-1],s[0][N-1]);
    }
    public static void main(String[] args) {
        System.out.println(winSum(new int[]{3, 100, 8,70}));
    }
}
  • N皇后。N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列， 也不在同一条斜线上给定一个整数n，返回n皇后的摆法有多少种。�n=1，返回1，n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0，n=8，返回92。
// N皇后问题
public class NQueen {
   public static int nQueen(int n){
       if(n <= 0){
           return 0;
       }
       int[] record = new int[n];
        return process(0,record,n);
   }

   // index 当前来到index行准备摆放皇后。
    // record[i] 表示第i行第record[i]列是否已经摆好了皇后
    // n个皇后
   private static int process(int index,int[] record,int n){
       if(index == n){
           // 如果index == n说明已经放完了皇后,收集一种摆放方法
           return 1;
       }
       // 在index行中每列的位置都和前面已经摆好的位置的皇后做比较，若有违规则不再摆放
       // 没有违规则继续摆放
       int res = 0;
       for (int col = 0; col < n; col++) {
            if(verify(record,index,col)){
                // 如果不违规则继续index + 1行的摆放,且在record中摆放好当前位置
                record[index] = col;
                // index 这一行上有多少种摆法
                res += process(index + 1, record, n);
            }
       }
       return res;
   }
   // true 不违规，false 违规
    // i j 此时皇后摆放的位置
   private static boolean verify(int[] record,int i ,int j){
       for (int k = 0; k < i; k++) {
           // 比较前面i-1行
           if(record[k] == j || Math.abs(k - i) == Math.abs(record[k] - j)){
               //不用判断共行，只用判断共列和共斜线
               // (a,b)   (c,d) 是否共斜线
               // |(a - c)| == |(b - d)|
               return false;
           }
       }
       return true;
   }
    public static void main(String[] args) {
        System.out.println(nQueen(14));
    }
}
  • 位运算优化
 public static int nQueen2(int n){
       if(n <= 0){
           return 0;
       }
       int limit = n == 32 ? -1 : (1 << n) - 1 ;
       return process2(limit,0,0,0,n);
   }

   // limit固定规模,n皇后就是右边有n个1
   // leftLimit 左斜线限制
    // rightLimit 右斜线限制
    // colLimit 列限制,摆放了多少个皇后
   public static int process2(int limit,int colLimit,int leftLimit,int rightLimit,int n){
        if(colLimit == limit){
            // 已经摆满了皇后
            return 1;
        }
        // 此时在哪些位置可以摆放 colLimit | leftLimit | rightLimit o 的位置都可以放
       //                     01000000   00010000    00100000
       // 11111111 & ~(01110000)
       // 11111111 & 10001111
       // 0000010001111
       // pos 中1的位置都可以尝试
       int pos = limit & (~(colLimit | leftLimit | rightLimit));
        // 每个位置尝试
       int res = 0;
       while (pos != 0){
           // 提取最右边的1
           int mostRightOne = pos & (-pos);
           pos = pos ^ mostRightOne;
           res += process2(limit,(colLimit | mostRightOne),((leftLimit | mostRightOne) << 1),((rightLimit | mostRightOne) >> 1),n);
       }
       return res;
   }
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,992评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,212评论 3赞 388
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 159,535评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,197评论 1赞 287
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,310评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,383评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,409评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,191评论 0赞 269
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,621评论 1赞 306
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,910评论 2赞 328
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,084评论 1赞 342
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,763评论 4赞 337
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,403评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,083评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,318评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,946评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,967评论 2赞 351