Question

679. 24 点游戏

English Version

题目描述

给定一个长度为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

 

提示:

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

解法

方法一：DFS

我们设计一个函数 $dfs(nums)$，其中 $nums$ 表示当前的数字序列，函数返回一个布尔值，表示是否存在一种排列方式，使得这个数字序列可以得到 $24$。

如果 $nums$ 的长度为 $1$，那么只有当这个数字等于 $24$ 时，我们才返回 $true$，否则返回 $false$。

否则，我们可以枚举 $nums$ 中的任意两个数 $a$ 和 $b$ 作为左右两个操作数，枚举 $a$ 和 $b$ 之间的运算符 $op$，那么 $a\ op\ b$ 的结果就可以作为新的数字序列的一个元素，我们将其加入到新的数字序列中，并从 $nums$ 中移除 $a$ 和 $b$，然后递归地调用 $dfs$ 函数，如果返回 $true$，那么我们就找到了一种排列方式，使得这个数字序列可以得到 $24$，我们就返回 $true$。

如果枚举完所有的情况都没有返回 $true$，那么我们就返回 $false$。

class Solution:
  def judgePoint24(self, cards: List[int]) -> bool:
    def dfs(nums: List[float]):
      n = len(nums)
      if n == 1:
        if abs(nums[0] - 24) < 1e-6:
          return True
        return False
      ok = False
      for i in range(n):
        for j in range(n):
          if i != j:
            nxt = [nums[k] for k in range(n) if k != i and k != j]
            for op in ops:
              match op:
                case "/":
                  if nums[j] == 0:
                    continue
                  ok |= dfs(nxt + [nums[i] / nums[j]])
                case "*":
                  ok |= dfs(nxt + [nums[i] * nums[j]])
                case "+":
                  ok |= dfs(nxt + [nums[i] + nums[j]])
                case "-":
                  ok |= dfs(nxt + [nums[i] - nums[j]])
              if ok:
                return True
      return ok

    ops = ("+", "-", "*", "/")
    nums = [float(x) for x in cards]
    return dfs(nums)

class Solution {
  private final char[] ops = {'+', '-', '*', '/'};

  public boolean judgePoint24(int[] cards) {
    List<Double> nums = new ArrayList<>();
    for (int num : cards) {
      nums.add((double) num);
    }
    return dfs(nums);
  }

  private boolean dfs(List<Double> nums) {
    int n = nums.size();
    if (n == 1) {
      return Math.abs(nums.get(0) - 24) < 1e-6;
    }
    boolean ok = false;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i != j) {
          List<Double> nxt = new ArrayList<>();
          for (int k = 0; k < n; ++k) {
            if (k != i && k != j) {
              nxt.add(nums.get(k));
            }
          }
          for (char op : ops) {
            switch (op) {
              case '/' -> {
                if (nums.get(j) == 0) {
                  continue;
                }
                nxt.add(nums.get(i) / nums.get(j));
              }
              case '*' -> {
                nxt.add(nums.get(i) * nums.get(j));
              }
              case '+' -> {
                nxt.add(nums.get(i) + nums.get(j));
              }
              case '-' -> {
                nxt.add(nums.get(i) - nums.get(j));
              }
            }
            ok |= dfs(nxt);
            if (ok) {
              return true;
            }
            nxt.remove(nxt.size() - 1);
          }
        }
      }
    }
    return ok;
  }
}

class Solution {
public:
  bool judgePoint24(vector<int>& cards) {
    vector<double> nums;
    for (int num : cards) {
      nums.push_back(static_cast<double>(num));
    }
    return dfs(nums);
  }

private:
  const char ops[4] = {'+', '-', '*', '/'};

  bool dfs(vector<double>& nums) {
    int n = nums.size();
    if (n == 1) {
      return abs(nums[0] - 24) < 1e-6;
    }
    bool ok = false;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i != j) {
          vector<double> nxt;
          for (int k = 0; k < n; ++k) {
            if (k != i && k != j) {
              nxt.push_back(nums[k]);
            }
          }
          for (char op : ops) {
            switch (op) {
            case '/':
              if (nums[j] == 0) {
                continue;
              }
              nxt.push_back(nums[i] / nums[j]);
              break;
            case '*':
              nxt.push_back(nums[i] * nums[j]);
              break;
            case '+':
              nxt.push_back(nums[i] + nums[j]);
              break;
            case '-':
              nxt.push_back(nums[i] - nums[j]);
              break;
            }
            ok |= dfs(nxt);
            if (ok) {
              return true;
            }
            nxt.pop_back();
          }
        }
      }
    }
    return ok;
  }
};

func judgePoint24(cards []int) bool {
  ops := [4]rune{'+', '-', '*', '/'}
  nums := make([]float64, len(cards))
  for i, num := range cards {
    nums[i] = float64(num)
  }
  var dfs func([]float64) bool
  dfs = func(nums []float64) bool {
    n := len(nums)
    if n == 1 {
      return math.Abs(nums[0]-24) < 1e-6
    }
    ok := false
    for i := 0; i < n; i++ {
      for j := 0; j < n; j++ {
        if i != j {
          var nxt []float64
          for k := 0; k < n; k++ {
            if k != i && k != j {
              nxt = append(nxt, nums[k])
            }
          }
          for _, op := range ops {
            switch op {
            case '/':
              if nums[j] == 0 {
                continue
              }
              nxt = append(nxt, nums[i]/nums[j])
            case '*':
              nxt = append(nxt, nums[i]*nums[j])
            case '+':
              nxt = append(nxt, nums[i]+nums[j])
            case '-':
              nxt = append(nxt, nums[i]-nums[j])
            }
            ok = ok || dfs(nxt)
            if ok {
              return true
            }
            nxt = nxt[:len(nxt)-1]
          }
        }
      }
    }
    return ok
  }

  return dfs(nums)
}

function judgePoint24(cards: number[]): boolean {
  const ops: string[] = ['+', '-', '*', '/'];
  const dfs = (nums: number[]): boolean => {
    const n: number = nums.length;
    if (n === 1) {
      return Math.abs(nums[0] - 24) < 1e-6;
    }
    let ok: boolean = false;
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (i !== j) {
          const nxt: number[] = [];
          for (let k = 0; k < n; k++) {
            if (k !== i && k !== j) {
              nxt.push(nums[k]);
            }
          }
          for (const op of ops) {
            switch (op) {
              case '/':
                if (nums[j] === 0) {
                  continue;
                }
                nxt.push(nums[i] / nums[j]);
                break;
              case '*':
                nxt.push(nums[i] * nums[j]);
                break;
              case '+':
                nxt.push(nums[i] + nums[j]);
                break;
              case '-':
                nxt.push(nums[i] - nums[j]);
                break;
            }
            ok = ok || dfs(nxt);
            if (ok) {
              return true;
            }
            nxt.pop();
          }
        }
      }
    }
    return ok;
  };

  return dfs(cards);
}