24点游戏 - algorithms

24 Game

import java.util.*;

/**
 * 题目地址：https://leetcode.com/problems/24-game/
 * 思路：每次从数组中任意选择两个元素进行运算，使得原数组大小减一，
 * 递归的进行上述操作，知道只剩下一个元素判断是否为24即可。
 */

public class Solution {
    /**
     * @param arr int整型一维数组
     * @return bool布尔型
     */
    private double eps = 1e-6;

    public boolean Game24Points(int[] arr) {
        // write code here
        if (arr == null || arr.length < 2) return false;
        List<Double> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            list.add(arr[i] * 1.0);
        }
        return isValid24(list);
    }

    public boolean isValid24(List<Double> list) {
        if (list.size() == 1) return Math.abs(list.get(0) - 24) < eps;
        for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < i; j++) {
                double p = list.get(i), q = list.get(j);
                List<Double> d = new ArrayList<>();
                d.add(p + q);
                d.add(p - q);
                d.add(q - p);
                d.add(p * q);
                if (q > eps) d.add(p / q);
                if (p > eps) d.add(q / p);
                list.remove(i);
                list.remove(j);
                for (Double aDouble : d) {
                    list.add(aDouble);
                    if (isValid24(list)) {
                        return true;
                    }
                    list.remove(list.size()-1);
                }
                //注意这里只能先添加j，然后添加i，不然会越界而且list无法还原 。
                list.add(j,q);
                list.add(i,p);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{7, 2, 1, 10};
        System.out.println(new Solution().Game24Points(arr));
    }
}