数据结构与算法——暴力递归

暴力递归就是尝试

1, 把问题转化为规模缩小了的同类问题的子问题

2, 有明确的不需要继续进行递归的条件(base case)

3, 有当得到了子问题的结果之后的决策过程

4, 不记录每一个子问题的解

一定要学会怎么去尝试，因为这是动态规划的基础，这一内容我们将在提升班讲述

汉诺塔问题

打印n层汉诺塔从最左边移动到最右边的全部过程

public static void hanoi(int n) {
        if (n > 0) {
            func(n, "左", "右", "中");
        }
    }

    // 1~i 圆盘 目标是from -> to， other是另外一个
    public static void func(int N, String from, String to, String other) {
        if (N == 1) { // base
            System.out.println("Move 1 from " + from + " to " + to);
        } else {
            func(N - 1, from, other, to);
            System.out.println("Move " + N + " from " + from + " to " + to);
            func(N - 1, other, to, from);
        }
    }

打印一个字符串的全部子序列，包括空字符串

public static List<String> getAllSubs(String s){
        char[] str = s.toCharArray();
        String path = "";
        List<String> ans = new ArrayList<>();
        process(str, 0, ans, path);
        return ans;
    }
    
    public static void process(char[] str, int index, 
            List<String> ans, String path) {
        if(index == str.length) {
            ans.add(path);
            return;
        }
        String noPath = path;
        process(str, index+1,ans, noPath);
        String yesPath = path + String.valueOf(str[index]);
        process(str, index+1,ans, yesPath);
    }

省空间方法用str

public static void printAllSubsquence(String str) {
        char[] chs = str.toCharArray();
        process(chs, 0);
    }

    // 当前来到i位置，要和不要，走两条路
    // 之前的选择，所形成的结果，是str
    public static void process(char[] str, int i) {
        if (i == str.length) {
            System.out.println(String.valueOf(str));
            return;
        }
        process(str, i + 1); // 要当前字符的路
        char tmp = str[i];
        str[i] = 0;
        process(str, i + 1); // 不要当前字符的路
        str[i] = tmp;
    }

打印一个字符串的全部排列

打印一个字符串的全部排列，要求不要出现重复的排列

public static ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();
        if (str == null || str.length() == 0) {
            return res;
        }
        char[] chs = str.toCharArray();
        process(chs, 0, res);
        return res;
    }

    // str[i..]范围上，所有的字符，都可以在i位置上，后续都去尝试
    // str[0..i-1]范围上，是之前做的选择
    // 请把所有的字符串形成的全排列，加入到res里去
    public static void process(char[] str, int i, ArrayList<String> res) {
        if (i == str.length) {
            res.add(String.valueOf(str));
        }
        boolean[] visit = new boolean[26]; // visit[0 1 .. 25]
        for (int j = i; j < str.length; j++) {
            if (!visit[str[j] - 'a']) {
                visit[str[j] - 'a'] = true;  //去重
                swap(str, i, j);
                process(str, i + 1, res);
                swap(str, 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 List<String> getAllC(String s) {
        List<String> ans = new ArrayList<>();
        ArrayList<Character> set = new ArrayList<>();
        for (char cha : s.toCharArray()) {
            set.add(cha);
        }
        process(set, "", ans);
        return ans;
    }

    public static void process(ArrayList<Character> list, String path, List<String> ans) {
        if (list.isEmpty()) {
            ans.add(path);
            return;
        }
        HashSet<Character> picks = new HashSet<>();
        for (int index = 0; index < list.size(); index++) {
            if (!picks.contains(list.get(index))) {
                picks.add(list.get(index));
                String pick = path + list.get(index);
                ArrayList<Character> next = new ArrayList<>(list);
                next.remove(index);
                process(next, pick, ans);
            }
        }
    }

给你一个栈，请你逆序这个栈，

不能申请额外的数据结构，只能使用递归函数。 如何实现？

import java.util.Stack;

public class ReverseStackUsingRecursive {

    public static void reverse(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        int i = f(stack);
        reverse(stack);
        stack.push(i);
    }

    public static int f(Stack<Integer> stack) {
        int result = stack.pop();
        if (stack.isEmpty()) {
            return result;
        } else {
            int last = f(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和A对应、2和B对应、3和C对应...

那么一个数字字符串比如"111",就可以转化为"AAA"、"KA”和"AK”。 给定一个只有数字字符组成的字符串str，返回有多少种转化结果。

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

    // i之前的位置，如何转化已经做过决定了, 不用再关心
    // 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]字符不是‘0’
        if (str[i] == '1') {
            int res = process(str, i + 1); // i自己作为单独的部分，后续有多少种方法
            if (i + 1 < str.length) {
                res += process(str, i + 2); // (i和i+1)作为单独的部分，后续有多少种方法
            }
            return res;
        }
        if (str[i] == '2') {
            int res = process(str, i + 1); // i自己作为单独的部分，后续有多少种方法
            // (i和i+1)作为单独的部分并且没有超过26，后续有多少种方法
            if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
                res += process(str, i + 2); // (i和i+1)作为单独的部分，后续有多少种方法
            }
            return res;
        }
        // str[i] == '3' ~ '9'
        return process(str, i + 1);
    }

    public static int dpWays(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            if (str[i] == '0') {
                dp[i] = 0;
            } else if (str[i] == '1') {
                dp[i] = dp[i + 1];
                if (i + 1 < N) {
                    dp[i] += dp[i + 2];
                }
            } else if (str[i] == '2') {
                dp[i] = dp[i + 1];
                if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {
                    dp[i] += dp[i + 2];
                }
            } else {
                dp[i] = dp[i + 1];
            }
        }
        return dp[0];
    }

给定两个长度都为N的数组

weights和values, weights [i]和values [ i]分别代表 i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物 品不能超过这个重量。返回你能装下最多的价值是多少？

public static int getMaxValue(int[] w, int[] v, int bag) {
        return process(w, v, 0, 0, bag);
    }

    // index... 最大价值
    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);

    }

    public static int maxValue(int[] w, int[] v, int bag) {
        return process(w, v, 0, bag);
    }

    // 只剩下rest的空间了，
    // index...货物自由选择，但是不要超过rest的空间
    // 返回能够获得的最大价值
    public static int process(int[] w, int[] v, int index, int rest) {
        if (rest <= 0) { // base case 1
            return 0;
        }
        // rest >=0
        if (index == w.length) { // base case 2
            return 0;
        }
        // 有货也有空间
        int p1 = process(w, v, index + 1, rest);
        int p2 = Integer.MIN_VALUE;
        if (rest >= w[index]) {
            p2 = v[index] + process(w, v, index + 1, rest - w[index]);
        }
        return Math.max(p1, p2);
    }

    public static int dpWay(int[] w, int[] v, int bag) {
        int N = w.length;
        int[][] dp = new int[N + 1][bag + 1];
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 1; rest <= bag; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest >= w[index]) {
                    dp[index][rest] = Math.max(dp[index][rest], v[index] + dp[index + 1][rest - w[index]]);
                }
            }
        }
        return dp[0][bag];
    }

