X

LEETCODE 679. 24 Game 解题思路分析

题目大意:

24 点游戏

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 */+-() 的运算得到 24。

示例 1:

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

示例 2:

输入: [1, 2, 1, 2]
输出: False

注意:

  • 除法运算符 / 表示实数除法,而不是整数除法。例如 4 / (1 – 2/3) = 12 。
  • 每个运算符对两个数进行运算。特别是我们不能用 – 作为一元运算符。例如,[1, 1, 1, 1] 作为输入时,表达式 -1 – 1 – 1 – 1 是不允许的。
  • 你不能将数字连接在一起。例如,输入为 [1, 2, 1, 2] 时,不能写成 12 + 12 。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=679

解题思路分析:

本题的难点在于除法,比如2除以3,应该等于三分之二,在java中要是按照整数除法的话会等于0,这样会影响到最后的计算结果。我在解题时想到了一个比较笨的办法,即将每一个数(整数或者小数)都看作是一个分数,由分子和分母组成,我们用一个数组来表示该分数,int[] num。num[0]是分子,num[1]是分母,该数值应该是 num[0] / num[1]。比如三分之二,我们可以表示为[2,3],同理整数5可以表示为[5,1]。

有了上面的解决除法的思路,本题难度就大幅下降了。我们采用递归方式来解题,先将所有数字(总共4个数字,分别由分数数组形式表示)组成一个集合(ArrayList)传入递归方法,递归方法中,循环取出任意2个数字,对其进行加减乘除四种分数运算,分别将计算结果与剩余没有用到的数字,组成新的集合传入递归方法。递归结束条件为当前集合只有1个元素时,查看其分子与分母的商是否正好等于24,如果是返回true,反之返回false即可。循环遍历的所有情况中,只要有一种结果为true,最终的返回结果即是true。

实现代码:

boolean res; // 返回结果
public boolean judgePoint24(int[] nums) {
    // 将所有整数变为分数集合
    List<int[]> list = new ArrayList<>();
    for(int num : nums) list.add(new int[]{num, 1});
    help(list); // 递归求解
    return res;
}

void help(List<int[]> nums){
    // 如果集合中只有一个元素,或者已经找到合理的24点计算方法时,结束递归
    if(nums.size()==1 || res){
        int[] num = nums.get(0); // 取得集合中唯一的元素
        // 如果该数分母不为0,并且分子除以分母正好等于24
        if(num[1]!=0&&num[0]/num[1]==24&&num[0]%num[1]==0){
            res = true; // 返回结果为true。
        }
        return; // 结束递归
    }
    // 循环取出集合中的2个数字。
    for(int i=0;i<nums.size();i++){
        int nu1=nums.get(i)[0]; // 第一个数的分子
        int de1=nums.get(i)[1]; // 第一个数的分母
        for(int j=0;j<nums.size();j++){
            // 取出一个与第一个数不同的第二个数字
            if(i!=j){
                int nu2=nums.get(j)[0]; // 第二个数的分子
                int de2=nums.get(j)[1]; // 第二个数的分母
                // 新建一个集合,存储剩下没用到的数字
                List<int[]> list = new ArrayList<>();
                for(int k=0;k<nums.size();k++){
                    if(k!=i&&k!=j) list.add(nums.get(k));
                }
                // 两个数进行加法运算,并将结果加入新的集合
                list.add(new int[]{nu1*de2+nu2*de1, de1*de2});
                // 利用新的集合递归求解
                help(list);
                // 从新的集合中删除加法运算结果
                list.remove(list.size()-1);
                // 两个数进行减法运算,并将结果加入新的集合
                list.add(new int[]{nu1*de2-nu2*de1, de1*de2});
                // 利用新的集合递归求解
                help(list);
                // 从新的集合中删除减法运算结果
                list.remove(list.size()-1);
                // 两个数进行乘法运算,并将结果加入新的集合
                list.add(new int[]{nu1*nu2,de1*de2});
                // 利用新的集合递归求解
                help(list);
                // 从新的集合中删除乘法运算结果
                list.remove(list.size()-1);
                // 两个数进行除法运算,并将结果加入新的集合
                list.add(new int[]{nu1*de2,de1*nu2});
                // 利用新的集合递归求解
                help(list);
                // 从新的集合中删除除法运算结果
                list.remove(list.size()-1);
            }
        }
    }
}

本题解法执行时间为9ms。

Runtime: 9 ms, faster than 76.81% of Java online submissions for 24 Game.

Memory Usage: 37.7 MB, less than 93.75% of Java online submissions for 24 Game.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-679-24-game-解题思路分析/
Categories: leetcode
kwantong: