java算法题之暴力递归

- 暴力递归
- - N皇后（位运算）
  - 递归实现字符串求值
  - 字符串的全排列
  - 纸牌累计分数
  - 岛数量问题
  - 人气值
  - - 错误代码
    - 平凡解限制
  - 返回字符串的所有子字符串（树形）
  - 数字转化成字母（树形）
  - 背包问题（树形）

暴力递归 N皇后（位运算）

class E {
    public static int num(int num) {
        if (num < 1 || num > 32) return 0;
        //limit用于限制在所有数据运算过程中保证除后num位的所有位数据均为零，来判断结束和标志结束
        int limit = num == 32 ? -1 : (1 << num) - 1;
        return process(limit, 0, 0, 0);
    }

    
    private static int process(int limit, int coLim, int leftLim, int rightLim) {
        if (limit == coLim) return 1;

        //(coLim | leftLim | rightLim)结果表示所有位上为1的位置均存在皇后，不能存放。
        //~后表示1的地方没有限制，可以存放皇后（但是，在32位的前32-num位上也为1，我们知道这是不合理的，因为不存在那么多的皇后）
        //limit&    表示将除num位的值变成0，这样就保证所有为1的元素均为空缺位置。
        int pos = limit & (~(coLim | leftLim | rightLim));
        int res = 0, mostRightOne;
        while (pos != 0) {//pos为0.说明不存在空缺位置
            mostRightOne = pos & (~pos + 1);//此时在后num位存在1，就将最右端的1取出。
            pos = pos - mostRightOne;//更新pos，将取出的1减掉，表明mostRightOne中1所对应的位存在了，不能放了。
            res += process(limit, coLim | mostRightOne  // 该mostRightOne位的皇后对于下一皇后纵向上的影响
                    , (leftLim | mostRightOne) << 1     // mostRightOne对于k=-1方向的影响
                    , (rightLim | mostRightOne) >> 1);  //mostRightOne对于k=1方向的影响
        }
        return res;
    }
}

递归实现字符串求值

public class Main {
	public static void main(String[] args) {
		int a = value("4-(1+2)*3+1");
		System.out.println(a);
	}

	private static int value(String string) {
		if (string == null || string.length() == 0) {
			return 0;
		}
		return value(string.toCharArray(), 0)[0];
	}

	private static int[] value(char[] str, int i) {
		linkedList list = new linkedList<>();
		int num = 0;
		int[] bra = null;
		while (i < str.length && str[i] != ')') {
			if (str[i] >= '0' && str[i] <= '9') {
				num = num * 10 + str[i++] - '0';
			} else if (str[i] != '(') {
				addNum(list, num);
				list.addLast(String.valueOf(str[i++]));
				num = 0;
			} else {
				bra = value(str, i + 1);
				num = bra[0];
				i = bra[1] + 1;
			}

		}
		addNum(list, num);
		return new int[] { getNum(list), i };
	}

	private static void addNum(linkedList list, int num) {
		if (!list.isEmpty()) {
			int cur = 0;
			String top = list.pollLast();
			if (top.equals("+") || top.equals("-")) {
				list.addLast(top);
			} else {
				cur = Integer.valueOf(list.pollLast());
				num = top.equals("*") ? (cur * num) : (cur / num);
			}
		}
		list.addLast(String.valueOf(num));

	}

	private static int getNum(linkedList list) {
		int res = 0;
		boolean add = true;
		String curString = null;
		int num = 0;
		while (!list.isEmpty()) {
			curString = list.pollFirst();
			if (curString.equals("+")) {
				add = true;
			} else if (curString.equals("-")) {
				add = false;
			} else {
				num = Integer.valueOf(curString);
				res += add ? num : (-num);
			}
		}
		return res;
	}
}

字符串的全排列

我们通常都思路都是将所有字符依次放在最前面，例如ABC，第一位为A，B,C，然后判断第二位，那么我们如何在字符串中标记该字符已经被我们安排在前面了？
若我们使用下标的方式，那么在每次选择都会产生一个下标，这样会很乱。
于是我们可以通过将欲放在前面的字符就直接放在前面（将字符一次和后面的交换），用一个下标指引我们前面已经定了多少的元素。
但是若我们交换后在后续调用时，数据顺序已经打乱，我们可能会造成重复情况，所以我们在每次运行后再将数据交换变成原来位置。
但是当数据有重复字符时，会出现重复的全排列，这是我们就要判断交换的字符是否和之前交换的相同，若相同，就不用交换

