679. 24 點(diǎn)游戲
你有 4 張寫有 1 到 9 數(shù)字的牌挫望。你需要判斷是否能通過 *立润，/，+士骤，-范删，(，) 的運(yùn)算得到24拷肌。
示例 1:
輸入: [4, 1, 8, 7]
輸出: True
解釋: (8-4) * (7-1) = 24
示例 2:
輸入: [1, 2, 1, 2]
輸出: False
注意:
- 除法運(yùn)算符 / 表示實(shí)數(shù)除法到旦，而不是整數(shù)除法。例如 4 / (1 - 2/3) = 12 巨缘。
- 每個運(yùn)算符對兩個數(shù)進(jìn)行運(yùn)算添忘。特別是我們不能用 - 作為一元運(yùn)算符。例如若锁，[1, 1, 1, 1] 作為輸入時搁骑，表達(dá)式 -1 - 1 - 1 - 1 是不允許的。
- 你不能將數(shù)字連接在一起又固。例如仲器，輸入為 [1, 2, 1, 2] 時，不能寫成 12 + 12 仰冠。
算法思路
總共有4個數(shù)乏冀，運(yùn)算得到24。
- 首先第一步肯定是挑出兩個數(shù)洋只，算出一個新的數(shù)取代挑出的兩個數(shù)辆沦；
- 然后在三個數(shù)中玩 24， 再挑出兩個數(shù)识虚，算出一個數(shù)取代它們肢扯；
- 最后在兩個數(shù)中玩 24 點(diǎn)，就可以得出判斷了担锤。
這就有了遞歸的思路：
挑出不同的兩數(shù)組合蔚晨，需要兩層循環(huán)，并且兩個數(shù)不能相同肛循。
遞歸函數(shù)：
- 設(shè)置各種運(yùn)算操作（加減乘除）— 對應(yīng)遞歸數(shù)的不同分支
- 每次嘗試一種運(yùn)算 — 選擇進(jìn)入一個分支
- 傳入長度更小的新數(shù)組繼續(xù)遞歸 — 遞歸計(jì)算當(dāng)前子樹（子問題）
- 當(dāng)做到只剩一個數(shù)時 — 到底遞歸數(shù)的地步铭腕，看看是不是24，是就返回 true育拨。（結(jié)束遞歸谨履，并且控制不讓進(jìn)入別的分支）
- 否則返回false， 告別錯誤的分支熬丧，進(jìn)入別的遞歸分支笋粟，嘗試別的運(yùn)算怀挠。
參考代碼
class Solution {
private static final int TARGET = 24;
public boolean judgePoint24(int[] num) {
if (num == null || num.length != 4) {
return false;
}
List<Double> nums = new ArrayList<>();
for (int n : num) {
nums.add(n * 1.0);
}
return dfs(nums);
}
private boolean dfs(List<Double> nums) {
if (nums.size() == 1) {
return Math.abs(nums.get(0) - TARGET) < 1e-5;
}
// 兩層循環(huán)，選擇兩個數(shù)
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums.size(); j++) {
// 兩個數(shù)不能相等
if (i == j) continue;
// 兩個數(shù)運(yùn)算后得出的新的數(shù)的集合
List<Double> next = new ArrayList<>();
for (int k = 0; k < nums.size(); k++) {
// 不包含選擇的兩個數(shù)
if (k != i && k != j) {
next.add(nums.get(k));
}
}
// 獲取兩個數(shù)
double n1 = nums.get(i), n2 = nums.get(j);
// 執(zhí)行四項(xiàng)運(yùn)算害捕，加法乘法符合交換律绿淋，a + b = b + a, a*b=b*a，可跳過其中一項(xiàng)
// 這里默認(rèn) i > j 部分跳過尝盼，以下 or 為短路語句
// 加法吞滞，乘法
if (i < j) {
next.add(n1 + n2);
if (dfs(next)) {
return true;
}
next.remove(next.size() - 1);
next.add(n1 * n2);
if (dfs(next)) {
return true;
}
next.remove(next.size() - 1);
}
// 減法
// 除法
next.add(n1 - n2);
if (dfs(next)) {
return true;
}
next.remove(next.size() - 1);
next.add(n1 / n2);
if (dfs(next)) {
return true;
}
next.remove(next.size() - 1);
}
}
return false;
}
}
以上謝謝大家，求贊求贊求贊盾沫！
