作者：whisper

链接：https://www.proprogrammar.com/article/822

声明：请尊重原作者的劳动，如需转载请注明出处

679. 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 。

先看一下我自己的写法

class Solution {
    int[] n;
    boolean res;
    int[] compute;
    int available;
    int count;
    // 才4个数，数据量很少，暴力计算
    public boolean judgePoint24(int[] nums) {
        n = nums;
        res = false;
        
        for(int i = 0; i < 4; i++){
            count = 3;
            available = 15 - (1<<i);
            compute = new int[]{nums[i], 1};
            helper();
            
        }

        return res || helper2();
    }

    private void helper(){
      if(res){
          return;
      }
        for(int i = 0; i < 4; i++){
            if((available & (1<<i)) > 0){
                int[] temp;
                available -= (1<<i);
                count--;

                // 1: +
                compute[0] += compute[1] * n[i];
                // System.out.println(compute[0] + " " + compute[1]);
                if(compute[1] != 0 && compute[0] % compute[1] == 0 && compute[0] / compute[1] == 24 && count == 0){
                    res = true;
                    return;
                }
                helper();
                compute[0] -= compute[1] * n[i];

                // 2: -
                compute[0] -= compute[1] * n[i];
                // System.out.println(compute[0] + " " + compute[1]);
                if(compute[1] != 0 && compute[0] % compute[1] == 0 && compute[0] / compute[1] == 24 && count == 0){
                    res = true;
                    return;
                }
                helper();
                compute[0] += compute[1] * n[i];
                
                // 3: *
                temp = new int[]{compute[0], compute[1]};
                if(compute[1] != 0 && n[i] % compute[1] == 0){
                    compute[0] *= (n[i] / compute[1]); 
                    compute[1] = 1;
                    
                }else{
                    compute[0] *= n[i];
                }
                // System.out.println(compute[0] + " " + compute[1]);
                if(compute[1] != 0 && compute[0] % compute[1] == 0 && compute[0] / compute[1] == 24 && count == 0){
                    res = true;
                    return;
                }
                helper();
                compute = temp;

                // 4: /
                temp = new int[]{compute[0], compute[1]};
                if(n[i] != 0 && compute[0] % n[i] == 0){
                    
                    compute[0] /= n[i]; 
                }else if(n[i] != 0){
                    compute[1] *= n[i];
                }
                // System.out.println(compute[0] + " " + compute[1]);
                if(compute[1] != 0 && compute[0] % compute[1] == 0 && compute[0] / compute[1] == 24 && count == 0){
                    res = true;
                    return;
                }
                if(n[i] != 0){
                    helper();
                }
                
                compute = temp;

                // 5: -
                compute[0] = n[i] * compute[1] - compute[0];
                // System.out.println(compute[0] + " " + compute[1]);
                if(compute[1] != 0 && compute[0] % compute[1] == 0 && compute[0] / compute[1] == 24 && count == 0){
                    res = true;
                    return;
                }
                helper();
                compute[0] = n[i] * compute[1] - compute[0];
                
                // 6: /
                temp = new int[]{compute[0], compute[1]};
                if(compute[0] != 0 && n[i] % compute[0] == 0){
                    
                    compute[0] = n[i] / compute[0] * compute[1]; 
                    compute[1] = 1;
                }else{
                    int t = compute[1];
                    compute[1] = compute[0];
                    compute[0] = n[i] * t;
                }
                
                if(compute[1] != 0 && compute[0] % compute[1] == 0 && compute[0] / compute[1] == 24 && count == 0){
                    res = true;
                    return;
                }
                if(temp[0] != 0){
                    helper();
                }
                
                compute = temp;
                count++;
                available += (1<<i);
            }
        }
        
    }

    private boolean helper2(){
        int[][] h = new int[][]{{0,1},{0,2},{0,3},{1,2},{1,3},{2,3}};

        for(int i = 0; i < h.length / 2; i++){
            for(int j = 1; j <= 6; j++){
                for(int k = 1; k <= 6; k++){
                    int[] c1 = compute(new int[]{n[h[i][0]], 1}, new int[]{n[h[i][1]], 1}, j);
                    int[] c2 = compute(new int[]{n[h[5-i][0]], 1}, new int[]{n[h[5-i][1]], 1}, k);
                    if(c1[0] != 99999 && c2[0] != 99999){
                        for(int x = 1; x <= 6; x++){
                            int[] c3 = compute(c1, c2, x);
                            if(c3[0] != 99999 && c3[1] != 0 && c3[0] % c3[1] == 0 && c3[0] / c3[1] == 24){
                                return true;
                            }
                        }
                    }
                }
            }
        }

        return false;
    }

    private int[] compute(int[] i1, int i2[], int type){
        switch(type){
            case 1:

                return new int[]{i1[0]*i2[1]+i2[0]*i1[1], i1[1]*i2[1]};
            
            case 2:
                return new int[]{i1[0]*i2[1]-i2[0]*i1[1], i1[1]*i2[1]};
            
            case 3:
                return new int[]{i1[0]*i2[0],i1[1]*i2[1]};
            
            case 4:
                if(i2[0] == 0){
                    return new int[]{99999, -1};
                }
                return new int[]{i1[0]*i2[1], i1[1]*i2[0]};
            
            case 5:
                return new int[]{i2[0]*i1[1]-i1[0]*i2[1], i1[1]*i2[1]};
            
            default:
                if(i1[0] == 0){
                    return new int[]{99999, -1};
                }
                return new int[]{i2[0]*i1[1], i1[0]*i2[1]};
        }
    }
}

分成两类，一类是只有一个数与另一个数运算(helper函数完成），如(1+2)*3+4，1与2再与3再与4，是一个一个数运算，另一类是有两个数运算（helper2函数完成），如(1+2)*(3-4)，1与2，3与4是一个数与一个数运算，它们之间是两个数与两个数运算，对两个数a, b，可能的操作有6种a+b,a-b,a*b,a/b,b-a,b/a，使用helper递归，先内层运算后外层运算，可以包括所有的第一类情况，第二类情况只有一种，先一一运算，再两两运算，helper2函数完成

缺点：按部就班，分类运算，没用什么特别的算法，代码长，效率低，但简单易懂，是那种不懂算法的人也能看明白的一般方法

下面再看一下其它人的优秀的算法

class Solution {
    public boolean judgePoint24(int[] nums) {
        double[] nums_2 = new double[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            nums_2[i] = nums[i];
        }
        
        return dfs(nums_2);
    }
    
    private boolean dfs(double[] nums_2) {
        if (nums_2.length == 1) {
            return Math.abs(nums_2[0] - 24.0) < 0.001;
        }
       
        for (int i = 0; i < nums_2.length; i++) {
            for (int j = i + 1; j < nums_2.length; j++) {
                double[] nums_3 = new double[nums_2.length - 1];
                 
                for (int k = 0, index = 0; k < nums_2.length; k++) {
                    if (k != i && k != j) {
                        nums_3[index++] = nums_2[k];
                    }
                 }
                 
                for (double r : compute(nums_2[i], nums_2[j])) {
                    nums_3[nums_3.length - 1] = r;
                    
                    if (dfs(nums_3)) {
                        return true;
                    }
                }
              }
          }
         
          return false;
      }
     
      private double[] compute(double i, double j) {
          return new double[]{i + j, i - j, j - i, i * j, i / j, j / i};
      }
}

这其实也是列举出所有的可能情况，先两两数字运算，结果作为另一个数字，数字个数减1，数字个数减到1（减3次）时判断是否为24，使用double代替int，当double数值与24绝对值相差很小时（小于0.001），那么认为就是24，代码简洁，简短

其实像第一种写100多行的写法90%以上都是有问题的，leetcode上的题目，肯定是有对应的比较优秀的解决方法的，代码写得过长，不是代码水平不行，就是对问题的理解不够深入，如果你代码水平不行，或者用时过长，代码过长，可以看看别人的优秀的解法，学习别人的代码与解法

亲爱的读者：有时间可以点赞评论一下