class PB {
    public static List list=new ArrayList<>();
    public static void process(String string){
        char[] chars = string.toCharArray();
        process(chars,0);
    }
    private static void process(char[] chars, int i){
        if (i==chars.length){//结果
            list.add(new String(chars));
            return;
        }
        boolean[] isVisited=new boolean[26];//默认只有大写字母
        for (int j=i;j 
纸牌累计分数 
 
class PB {
    public static int win(int[] arr){
        if (arr.length==0)return 0;
        return Math.max(front(arr,0,arr.length-1), end(arr,0,arr.length-1));
    }
    //先手的人对应的数据
    private static int front(int[] arr,int left,int right){
        if (left==right)return arr[left];//先手的人，最后还剩一个数据就是这个人的
        //取那个值和下一次该我选的时候我的收益最大。
        return Math.max(arr[left]+end(arr,left+1,right),arr[right]+end(arr,left,right-1));
    }
    private static int end(int[] arr, int left, int right){
        if (left==right)return 0;
        return Math.min(front(arr,left+1,right),+front(arr,left,right-1));
    }
}
 
岛数量问题 
 
class PB {
    private static int[][] arr;
    private static int N;
    private static int M;
    public static int process(int[][] arr){
        PB.arr=arr;
        PB.N=arr.length;
        PB.M=arr[0].length;
        int res=0;//记录结果
        for (int i=0;i=N||j<0||j>=M||arr[i][j]!=1)return;
        arr[i][j]=2;
        infect(i-1,j);
        infect(i+1,j);
        infect(i,j-1);
        infect(i,j+1);
    }
}
 
人气值 
 
错误代码 
public class Test {
    public static void process1(int start, int x, int y, int z, int end) {
        func(x, y, z, end, start);
    }
    private static int func(int x, int y, int z, int end, int thisNum) {
        if (end == thisNum) {
            return 0;
        }
        int resX = func(x, y, z, end, thisNum + 2) + x;
        int resY = func(x, y, z, end, thisNum * 2) + y;
        int resZ = func(x, y, z, end, thisNum - 2) + z;
        return Math.min(resX, Math.min(resY, resZ));
    }
}
 
平凡解限制 
public class Test {
    public static void main(String[] args) {
        System.out.println(process1(3, 100, 1, 2, 6));

    }

    public static int process1(int x, int y, int z, int start, int end) {
        return func(x, y, z, end, start, 0, (end - start) / 2 * x);
    }

    
    private static int func(int x, int y, int z, int end, int thisNum, int coinsNum, int generalSolution) {
        if (end == thisNum) {
            return coinsNum;
        }
        if (coinsNum > generalSolution) {
            return Integer.MAX_VALUE;
        }
        int resX = func(x, y, z, end, thisNum + 2, coinsNum + x, generalSolution);
        int resY = func(x, y, z, end, thisNum * 2, coinsNum + y, generalSolution);
        int resZ = func(x, y, z, end, thisNum - 2, coinsNum + z, generalSolution);
        return Math.min(resX, Math.min(resY, resZ));
    }
}
 
返回字符串的所有子字符串（树形） 
将该问题看成二分类问题，将所有的单个字符元素是否存在看成一个事件，通过对所有的单个字符判读存在情况就可以得出所有子字符串
这样可以理解为二叉树的情况，每一层的每个节点下有两个子节点，表示该层对应的字符是否添加进路径中，最后树的所有叶子节点对应的字符串就是所以子字符串
我们采用动态生成树的递归方法对树进行动态的遍历。（该树必定为满树） 
class PB {
    public static List list=new ArrayList<>();
    private static String s;
    public static void childrenString(String string){
        s=string;
        childrenString("",0);
    }
    
    private static void childrenString(String chlidString,int i){
        if (i==s.length()){//叶子节点
            list.add(chlidString);
            return;
        }
        childrenString(chlidString+s.charAt(i),i+1);//要这个字符
        childrenString(chlidString,i+1);//不要这个字符
    }
}
 
数字转化成字母（树形） 
 
class PB {
    public static int process(String s,int i){
        //若一个不剩或这还剩一个，就返回1（保证剩的不为0），若此时不返回，说明还剩至少两个字符
        if (s.length()==i||(s.length()==i+1&&s.charAt(i)!='0'))return 1;
        if (s.charAt(i)=='0')return 0;//没有0开头匹配的元素
        int res=process(s,i+1);//一个字符的
        if (Integer.parseInt(s.substring(i,i+2))<=26)
            res+=process(s,i+2);//若满足匹配条件，进行两个字符的
        return res;//累加的结果返回就行了
    }
}
 
背包问题（树形） 
 
和返回字符串的所有子字符串相似，判断每个物品是否装进了袋子两种选择
只需要用递归像树一样遍历所有选择取出最大值即可
这样的题可以使用动态规划O(N²),递归O(2^N),关于递归转为动态规划，后续再说。 
class PB {
    private static int maxBag;
    private static int[] weights;
    private static int[] values;
    public static int process(int[] weights,int[] values,int maxBag){
        PB.maxBag=maxBag;
        PB.weights=weights;
        PB.values=values;
        return process(0,0,0);
    }

    
    private static int process(int w,int v,int i){
        if (w>maxBag)return 0;
        if (i==weights.length)return v;
        return Math.max(process(w+weights[i],v+values[i],i+1),
                        process(w,v,i+1));
    }
}

java算法题 之 暴力递归

Java相关栏目本月热门文章

java算法题之暴力递归