微软面试题——24点游戏

给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。

输入: cards = [4, 1, 8, 7]
输出: true
解释: (8-4) * (7-1) = 24

显而易见是回溯，但是由于题中给出除法是实数除法，所以必须使用double来进行计算

class Solution {
    static double Target = 24;
    //浮点数误差最小精度
    static double standard = 1e-6;
    public boolean judgePoint24(int[] cards) {
        return backTrack(new double[]{cards[0],cards[1],cards[2],cards[3]});
    }
    boolean backTrack(double[] nums){
        //若最终结果与target的差值小于某一数值，则证明相等
        if(nums.length ==1 )return Math.abs(nums[0]-Target)<standard;
        for(int i =0;i<nums.length;i++){
            for(int j = i+1;j<nums.length;j++){
                //建立一个数组，存储除选中的两个数以外的所有数和这两个数的运算结果
                double[] next = new double[nums.length-1];
                for(int k=0,index=0;index<nums.length;index++){
                    if(index!=i&&index!=j) next[k++] = nums[index];
                }
                //决策树选择
                for(double num:caculator(nums[i],nums[j])){
                    next[next.length-1] = num;
                    if(backTrack(next)) return true;
                }
            }
        }
        return false;
    }
    //存储两个数可以获得的所有运算结果
    ArrayList<Double> caculator(double a, double b){
        ArrayList<Double> list = new ArrayList();
        list.add(a*b);
        list.add(a+b);
        list.add(a-b);
        list.add(b-a);
        //若a绝对值小于精度，则可以认为a为零
        if(!(Math.abs(a)<standard)) list.add(b/a);
        if(!(Math.abs(b)<standard)) list.add(a/b);
        return list;
    }
}