幸运的袋子_字符串通配符问题

幸运的袋子

幸运的袋子

import java.util.*;
public class Main{
    public static int dsfCount(int[] array,int n,int pos,int sum,int multi){
        int count = 0;
        for(int i = pos;i<n;i++){
            sum += array[i];
            multi *= array[i];
            if(sum>multi){
                //满足幸运袋子!
                //count +1 并且往下一层遍历!
                count = count + 1 + dsfCount(array,n,i+1,sum,multi);
            }else if(array[i]==1){//如果 这个数是1 1 加上任何数的和都大于积!
                //需要往深度遍历! count + 加上之后的幸运组合!
                count = count + dsfCount(array,n,i+1,sum,multi);
            }else{
                //不满足条件,这层已经不可能是幸运的袋子了!就直接回退!
                break;
            }
            //回退,
            sum -= array[i];
            multi /= array[i];
            while(i+1<n&&array[i]==array[i+1]){
                //相同的球不可重复计算
                i++;//跳过!
            }
        }
        return count;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for(int i = 0;i<n;i++){
            array[i] = sc.nextInt();
        }
        //排序!
        Arrays.sort(array);
        int count = dsfCount(array,n,0,0,1);
        System.out.println(count);
    }
}

回溯小总结

• 每一层就添加了一个数,每次都深度遍历进入下一层(函数)!
• 要有递归出口!递归出来就相当于这层结束! 并不用回退,因为这层不会再往后计算了
• 而 回退指的是这层的这个数已经使用过,不用了,要换下一个数!

break:直接结束这一层递归!

回退: 完成了这层的当前数计算!

字符串通配符

字符串通配符

动归问题:

import java.util.Scanner;
public class Main{
    public static boolean helpfun(String str1,String str2){
        int str1Len = str1.length();//通配符
        int str2Len = str2.length();
        boolean[][] result = new boolean[str2Len+1][str1Len+1];
        result[0][0] = true;//空字符串匹配空字符!
        for(int i = 0;i<=str2Len;i++){//待匹配的字符!
            for(int j = 1;j<=str1Len;j++){//通配符!
                char tmp1 = str1.charAt(j-1);
                if(tmp1=='*'||tmp1=='?'){ //为*或者? 一起处理!
                    if(i==0){ //防止越界! 这里看 前面是否匹配上就好!
                        result[i][j] = result[i][j-1];
                    }else{ 
                        char t = str2.charAt(i-1);
                        //通配符 只能匹配 字母 . 数字!
                        if(t>='a'&&t<='z'||t>='0'&&t<='9'||t=='.'){
                            if(tmp1=='?'){
                               result[i][j] = result[i-1][j-1]; 
                            }else{ //左边和上面相或!
                               result[i][j] = result[i][j-1]||result[i-1][j];  
                            }
                        }
                    }
                }else{
                   if(i>0&&tmp1==str2.charAt(i-1)){//是否相等!
                       result[i][j] = result[i-1][j-1];
                   }
                }
            }
        }
      return result[str2Len][str1Len];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        System.out.println(helpfun(str1,str2));
    }
}

注意:这里的 i-1 j-1 是字符串位置防止越界!

而我们的二维数组保存了 字符串-1``-1 的辅助结果 true~

这里的字符遍历是要减一位置开始! 而二维数组的结果是正常下标!