LeetCode每日一题（20200822）
程序员文章站
2022-06-16 09:18:00
原题地址思考过程：先看本题的所有可能性，四个数字排列，4*3*2=24种，然后后在两个数字之间加一个运算符号，4*4*4=64，所以穷举有1536种可能性，是一个量级不大的常数，所以穷举可行；代码实现：第一版代码执行不通过（和以下代码类似），再来思考思路是否有缺漏，我考虑到的穷举是，四个数字排列，然后以此对四个数字做运算，但是ab运算后，cd运算后，两个结果再运算，这种可能没有考虑在内。按此再修改出如下代码：public boolean judgePoint24(int[] nums)...
思考过程：
先看本题的所有可能性，四个数字排列，4*3*2=24种，然后后在两个数字之间加一个运算符号，4*4*4=64，所以穷举有1536种可能性，是一个量级不大的常数，所以穷举可行；
代码实现：
第一版代码执行不通过（和以下代码类似），再来思考思路是否有缺漏，我考虑到的穷举是，四个数字排列，然后以此对四个数字做运算，但是ab运算后，cd运算后，两个结果再运算，这种可能没有考虑在内。按此再修改出如下代码：
public boolean judgePoint24(int[] nums) {
Set<Integer> set = new HashSet<>();
Set<String> history = new HashSet<>();
for (int a = 0; a < 4; a++) {
set.add(a);
for (int b = 0; b < 4; b++) {
if (!set.contains(b)) {
set.add(b);
for (int c = 0; c < 4; c++) {
if (!set.contains(c)) {
set.add(c);
for (int d = 0; d < 4; d++) {
if (!set.contains(d)) {
if (check(nums[a], nums[b], nums[c], nums[d], history)) {
return true;
}
}
}
set.remove(c);
}
}
set.remove(b);
}
}
set.remove(a);
}
return false;
}
private boolean check(int a, int b, int c, int d, Set<String> history) {
if (history.contains(a + "-" + b + "-" + c + "-" + d)) {
return false;
}
for (int i = 0; i < 6; i++) {
float ab;
switch (i) {
default:
case 0:
ab = (float) a + (float) b;
break;
case 1:
ab = (float) a - (float) b;
break;
case 2:
ab = (float) a * (float) b;
break;
case 3:
ab = (float) a / (float) b;
break;
case 4:
ab = (float) b - (float) a;
break;
case 5:
ab = (float) b / (float) a;
}
for (int j = 0; j < 6; j++) {
float abc;
switch (j) {
default:
case 0:
abc = (float) ab + (float) c;
break;
case 1:
abc = (float) ab - (float) c;
break;
case 2:
abc = (float) ab * (float) c;
break;
case 3:
abc = (float) ab / (float) c;
break;
case 4:
abc = (float) c - (float) ab;
break;
case 5:
abc = (float) c / (float) a;
}
for (int k = 0; k < 6; k++) {
switch (k) {
default:
case 0:
if ((abc + (float) d) - 24 == 0) {
return true;
}
break;
case 1:
if ((abc - (float) d) - 24 == 0) {
return true;
}
break;
case 2:
if ((abc * (float) d) - 24 == 0) {
return true;
}
break;
case 3:
if ((abc / (float) d) - 24 == 0) {
return true;
}
break;
case 4:
if (((float) d / abc) - 24 == 0) {
return true;
}
break;
case 5:
if (((float) d - abc) - 24 == 0) {
return true;
}
break;
}
}
}
}
float ab = 0;
for (int i = 0; i < 6; i++) {
switch (i) {
default:
case 0:
ab = (float) a + (float) b;
break;
case 1:
ab = (float) a - (float) b;
break;
case 2:
ab = (float) a * (float) b;
break;
case 3:
ab = (float) a / (float) b;
break;
case 4:
ab = (float) b - (float) a;
break;
case 5:
ab = (float) b / (float) a;
break;
}
}
float cd = 0;
for (int i = 0; i < 6; i++) {
switch (i) {
default:
case 0:
cd = (float) c + (float) d;
break;
case 1:
cd = (float) c - (float) d;
break;
case 2:
cd = (float) c * (float) d;
break;
case 3:
cd = (float) c / (float) d;
break;
case 4:
cd = (float) d - (float) c;
break;
case 5:
cd = (float) d / (float) c;
break;
}
}
for (int i = 0; i < 4; i++) {
switch (i) {
default:
case 0:
if ((ab + cd) - 24 == 0) {
return true;
}
break;
case 1:
if ((ab - cd) - 24 == 0) {
return true;
}
break;
case 2:
if ((ab * cd) - 24 == 0) {
return true;
}
break;
case 3:
if ((ab / cd) - 24 == 0) {
return true;
}
break;
case 4:
if ((cd - ab) - 24 == 0) {
return true;
}
break;
case 5:
if ((cd / ab) - 24 == 0) {
return true;
}
break;
}
}
history.add(a + "-" + b + "-" + c + "-" + d);
return false;
}
依然不通过，思来想去，没有找到问题所在。
思路和我略有不同，如下：
先在四个数种找两个，进行运算，4*3*4
然后四个数变三个数，找两个运算，3*2*4
然后变成两个数，2*4
所以共有9216种。
官方代码如下：
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;
}
总结：
思考问题时，想到来这个问题的解是有限常数个，可以使用穷举法，但是在思考问题的全面性和代码实现上还有很大的不足。
按照官方的思路，实现自己的代码（待续。。。）
本文地址：https://blog.csdn.net/Payne_xy/article/details/108188123