diff options
author | Jack Sangdahl <[email protected]> | 2025-08-17 18:30:08 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-08-17 18:30:08 -0600 |
commit | 6c5db50fce3a14a2205e7d927c8adaf829aa6280 (patch) | |
tree | f768527878f85565a3670dbe4f85082255edf6e7 | |
parent | 5d449e06b0ccf99ad3d10e2ed2c37e6e902bab1c (diff) | |
download | leetcode-6c5db50fce3a14a2205e7d927c8adaf829aa6280.tar.gz leetcode-6c5db50fce3a14a2205e7d927c8adaf829aa6280.zip |
679. 24 game
-rw-r--r-- | 24_game.c | 133 |
1 files changed, 44 insertions, 89 deletions
@@ -15,100 +15,55 @@ * 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; -} +#define EPSILON 0.00000001 -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; - } - } - } - } - } +bool backtrack(double *cards, int cardsSize) { + if (cardsSize == 1) + return fabs(cards[0] - 24) < EPSILON; + double *new = NULL; + for (int i = 0; i + 1 < cardsSize; i++) + for (int j = 0; j < cardsSize; j++) { + int n = cardsSize - 1, newSize = 0; + new = (double *)calloc(sizeof(double), n); + for (int k = 0; k < cardsSize; k++) + if (k != i && k != j) + new[newSize++] = cards[k]; + new[newSize++] = cards[i] + cards[j]; + if (backtrack(new, newSize)) + return true; + newSize--; + new[newSize++] = cards[i] - cards[j]; + if (backtrack(new, newSize)) + return true; + newSize--; + new[newSize++] = cards[j] - cards[i]; + if (backtrack(new, newSize)) + return true; + newSize--; + new[newSize++] = cards[i] * cards[j]; + if (backtrack(new, newSize)) + return true; + newSize--; + new[newSize++] = cards[i] / cards[j]; + if (backtrack(new, newSize)) + return true; + newSize--; + new[newSize++] = cards[j] / cards[i]; + if (backtrack(new, newSize)) + return true; } + if (new) + free(new); return false; } +bool judgePoint24(int *cards, int cardsSize) { + double *newCards = (double *)calloc(sizeof(double), cardsSize); + bool ans = backtrack(newCards, cardsSize); + free(newCards); + return ans; +} + int main() { int c1[] = {4, 1, 8, 7}, c2[] = {1, 2, 1, 2}; printf("%d\n", judgePoint24(c1, ARRAY_SIZE(c1))); // expect: 1 |