作者:whisper
链接:https://www.proprogrammar.com/article/822
声明:请尊重原作者的劳动,如需转载请注明出处
你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *
,/
,+
,-
,(
,)
的运算得到 24。
示例 1:
输入: [4, 1, 8, 7] 输出: True 解释: (8-4) * (7-1) = 24
示例 2:
输入: [1, 2, 1, 2] 输出: False
注意:
除法运算符 / 表示实数除法,而不是整数除法。例如 4 / (1 - 2/3) = 12 。 每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如,[1, 1, 1, 1] 作为输入时,表达式 -1 - 1 - 1 - 1 是不允许的。 你不能将数字连接在一起。例如,输入为 [1, 2, 1, 2] 时,不能写成 12 + 12 。
先看一下我自己的写法
class Solution {
int[] n;
boolean res;
int[] compute;
int available;
int count;
// 才4个数,数据量很少,暴力计算
public boolean judgePoint24(int[] nums) {
n = nums;
res = false;
for(int i = 0; i < 4; i++){
count = 3;
available = 15 - (1<<i);
compute = new int[]{nums[i], 1};
helper();
}
return res || helper2();
}
private void helper(){
if(res){
return;
}
for(int i = 0; i < 4; i++){
if((available & (1<<i)) > 0){
int[] temp;
available -= (1<<i);
count--;
// 1: +
compute[0] += compute[1] * n[i];
// System.out.println(compute[0] + " " + compute[1]);
if(compute[1] != 0 && compute[0] % compute[1] == 0 && compute[0] / compute[1] == 24 && count == 0){
res = true;
return;
}
helper();
compute[0] -= compute[1] * n[i];
// 2: -
compute[0] -= compute[1] * n[i];
// System.out.println(compute[0] + " " + compute[1]);
if(compute[1] != 0 && compute[0] % compute[1] == 0 && compute[0] / compute[1] == 24 && count == 0){
res = true;
return;
}
helper();
compute[0] += compute[1] * n[i];
// 3: *
temp = new int[]{compute[0], compute[1]};
if(compute[1] != 0 && n[i] % compute[1] == 0){
compute[0] *= (n[i] / compute[1]);
compute[1] = 1;
}else{
compute[0] *= n[i];
}
// System.out.println(compute[0] + " " + compute[1]);
if(compute[1] != 0 && compute[0] % compute[1] == 0 && compute[0] / compute[1] == 24 && count == 0){
res = true;
return;
}
helper();
compute = temp;
// 4: /
temp = new int[]{compute[0], compute[1]};
if(n[i] != 0 && compute[0] % n[i] == 0){
compute[0] /= n[i];
}else if(n[i] != 0){
compute[1] *= n[i];
}
// System.out.println(compute[0] + " " + compute[1]);
if(compute[1] != 0 && compute[0] % compute[1] == 0 && compute[0] / compute[1] == 24 && count == 0){
res = true;
return;
}
if(n[i] != 0){
helper();
}
compute = temp;
// 5: -
compute[0] = n[i] * compute[1] - compute[0];
// System.out.println(compute[0] + " " + compute[1]);
if(compute[1] != 0 && compute[0] % compute[1] == 0 && compute[0] / compute[1] == 24 && count == 0){
res = true;
return;
}
helper();
compute[0] = n[i] * compute[1] - compute[0];
// 6: /
temp = new int[]{compute[0], compute[1]};
if(compute[0] != 0 && n[i] % compute[0] == 0){
compute[0] = n[i] / compute[0] * compute[1];
compute[1] = 1;
}else{
int t = compute[1];
compute[1] = compute[0];
compute[0] = n[i] * t;
}
if(compute[1] != 0 && compute[0] % compute[1] == 0 && compute[0] / compute[1] == 24 && count == 0){
res = true;
return;
}
if(temp[0] != 0){
helper();
}
compute = temp;
count++;
available += (1<<i);
}
}
}
private boolean helper2(){
int[][] h = new int[][]{{0,1},{0,2},{0,3},{1,2},{1,3},{2,3}};
for(int i = 0; i < h.length / 2; i++){
for(int j = 1; j <= 6; j++){
for(int k = 1; k <= 6; k++){
int[] c1 = compute(new int[]{n[h[i][0]], 1}, new int[]{n[h[i][1]], 1}, j);
int[] c2 = compute(new int[]{n[h[5-i][0]], 1}, new int[]{n[h[5-i][1]], 1}, k);
if(c1[0] != 99999 && c2[0] != 99999){
for(int x = 1; x <= 6; x++){
int[] c3 = compute(c1, c2, x);
if(c3[0] != 99999 && c3[1] != 0 && c3[0] % c3[1] == 0 && c3[0] / c3[1] == 24){
return true;
}
}
}
}
}
}
return false;
}
private int[] compute(int[] i1, int i2[], int type){
switch(type){
case 1:
return new int[]{i1[0]*i2[1]+i2[0]*i1[1], i1[1]*i2[1]};
case 2:
return new int[]{i1[0]*i2[1]-i2[0]*i1[1], i1[1]*i2[1]};
case 3:
return new int[]{i1[0]*i2[0],i1[1]*i2[1]};
case 4:
if(i2[0] == 0){
return new int[]{99999, -1};
}
return new int[]{i1[0]*i2[1], i1[1]*i2[0]};
case 5:
return new int[]{i2[0]*i1[1]-i1[0]*i2[1], i1[1]*i2[1]};
default:
if(i1[0] == 0){
return new int[]{99999, -1};
}
return new int[]{i2[0]*i1[1], i1[0]*i2[1]};
}
}
}
分成两类,一类是只有一个数与另一个数运算(helper函数完成),如(1+2)*3+4,1与2再与3再与4,是一个一个数运算,另一类是有两个数运算(helper2函数完成),如(1+2)*(3-4),1与2,3与4是一个数与一个数运算,它们之间是两个数与两个数运算,对两个数a, b,可能的操作有6种a+b,a-b,a*b,a/b,b-a,b/a,使用helper递归,先内层运算后外层运算,可以包括所有的第一类情况,第二类情况只有一种,先一一运算,再两两运算,helper2函数完成
缺点:按部就班,分类运算,没用什么特别的算法,代码长,效率低,但简单易懂,是那种不懂算法的人也能看明白的一般方法
下面再看一下其它人的优秀的算法
class Solution {
public boolean judgePoint24(int[] nums) {
double[] nums_2 = new double[nums.length];
for (int i = 0; i < nums.length; i++) {
nums_2[i] = nums[i];
}
return dfs(nums_2);
}
private boolean dfs(double[] nums_2) {
if (nums_2.length == 1) {
return Math.abs(nums_2[0] - 24.0) < 0.001;
}
for (int i = 0; i < nums_2.length; i++) {
for (int j = i + 1; j < nums_2.length; j++) {
double[] nums_3 = new double[nums_2.length - 1];
for (int k = 0, index = 0; k < nums_2.length; k++) {
if (k != i && k != j) {
nums_3[index++] = nums_2[k];
}
}
for (double r : compute(nums_2[i], nums_2[j])) {
nums_3[nums_3.length - 1] = r;
if (dfs(nums_3)) {
return true;
}
}
}
}
return false;
}
private double[] compute(double i, double j) {
return new double[]{i + j, i - j, j - i, i * j, i / j, j / i};
}
}
这其实也是列举出所有的可能情况,先两两数字运算,结果作为另一个数字,数字个数减1,数字个数减到1(减3次)时判断是否为24,使用double代替int,当double数值与24绝对值相差很小时(小于0.001),那么认为就是24,代码简洁,简短
其实像第一种写100多行的写法90%以上都是有问题的,leetcode上的题目,肯定是有对应的比较优秀的解决方法的,代码写得过长,不是代码水平不行,就是对问题的理解不够深入,如果你代码水平不行,或者用时过长,代码过长,可以看看别人的优秀的解法,学习别人的代码与解法
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论