1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
// 679. 24 Game
#include "leetcode.h"
/*
* given an integer array 'cards' of length 4. you have four cards, each
* containing a number in the range '[1,9]'. you should arrange the numbers on
* these cards in a mathematical expression using the operators '[+,-,*,/]' and
* the parenthesis '(' and ')' to get value 24. you are restricted to the
* following rules:
* - the division operation represents real division, not integer division
* - every operation done is between two numbers. in particular, we cannot use
* '-' as a unary operator
* - you cannot concatenate numbers together
* return true if you can get such expression that evaluates to 24 and false
* otherwise.
*/
float calculate(float n1, float n2, char operand) {
switch (operand) {
case '+':
return n1 + n2;
case '-':
return n1 - n2;
case '*':
return n1 * n2;
case '/':
if (!n2)
return -1;
return n1 / n2;
}
return 0;
}
bool judgePoint24(int *cards, int cardsSize) {
int i, j, k, l;
int x, y, z;
int t;
int opersSize = 4;
int sum = 6;
float cal[3];
int sign[3];
float ans;
char oper[4] = {'+', '-', '*', '/'};
for (i = 0; i < cardsSize; i++)
for (j = 0; j < cardsSize; j++) {
if (j == i)
continue;
for (k = 0; k < cardsSize; k++) {
if (k == i || k == j)
continue;
l = sum - (i + j + k);
for (x = 0; x < opersSize; x++) {
sign[0] = 0;
if (x <= 1)
sign[0] = 1;
for (y = 0; y < opersSize; y++) {
sign[1] = 0;
if (y <= 1)
sign[1] = 1;
for (z = 0; z < opersSize; z++) {
sign[2] = 0;
if (z <= 1)
sign[2] = 1;
if ((sign[0] ^ sign[1]) || (sign[0] ^ sign[2]) ||
(sign[1] ^ sign[2])) {
cal[0] = calculate(cards[i], cards[j], oper[x]);
cal[1] = calculate(cal[0], cards[k], oper[y]);
cal[2] = calculate(cal[1], cards[l], oper[z]);
ans = cal[2] > 24 ? cal[2] - 24 : 24 - cal[2];
if (ans < 0.0001)
return true;
cal[0] = calculate(cards[i], cards[j], oper[x]);
cal[2] = calculate(cards[k], cards[l], oper[z]);
cal[1] = calculate(cal[0], cal[2], oper[y]);
ans = cal[1] > 24 ? cal[1] - 24 : 24 - cal[1];
if (ans < 0.0001)
return true;
cal[1] = calculate(cards[j], cards[k], oper[y]);
cal[0] = calculate(cards[i], cal[1], oper[x]);
cal[2] = calculate(cal[0], cards[l], oper[z]);
ans = cal[2] > 24 ? cal[2] - 24 : 24 - cal[2];
if (ans < 0.0001)
return true;
cal[1] = calculate(cards[j], cards[k], oper[y]);
cal[2] = calculate(cal[1], cards[l], oper[z]);
cal[0] = calculate(cards[i], cal[2], oper[x]);
ans = cal[0] > 24 ? cal[0] - 24 : 24 - cal[0];
if (ans < 0.0001)
return true;
cal[2] = calculate(cards[k], cards[l], oper[z]);
cal[1] = calculate(cards[j], cal[2], oper[y]);
cal[0] = calculate(cards[i], cal[1], oper[x]);
ans = cal[0] > 24 ? cal[0] - 24 : 24 - cal[0];
if (ans < 0.0001)
return true;
} else {
cal[0] = calculate(cards[i], cards[j], oper[x]);
cal[1] = calculate(cal[0], cards[k], oper[y]);
cal[2] = calculate(cal[1], cards[l], oper[z]);
ans = cal[2] > 24 ? cal[2] - 24 : 24 - cal[2];
if (ans < 0.0001)
return true;
}
}
}
}
}
}
return false;
}
int main() {
int c1[] = {4, 1, 8, 7}, c2[] = {1, 2, 1, 2};
printf("%d\n", judgePoint24(c1, ARRAY_SIZE(c1))); // expect: 1
printf("%d\n", judgePoint24(c2, ARRAY_SIZE(c2))); // expect: 0
}
|