Hard

题目描述

给定一个长度为 4 的整数数组 cards。你有四张卡片，每张卡片上都有一个范围在 [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

提示：

  • cards.length == 4
  • 1 <= cards[i] <= 9

解题思路

这是一个典型的回溯算法问题。核心思路是通过递归的方式尝试所有可能的数字组合和运算符组合。

解题思路：

  1. 状态表示：使用一个数组表示当前可用的数字，初始为输入的4个数字
  2. 递归过程：每次选择两个数字进行运算，得到新的结果，然后递归处理剩余的数字
  3. 终止条件：当只剩一个数字时，检查是否接近24（考虑浮点数精度问题）
  4. 回溯操作：尝试所有可能的数字对和四种运算符

关键细节：

  • 使用浮点数进行计算，避免整数除法的问题
  • 注意除法时分母不能为0
  • 由于浮点数精度问题，判断是否等于24时使用epsilon比较
  • 加法和乘法满足交换律，减法和除法需要考虑两种顺序

时间复杂度优化： 虽然看似复杂度很高，但由于只有4个数字，实际的搜索空间是有限的，完全可以接受。

代码实现

class Solution {
public:
    bool judgePoint24(vector<int>& cards) {
        vector<double> nums;
        for (int card : cards) {
            nums.push_back(card);
        }
        return backtrack(nums);
    }
    
private:
    bool backtrack(vector<double>& nums) {
        if (nums.size() == 1) {
            return abs(nums[0] - 24) < 1e-6;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                double a = nums[i], b = nums[j];
                vector<double> next;
                
                // 将其他数字加入下一轮
                for (int k = 0; k < nums.size(); k++) {
                    if (k != i && k != j) {
                        next.push_back(nums[k]);
                    }
                }
                
                // 尝试四种运算
                vector<double> candidates = {a + b, a - b, b - a, a * b};
                if (abs(b) > 1e-6) candidates.push_back(a / b);
                if (abs(a) > 1e-6) candidates.push_back(b / a);
                
                for (double candidate : candidates) {
                    next.push_back(candidate);
                    if (backtrack(next)) return true;
                    next.pop_back();
                }
            }
        }
        return false;
    }
};

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        def backtrack(nums):
            if len(nums) == 1:
                return abs(nums[0] - 24) < 1e-6
            
            for i in range(len(nums)):
                for j in range(i + 1, len(nums)):
                    a, b = nums[i], nums[j]
                    # 剩余的数字
                    remaining = [nums[k] for k in range(len(nums)) if k != i and k != j]
                    
                    # 尝试所有运算
                    candidates = [a + b, a - b, b - a, a * b]
                    if abs(b) > 1e-6:
                        candidates.append(a / b)
                    if abs(a) > 1e-6:
                        candidates.append(b / a)
                    
                    for candidate in candidates:
                        if backtrack(remaining + [candidate]):
                            return True
            return False
        
        return backtrack([float(card) for card in cards])

public class Solution {
    public bool JudgePoint24(int[] cards) {
        var nums = new List<double>();
        foreach (int card in cards) {
            nums.Add(card);
        }
        return Backtrack(nums);
    }
    
    private bool Backtrack(List<double> nums) {
        if (nums.Count == 1) {
            return Math.Abs(nums[0] - 24) < 1e-6;
        }
        
        for (int i = 0; i < nums.Count; i++) {
            for (int j = i + 1; j < nums.Count; j++) {
                double a = nums[i], b = nums[j];
                var next = new List<double>();
                
                // 添加其他数字
                for (int k = 0; k < nums.Count; k++) {
                    if (k != i && k != j) {
                        next.Add(nums[k]);
                    }
                }
                
                // 尝试四种运算
                var candidates = new List<double> { a + b, a - b, b - a, a * b };
                if (Math.Abs(b) > 1e-6) candidates.Add(a / b);
                if (Math.Abs(a) > 1e-6) candidates.Add(b / a);
                
                foreach (double candidate in candidates) {
                    next.Add(candidate);
                    if (Backtrack(next)) return true;
                    next.RemoveAt(next.Count - 1);
                }
            }
        }
        return false;
    }
}

var judgePoint24 = function(cards) {
    const eps = 1e-6;
    
    function solve(nums) {
        if (nums.length === 1) {
            return Math.abs(nums[0] - 24) < eps;
        }
        
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                const a = nums[i];
                const b = nums[j];
                const remaining = nums.filter((_, idx) => idx !== i && idx !== j);
                
                const operations = [
                    a + b,
                    a - b,
                    b - a,
                    a * b
                ];
                
                if (Math.abs(b) > eps) operations.push(a / b);
                if (Math.abs(a) > eps) operations.push(b / a);
                
                for (const result of operations) {
                    if (solve([...remaining, result])) {
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
    
    return solve(cards);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)虽然递归深度和分支因子较大，但由于输入规模固定（4个数字），总的状态空间是常数级的
空间复杂度O(1)递归栈的深度最多为3层，使用的额外空间是常数级的