Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream

1. The subject

You have four cards with numbers one through nine. You need to decide if you can get 24 from *, /, +, -, (,).

Input: [4, 1, 8, 7] Output: True Description: (8-4) * (7-1) = 24 Example 2: Input: [1, 2, 1, 2] Output: FalseCopy the code

Note: 1) The division operator/represents real division, not integer division. For example, 4 / (1-2/3) = 12. So the result is a floating-point number, and the numbers stored in the list are all floating-point numbers. The accuracy error should be considered in determining whether the result is equal to 24. In this case, the error less than 10^(-6) is considered equal.) 2) Each operator operates on two numbers. In particular, we cannot use – as the unary operator. For example, the expression -1-1-1-1 is not allowed when [1, 1, 1, 1] is used as input. 3) You can’t connect numbers. For example, when the input is [1, 2, 1, 2], 12 + 12 cannot be written.

2.

In 24-point games, A42∗4∗A32∗4∗A22∗4=9126A^2_4 * 4 * A^2_3 * 4 * A^2_2 * 4= 9126A42∗4∗A32∗4∗A22∗4=9126, The simplest way to do this is by enumerating all the numbers in the list that satisfy the result of the operation 24.

Then in the remaining 3 numbers in order to choose 2 numbers, a total of 3×2=6 options, and choose one of the four operations, with the result of the two numbers selected to replace the results, the remaining 2 numbers. Finally, two numbers are left, in two different orders, and one of the four operations is chosen. So there are 12×4×6×4×2×4= 9,216 different possibilities.Copy the code

You can go through all the different possibilities by backtracking. Specifically, a list is used to store all the current numbers. Each time two numbers are selected from the list, and then an operation is selected to replace the selected two numbers with the calculated results, so that the number in the list is reduced by one. Repeat the process until there is only one number left in the list, which is the result of one possibility. If the result is 24, then you can do the operation to get 24. If none of the possibilities is equal to 24, then you can’t do the operation to get 24.

Result = [] def backtrack(path, select list): if the end condition is met: result.add(path) return for select in select list: Backtrack to this problem, paths represent all numbers (e.g. [1, 2, 1, 2]), a list of four operators (e.g., a list of four operators), and an end condition (e.g., all four paths/numbers are selected and the final result is 24). Finally, the calculation is loaded into the result array.Copy the code

So in terms of how to do backtracking,

It is complicated to determine whether four numbers can lead to 24, but it is fairly easy to determine whether two numbers can lead to 24 through four operations, so the key to solving this problem is how to turn four numbers into three numbers, and then two numbers. 4->3: Take any two of the four numbers (6 possible) and perform four operations to get five values and combine them with the remaining two numbers to get three numbers; 3->2: Take any two of the three numbers (3 possibilities) and perform four operations. The five values obtained are combined with the remaining number to get two numbers. 2-> Result: Perform four operations on two numbers, return true if 24 can be obtained.

Here is a diagram of the backtracking process:

class Solution { public: static constexpr int TARGET = 24; static constexpr double EPSILON = 1e-6; static constexpr int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3; bool judgePoint24(vector<int> &nums) { vector<double> l; for (const int &num : nums) { l.emplace_back(static_cast<double>(num)); } return solve(l); } bool solve(vector<double> &l) { if (l.size() == 0) { return false; } if (l.size() == 1) { return fabs(l[0] - TARGET) < EPSILON; } int size = l.size(); for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (i ! = j) { vector<double> list2 = vector<double>(); // select list for (int k = 0; k < size; k++) { if (k ! = i && k ! = j) { list2.emplace_back(l[k]); } } // backtrack for (int k = 0; k < 4; k++) { if (k < 2 && i > j) { continue; } if (k == ADD) { list2.emplace_back(l[i] + l[j]); } else if (k == MULTIPLY) { list2.emplace_back(l[i] * l[j]); } else if (k == SUBTRACT) { list2.emplace_back(l[i] - l[j]); } else if (k == DIVIDE) { if (fabs(l[j]) < EPSILON) { continue; } list2.emplace_back(l[i] / l[j]); If (solve(list2)) {return true; } // Unselect list2.pop_back(); } } } } return false; }};Copy the code

  • Time complexity: O(1). There are 9216 possibilities, for each of which the time complexity of each operation is O(1), so the total time complexity is O(1).

  • Space complexity: O(1). The spatial complexity depends on the number of layers of recursive calls and the list of intermediate states. Since there are four numbers, the number of layers of recursive calls is at most four, and the list of intermediate states contains at most four elements, so the spatial complexity is constant.

Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream