⭐ 题目日期：

腾讯 - 2024/9/14

🌳 题目描述：

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

你须遵守以下规则:

• 除法运算符 '/' 表示实数除法，而不是整数除法。
  • 例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
• 每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
  • 例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
• 你不能把数字串在一起
  • 例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。

如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。

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

🕵🏽 面试评估：

这道题可以用递归或迭代解题，思路不难，难在实现，对代码的设计能力要求高。

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

24 点的解题思路在于计算顺序，一共分以下几种：

以 A, B, C, D 四个数为例，

2 - 2 型

1. （AB）(CD), 例如：(3 * 2) * (5 - 1)

1 - 3 型

1. A ((BC)D)
2. A(B(CD))

3 - 1 型

1. ((AB)C)D
2. (A(BC))D

枚举以上类型，检查是否有结果为 24。

💻代码：

Java

    static final double EPSILON = 1e-6;
    static final int TWENTYFOUR = 24;
    static final int NUMCARDS = 4;
    static final int DISALLOWED_DIVIDOR = 0;

    public boolean judgePoint24(int[] cards) {
        for (int i = 0; i < cards.length; i++) {
            for (int j = 0; j < cards.length; j++) {
                for (int m = 0; m < cards.length; m++) {
                    for (int n = 0; n < cards.length; n++) {
                        if (isValidCards(i, j, m, n)) {
                            // 2 - 2
                            List<Double> resultIJ = calculateTwoNums(cards[i], cards[j]);
                            List<Double> resultMN = calculateTwoNums(cards[m], cards[n]);
                            for (double num : resultIJ) {
                                List<Double> resultMNIJ = calculateTwoNumsPlus(resultMN, num, false);
                                if (has24(resultMNIJ)) {
                                    return true;
                                }
                            }
                            
                            // 1 - 3: 1 ((2)1)
                            List<Double> resultJM = calculateTwoNums(cards[j], cards[m]);
                            List<Double> resultJMN = calculateTwoNumsPlus(resultJM, cards[n], true);
                            List<Double> resultJMNI = calculateTwoNumsPlus(resultJMN, cards[i], false);
                            if (has24(resultJMNI)) {
                                return true;
                            }
                            
                            // 1 - 3: 1(1(2))
                            List<Double> resultMNJ = calculateTwoNumsPlus(resultMN, cards[j], false);
                            List<Double> resultMNJI = calculateTwoNumsPlus(resultMNJ, cards[i], false);
                            if (has24(resultMNJI)) {
                                return true;
                            }
                            
                            // 3 - 1 : ((2)1)1
                            List<Double> resultIJM = calculateTwoNumsPlus(resultIJ, cards[m], true);
                            List<Double> resultIJMN = calculateTwoNumsPlus(resultIJM, cards[n], true);
                            if (has24(resultIJMN)) {
                                return true;
                            }
                            
                            // 3 - 1 : (1(2))1
                            List<Double> resultJMI = calculateTwoNumsPlus(resultJM, cards[i], false);
                            List<Double> resultJMIN = calculateTwoNumsPlus(resultJMI, cards[n], true);
                            if (has24(resultJMIN)) {
                                return true;
                            }
                        }
                    }
                }
            }
        }

        return false;
    }

    private boolean isValidCards(int i, int j, int m, int n) {
        Set<Integer> set = new HashSet<>();
        set.addAll(Arrays.asList(i, j, m, n));
        return set.size() == NUMCARDS;
    }

    private boolean has24(List<Double> result) {
        for (double num : result) {
            if (Math.abs(num - TWENTYFOUR) < EPSILON) {
                return true;
            }
        }

        return false;
    }

    public List<Double> calculateTwoNums(double num1, double num2) {
        List<Double> result = new ArrayList<>();
        result.addAll(Arrays.asList(num1 + num2, num1 - num2, num1 * num2));
        if (Math.abs(num2 - DISALLOWED_DIVIDOR) >= EPSILON) {
            result.add(num1 / num2);
        }

        return result;
    }
    
    public List<Double> calculateTwoNumsPlus(List<Double> list, double num, boolean listItemFirst) {
        List<Double> result = new ArrayList<>();
        for (double item : list) {
            List<Double> temp;
            if (listItemFirst) {
                temp = calculateTwoNums(item, num);
            } else {
                temp = calculateTwoNums(num, item);
            }
            result.addAll(temp);
        }
        
        return result;
    }

Python

EPSILON = 1e-6
TWENTYFOUR = 24
NUMCARDS = 4
DISALLOWED_DIVIDOR = 0

class Solution:
    def judgePoint24(self, cards:List[int]) -> bool():
        def is_valid_cards(i, j, m, n):
            return len(set([i, j, m, n])) == NUMCARDS

        def has_24(result):
            return any(abs(num - TWENTYFOUR) < EPSILON for num in result)

        def calculate_two_nums(num1, num2):
            result = [num1 + num2, num1 - num2, num1 * num2]
            if abs(num2 - DISALLOWED_DIVIDOR) >= EPSILON:
                result.append(num1 / num2)
            return result

        def calculate_two_nums_plus(lst, num, list_item_first):
            result = []
            for item in lst:
                if list_item_first:
                    result.extend(calculate_two_nums(item, num))
                else:
                    result.extend(calculate_two_nums(num, item))
            return result

        for i in range(len(cards)):
            for j in range(len(cards)):
                for m in range(len(cards)):
                    for n in range(len(cards)):
                        if is_valid_cards(i, j, m, n):
                            # 2 - 2
                            result_ij = calculate_two_nums(cards[i], cards[j])
                            result_mn = calculate_two_nums(cards[m], cards[n])
                            for num in result_ij:
                                result_mnij = calculate_two_nums_plus(result_mn, num, False)
                                if has_24(result_mnij):
                                    return True

                            # 1 - 3: 1 ((2)1)
                            result_jm = calculate_two_nums(cards[j], cards[m])
                            result_jmn = calculate_two_nums_plus(result_jm, cards[n], True)
                            result_jmni = calculate_two_nums_plus(result_jmn, cards[i], False)
                            if has_24(result_jmni):
                                return True

                            # 1 - 3: 1(1(2))
                            result_mnj = calculate_two_nums_plus(result_mn, cards[j], False)
                            result_mnji = calculate_two_nums_plus(result_mnj, cards[i], False)
                            if has_24(result_mnji):
                                return True

                            # 3 - 1: ((2)1)1
                            result_ijm = calculate_two_nums_plus(result_ij, cards[m], True)
                            result_ijmn = calculate_two_nums_plus(result_ijm, cards[n], True)
                            if has_24(result_ijmn):
                                return True

                            # 3 - 1: (1(2))1
                            result_jmi = calculate_two_nums_plus(result_jm, cards[i], False)
                            result_jmin = calculate_two_nums_plus(result_jmi, cards[n], True)
                            if has_24(result_jmin):
                                return True

        return False

🚵🏻复杂度分析：

时间复杂度：O(1), 理论组合数固定，不会随着输入的不同发生变化。

空间复杂度：O(1)

🔬在线评测(Online Judge):

题目链接