class Solution {
public:
bool judgePoint24(vector<int>& cards) {
}
};
679. 24 点游戏
给定一个长度为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 == 41 <= cards[i] <= 9原站题解
java 解法, 执行用时: 4 ms, 内存消耗: 42 MB, 提交时间: 2023-09-27 10:59:08
class Solution {
static final int TARGET = 24;
static final double EPSILON = 1e-6;
static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
public boolean judgePoint24(int[] nums) {
List<Double> list = new ArrayList<Double>();
for (int num : nums) {
list.add((double) num);
}
return solve(list);
}
public boolean solve(List<Double> list) {
if (list.size() == 0) {
return false;
}
if (list.size() == 1) {
return Math.abs(list.get(0) - TARGET) < EPSILON;
}
int size = list.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) {
List<Double> list2 = new ArrayList<Double>();
for (int k = 0; k < size; k++) {
if (k != i && k != j) {
list2.add(list.get(k));
}
}
for (int k = 0; k < 4; k++) {
if (k < 2 && i > j) {
continue;
}
if (k == ADD) {
list2.add(list.get(i) + list.get(j));
} else if (k == MULTIPLY) {
list2.add(list.get(i) * list.get(j));
} else if (k == SUBTRACT) {
list2.add(list.get(i) - list.get(j));
} else if (k == DIVIDE) {
if (Math.abs(list.get(j)) < EPSILON) {
continue;
} else {
list2.add(list.get(i) / list.get(j));
}
}
if (solve(list2)) {
return true;
}
list2.remove(list2.size() - 1);
}
}
}
}
return false;
}
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 9.3 MB, 提交时间: 2023-09-27 10:58:20
class Solution {
public:
static constexpr int TARGET = 24;
static constexpr double EPSILON = 1e-6;
static constexpr int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
bool judgePoint24(vector<int> &nums) {
vector<double> l;
for (const int &num : nums) {
l.emplace_back(static_cast<double>(num));
}
return solve(l);
}
bool solve(vector<double> &l) {
if (l.size() == 0) {
return false;
}
if (l.size() == 1) {
return fabs(l[0] - TARGET) < EPSILON;
}
int size = l.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) {
vector<double> list2 = vector<double>();
for (int k = 0; k < size; k++) {
if (k != i && k != j) {
list2.emplace_back(l[k]);
}
}
for (int k = 0; k < 4; k++) {
if (k < 2 && i > j) {
continue;
}
if (k == ADD) {
list2.emplace_back(l[i] + l[j]);
} else if (k == MULTIPLY) {
list2.emplace_back(l[i] * l[j]);
} else if (k == SUBTRACT) {
list2.emplace_back(l[i] - l[j]);
} else if (k == DIVIDE) {
if (fabs(l[j]) < EPSILON) {
continue;
}
list2.emplace_back(l[i] / l[j]);
}
if (solve(list2)) {
return true;
}
list2.pop_back();
}
}
}
}
return false;
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-27 10:57:58
const (
TARGET = 24
EPSILON = 1e-6
ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3
)
func judgePoint24(nums []int) bool {
list := []float64{}
for _, num := range nums {
list = append(list, float64(num))
}
return solve(list)
}
func solve(list []float64) bool {
if len(list) == 0 {
return false
}
if len(list) == 1 {
return abs(list[0] - TARGET) < EPSILON
}
size := len(list)
for i := 0; i < size; i++ {
for j := 0; j < size; j++ {
if i != j {
list2 := []float64{}
for k := 0; k < size; k++ {
if k != i && k != j {
list2 = append(list2, list[k])
}
}
for k := 0; k < 4; k++ {
if k < 2 && i < j {
continue
}
switch k {
case ADD:
list2 = append(list2, list[i] + list[j])
case MULTIPLY:
list2 = append(list2, list[i] * list[j])
case SUBTRACT:
list2 = append(list2, list[i] - list[j])
case DIVIDE:
if abs(list[j]) < EPSILON {
continue
} else {
list2 = append(list2, list[i] / list[j])
}
}
if solve(list2) {
return true
}
list2 = list2[:len(list2) - 1]
}
}
}
}
return false
}
func abs(x float64) float64 {
if x < 0 {
return -x
}
return x
}
python3 解法, 执行用时: 80 ms, 内存消耗: 16 MB, 提交时间: 2023-09-27 10:57:29
'''
4个数，3种运算符，共有 12×4×6×4×2×4=921612 种可能。
可以通过回溯的方法遍历所有不同的可能性。具体做法是，使用一个列表存储目前的全部数字，
每次从列表中选出 2 个数字，再选择一种运算操作，用计算得到的结果取代选出的 2 个数字，
这样列表中的数字就减少了 1 个。重复上述步骤，直到列表中只剩下 1 个数字，
这个数字就是一种可能性的结果，等于24或不等于24.
'''
class Solution:
def judgePoint24(self, nums: List[int]) -> bool:
TARGET = 24
EPSILON = 1e-6
ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3
def solve(nums: List[float]) -> bool:
if not nums:
return False
if len(nums) == 1:
return abs(nums[0] - TARGET) < EPSILON
for i, x in enumerate(nums):
for j, y in enumerate(nums):
if i != j:
newNums = list()
for k, z in enumerate(nums):
if k != i and k != j:
newNums.append(z)
for k in range(4):
if k < 2 and i > j:
continue
if k == ADD:
newNums.append(x + y)
elif k == MULTIPLY:
newNums.append(x * y)
elif k == SUBTRACT:
newNums.append(x - y)
elif k == DIVIDE:
if abs(y) < EPSILON:
continue
newNums.append(x / y)
if solve(newNums):
return True
newNums.pop()
return False
return solve(nums)