暴力递归

题

汉诺塔问题

public static void hanoi(int i){
    process(i,"左","右","中");
}
public static void process(int i, String from,String to,String other){
    if (i == 1){
        System.out.println("1  "+from +"->"+to);
    }
    else {
        process(i - 1,from,other,to);
        System.out.println(i+from +"->"+to);
        process(i-1,other,to,from);
    }
}

全部子序列

/**
 * @Author: 郜宇博
 * @Date: 2021/11/9 14:04
 */
public class PrintString {
    public static void main(String[] args) {
        printAllSubsquence("abc");
    }
    public static void printAllSubsquence(String str) {
        char[] chs = str.toCharArray();
        process(chs, 0);
    }

    /**
     * 对于每一个i步，都存在走和不走的选择
     */
   public static void process(char[] chars,int i){
        if (i == chars.length){
            System.out.println(String.valueOf(chars));
        }
        else {
            //走字符i
            process(chars,i+1);
            char temp = chars[i];
            chars[i] = 0;
            //不走字符i
            process(chars,i+1);
            chars[i] = temp;
        }
   }


}

全排列

public static ArrayList allPermutations(String str){
    ArrayList<String> strings = new ArrayList<>();
    process(str.toCharArray(),0,strings);
    return strings;
}
public static void process(char[] chars,int i, ArrayList<String> res){
    //base
    if (i == chars.length){
        res.add(String.valueOf(chars));
    }
    //对于[0- i-1]的char数组，已经是选择过得了，后面的i-end随意选择一个进行全排列
    else {
        boolean[] visit = new boolean[26];
        for (int j = i ; j < chars.length; j++){
            if ( ! visit[chars[j]-'a']){
                visit[chars[j]-'a'] = true;
                swap(chars,i,j);
                process(chars,i+1,res);
                swap(chars,i,j);
            }

        }
    }
}
public static void swap(char[] chars,int i, int j){
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;

}

拿牌问题

给定一个整型数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸 牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A 和玩家B都绝顶聪明。请返回最后获胜者的分数。

/**
 * @Author: 郜宇博
 * @Date: 2021/11/9 14:54
 */
//先手拿牌
public static int firstTake(int []nums,int left,int right){
    //只有一个牌，先手拿到了
    if (left == right){
        return nums[left];
    }
    //拿左边 =  左边值+ 后手拿牌
    //右边=
    //然后选择一个最大的
    int valueTakeLeft = nums[left] + lastTake(nums,left+1,right);
    int valueTakeRight = nums[right] + lastTake(nums,left,right-1);
    return Math.max(valueTakeLeft,valueTakeRight);
}
//后手拿牌
public static int lastTake(int []nums,int left,int right){
    if (left == right){
        return 0;
    }
    //此时牌少一个
    int valueTakeLeft = firstTake(nums,left+1,right);
    int valueTakeRight = firstTake(nums,left,right-1);
    //先手的人知道我有这两个选择了，因此先手人的选择是让我选这两个里最小
    return Math.min(valueTakeLeft,valueTakeRight);

}
public static int winner(int []nums){
    if (nums == null || nums.length == 0){
        return 0;
    }
    int AfirstValue = firstTake(nums,0,nums.length-1);
    int BlastValue = lastTake(nums,0,nums.length-1);
    return Math.max(AfirstValue,BlastValue);
}

逆序栈元素，不用额外空间

/**
 * @Author: 郜宇博
 * @Date: 2021/11/9 15:31
 */
public class ReverseStackNoOtherSpace {
    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();
        s.push(1);
        s.push(2);
        reverseStack(s);
        for (Integer num: s){
            System.out.print(num);
        }
    }
    public static int popBottom(Stack<Integer> stack){
        //保留栈顶元素值
        int res = stack.pop();
        //不为空
        if (!stack.isEmpty()){
            //一直尝试得到last
            int last = popBottom(stack);
            //得到last后,将保留的元素压入栈中
            stack.push(res);
            return last;
        }
        else {
            return res;
        }
    }
    public static void reverseStack(Stack<Integer> stack){
        int bottom = popBottom(stack);
        if (!stack.isEmpty()){
            reverseStack(stack);
        }
        stack.push(bottom);
    }
}

字母转化

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

/**
 * @Author: 郜宇博
 * @Date: 2021/11/9 16:25
 */
public class ToLetterCounts {
    public static void main(String[] args) {

        System.out.println(convertLetter("12131"));
    }

