679. 24 Game

用户1147447

发布于 2019-05-26 00:44:59

2300

发布于 2019-05-26 00:44:59

文章被收录于专栏：机器学习入门

LWC 50：679. 24 Game

Problem:

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:

Input: [4, 1, 8, 7] Output: True Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1, 2, 1, 2] Output: False

Note:

The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

观察可以发现状态数非常少，所以完全可以采用暴力构造，暴力计算，暴力搜索。4个数字有24中情况，运算符有4种，3个位置有64种情况，所以只需要枚举出64 * 24中算数表达式的值即可。

我的代码：

    char[] op = new char[] { '+', '-', '*', '/' };
    public boolean judgePoint24(int[] nums) {
        ops = new HashSet<>();
        permutation(nums, 0, new boolean[4], "");
        for (String oo : ops) {
            Set<Double> ans = cal(oo);
            for (double d : ans) {
                if (Math.abs(d - 24) <= 0.0000000001) return true;
            }
        }
        return false;
    }

    Set<Double> cal(String oo) {
        int cnt = 0;
        Set<Double> ans = new HashSet<>();
        for (int i = 0; i < oo.length(); ++i) {
            if (oo.charAt(i) == '+') {
                Set<Double> left = cal(oo.substring(0, i));
                Set<Double> right = cal(oo.substring(i + 1, oo.length()));
                cnt++;
                for (double a1 : left) {
                    for (double a2 : right) {
                        ans.add(a1 + a2);
                    }
                }
            }
            if (oo.charAt(i) == '-') {
                Set<Double> left = cal(oo.substring(0, i));
                Set<Double> right = cal(oo.substring(i + 1, oo.length()));
                cnt++;
                for (double a1 : left) {
                    for (double a2 : right) {
                        ans.add(a1 - a2);
                    }
                }
            }
            if (oo.charAt(i) == '*') {
                Set<Double> left = cal(oo.substring(0, i));
                Set<Double> right = cal(oo.substring(i + 1, oo.length()));
                cnt++;
                for (double a1 : left) {
                    for (double a2 : right) {
                        ans.add(a1 * a2);
                    }
                }
            }
            if (oo.charAt(i) == '/') {
                Set<Double> left = cal(oo.substring(0, i));
                Set<Double> right = cal(oo.substring(i + 1, oo.length()));
                cnt++;
                for (double a1 : left) {
                    for (double a2 : right) {
                        ans.add(a1 / a2);
                    }
                }
            }

        }
        if (cnt == 0) {
            ans.add(Double.parseDouble(oo));
            return ans;
        }
        return ans;
    }

    Set<String> ops;
    void permutation(int[] nums, int i, boolean[] vis, String ans) {
        if (i >= nums.length) {
            ops.add(ans.substring(0, ans.length() - 1));
            return;
        }
        for (int j = 0; j < nums.length; ++j) {
            if (!vis[j]) {
                vis[j] = true;
                for (int c = 0; c < 4; ++c) {
                    permutation(nums, i + 1, vis, ans + nums[j] + op[c]);
                }
                vis[j] = false;
            }
        }
    }

精简版本：

    public boolean judgePoint24(int[] nums) {
        ops = new int[24][4];   
        permutation(nums, 0, new boolean[4], new int[4]);
        for (int i = 0; i < 24; ++i) {
            Set<Double> ans = cal(ops[i], 0, 3);
            for (double d : ans) {
                if (Math.abs(d - 24) <= 0.0000000001) return true;
            }
        }
        return false;
    }

    int[][] ops;
    int tot = 0;
    void permutation(int[] nums, int i, boolean[] vis, int[] tmp) {
        if (i == 4) {
            for (int j = 0; j < 4; ++j) {
                ops[tot][j] = tmp[j];
            }
            tot++;
            return;
        }
        for (int j = 0; j < nums.length; ++j) {
            if (!vis[j]) {
                tmp[i] = nums[j];
                vis[j] = true;
                permutation(nums, i + 1, vis, tmp);
                vis[j] = false;
            }
        }
    }

    Set<Double> cal(int[] nums, int start, int end){
        Set<Double> ans = new HashSet<>();
        if (start == end) {
            return Collections.singleton(new Double(nums[start]));
        }
        else {
            for (int i = start; i < end; ++i) {
                Set<Double> left = cal(nums, start, i);
                Set<Double> right = cal(nums, i + 1, end);
                for (double a1 : left) {
                    for (double a2 : right) {
                        ans.add(a1 + a2);
                        ans.add(a1 - a2);
                        ans.add(a1 * a2);
                        ans.add(a1 / a2);
                    }
                }
            }
            return ans;
        }
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017年09月21日，如有侵权请联系 cloudcommunity@tencent.com 删除

division