LeetCode每日一题(20200822)
程序员文章站
2022-03-23 09:08:41
原题地址思考过程:先看本题的所有可能性,四个数字排列,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
推荐阅读
-
博客推荐:jythoner:Java每日一题系列
-
【Leetcode每日笔记】剑指 Offer 47. 礼物的最大价值(Python)
-
【LeetCode】第一题:两数之和
-
2020_10_15 每日一题 填充每个节点的下一个右侧节点指针
-
编程每日一题_C程序设计_求累加数据平均值
-
【Leetcode 每日一题】842. 将数组拆分成斐波那契序列(DFS)
-
leetcode每日一题—842.将数组拆分成斐波那契数列
-
leetcode第一题两数之和击败了 98.11% 的用户的答案(C++)
-
Leetcde每日一题:160.intersection-of-two-linked-lists(相交链表)
-
每日一题:面向对象的特征有哪些?