    /**
     * 从左往右尝试
     */
    public static int convertLetter(String str){
        if (str == null || str.length() == 0) {
            return 0;
        }
        int process = process(str.toCharArray(), 0);
        return process;
    }
    /**
     * 获取i及其后面字符的转化可能数
     */
    public static int process(char[] chars,int i){
        if (i == chars.length){
            return 1;
        }
        if (chars[i] == '0'){
            return 0;
        }
        if (chars[i] == '1'){
            //获取i+1及其后的可能数
            int res = process(chars,i+1);
            //1和任何个位数都可以组成一个字母
            if (i+1 < chars.length){
                //获取i+2及其后的可能数
                res += process(chars,i+2);
            }
            return res;
        }
        if (chars[i] == '2'){
            int res = process(chars,i+1);
            //小于26的数才能转字母
            if (i+1 < chars.length && chars[i+1] <='6' && chars[i+1]>='0'){
                res += process(chars,i+2);
            }
            return res;
        }
        //3开始
        else {
            //获取之后的
            return process(chars,i+1);
        }
    }
}

背包问题

给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值。

给定一个正数bag，表示一个载重bag的袋子，你装的物 品不能超过这个重量。返回你能装下最多的价值是多少？

/**
 * @Author: 郜宇博
 * @Date: 2021/11/9 16:56
 */
public class MaxValueBag {
    public static void main(String[] args) {
        int[] weights = { 3, 2, 4, 7 };
        int[] values = { 5, 6, 3, 19 };
        int bag = 11;
        System.out.println(bagProblem(weights, values, bag));
    }
    public static int process(int[] weight,int []value,int i,int bag,int selectWeight){
        if (i == weight.length){
            return 0;
        }
        if (selectWeight > bag){
            return 0;
        }
        int select = process(weight,value,i+1,bag,selectWeight+weight[i]) + value[i];
        int unSelect = process(weight,value,i+1,bag,selectWeight);
        return Math.max(select,unSelect);
    }
    public static int bagProblem(int [] weight,int[] value,int bag){
        int process = process(weight, value, 0, bag, 0);
        return process;
    }
}

n皇后问题

/**
 * @Author: 郜宇博
 * @Date: 2021/11/9 17:12
 */
public class Queen {
    public static void main(String[] args) {
        long n1 = System.currentTimeMillis();
        System.out.println(queen(13));
        System.out.println(System.currentTimeMillis()-n1);
        long n2 = System.currentTimeMillis();
        System.out.println(queen1(13));
        System.out.println(System.currentTimeMillis()-n2);
    }

    public static int queen(int n){
        int[] record = new int[n];
        return process(record,0,n);

    }
    /**
     * 得出i及其以后的行的可能数
     */
    public static int process(int[] record,int i, int n){
        int res = 0;
        //base case
        if (i == n){
            return 1;
        }
        else {
            //每一列查看
            for (int j = 0; j < n; j++){
                if (isValid(record,i,j)){
                    record[i] = j;
                    res += process(record, i+1,n);
                }
            }
        }
        return res;
    }

    public static int queen1(int n){
        if (n < 1 || n > 32){
            return 0;
        }
        int limit = n == 32? -1:(1 << n)-1;
        return process1(limit,0,0,0);
    }
    /**
     * 不再使用record进行记录，而是使用二进制限制
     * 有三个限制：列限制，左斜线限制，右斜线限制，全部异或就是总限制
     * 只需要在下一行尝试的时候在非限制的地方尝试就可以了；
     */
    public static int process1(int limit,int colLim,int leftSlash,int rightSlash){
        //base case,如果所有列都放满了
        if (colLim == limit){
            return 1;
        }
        //总共可放的位置
        int pos = 0;
        //最右边可放的位置,一个尝试
        int mostRightPos = 0;
        int res = 0;
        pos = limit & (~ ( colLim | leftSlash | rightSlash));
        while (pos!= 0){
            mostRightPos = pos & (~pos + 1);
            pos = pos - mostRightPos;
                    //列限制 = 之前的列限制 | 选择的位置
            res += process1(limit,colLim|mostRightPos,
                    //固定：左限制 = 之前的左限制 | 选择的位置 ，在左移一位
                    (leftSlash|mostRightPos) <<1,
                    //固定：右限制 = 之前的右限制 | 选择的位置 ，在右移一位，高位补齐0
                    (rightSlash | mostRightPos) >>>1 );
        }
        return res;
    }

    public static boolean isValid(int[] record,int i, int j){
        for (int k = 0; k < i; k++){
            if (record[k] == j || Math.abs(record[k]-j) == Math.abs(i-k)){
                return false;
            }
        }
        return true;
    }
}