给定一个整型数组arr,代表数值不同的纸牌排成一条线。

玩家A和玩家B依次拿走每张纸 牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A 和玩家B都绝顶聪明。请返回最后获胜者的分数。

【举例】arr=［1,2, 100, 4］。开始时，玩家A只能拿走1或4。如果开始时玩家A拿走1，则排列变为［2,100,4］，接下来 玩家B可以拿走2或4,然后继续轮到玩家A...

如果开始时玩家A拿走4,则排列变为［1,2,100］，接下来玩家B可以拿走1或100,然后继 续轮到玩家A...

玩家A作为绝顶聪明的人不会先拿4,因为拿4之后，玩家B将拿走100。所以玩家A会先拿1， 让排列变为［2,100,4］,接下来玩家B不管怎么选，100都会被玩家A拿走。玩家A会获胜， 分数为101。所以返回101。arr=［1, 100, 2］。

开始时，玩家A不管拿1还是2,玩家B作为绝顶聪明的人，都会把100拿走。玩家B会获胜， 分数为100。所以返回100。

public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
    }

    public static int f(int[] arr, int i, int j) {
        if (i == j) {
            return arr[i];
        }
        return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
    }

    public static int s(int[] arr, int i, int j) {
        if (i == j) {
            return 0;
        }
        return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
    }

    public static int win2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[][] f = new int[arr.length][arr.length];
        int[][] s = new int[arr.length][arr.length];
        for (int j = 0; j < arr.length; j++) {
            f[j][j] = arr[j];
            for (int i = j - 1; i >= 0; i--) {
                f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);
                s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);
            }
        }
        return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
    }

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;
        }
        int[] record = new int[n];// record[0..i-1]表示之前的行，放了的皇后位置
        return process1(0, record, n);
    }
    // 目前来到了第i行 
    public static int process1(int i, int[] record, int n) {// n代表整体一共有多少行  
        if (i == n) { //终止行
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) {// 当前i行的皇后，放在j列
            if (isValid(record, i, j)) {  //判断是否有效
                record[i] = j;
                res += process1(i + 1, record, n);
            }
        }
        return res;  // 返回值是，摆完所有的皇后，合理的摆法有多少种
    }


    public static boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {  //之前的某个k行的皇后
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }

位运算方法

public static int num2(int n) {
        if (n < 1 || n > 32) {
            return 0;
        }
        int upperLim = n == 32 ? -1 : (1 << n) - 1;
        return process2(upperLim, 0, 0, 0);
    }

    public static int process2(int upperLim, int colLim, int leftDiaLim,
            int rightDiaLim) {
        if (colLim == upperLim) {
            return 1;
        }
        int pos = 0;
        int mostRightOne = 0;
        // 所有候选皇后的位置，都在pos上
        pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
        int res = 0;
        while (pos != 0) {
            mostRightOne = pos & (~pos + 1);
            pos = pos - mostRightOne;
            res += process2(upperLim, colLim | mostRightOne,
                    (leftDiaLim | mostRightOne) << 1,
                    (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }