679 24 Game

679. 24 Game​
1. Question
You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through*,/,+,-,(,)to get the value of 24.
Example 1:
1
Input: [4, 1, 8, 7]
2
​
3
Output: True
4
​
5
Explanation: (8-4) * (7-1) = 24
Copied!
Example 2:
1
Input: [1, 2, 1, 2]
2
​
3
Output: False
Copied!
Note:
1.The division operator/represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
2.Every operation done is between two numbers. In particular, we cannot use-as a unary operator. For example, with[1, 1, 1, 1]as input, the expression -1 - 1 - 1 - 1is not allowed.
3.You cannot concatenate numbers together. For example, if the input is[1, 2, 1, 2], we cannot write this as 12 + 12.
2. Implementation
(1) Backtracking
1
class Solution {
2
    final double epsilon = 0.0001;
3
    public boolean judgePoint24(int[] nums) {
4
        if (nums == null || nums.length < 4) {
5
            return false;
6
        }
7
​
8
        List<Double> list = new ArrayList();
9
        for (int num : nums) {
10
            list.add((double) num);
11
        }
12
​
13
        return getPoint24(list);
14
    }
15
​
16
    public boolean getPoint24(List<Double> nums) {
17
        if (nums.size() == 0) {
18
            return false;
19
        }
20
​
21
        if (nums.size() == 1) {
22
            if (Math.abs(nums.get(0) - 24) < epsilon) {
23
                return true;
24
            }
25
        }
26
​
27
        for (int i = 1; i < nums.size(); i++) {
28
            for (int j = 0; j < i; j++) {
29
                double num1 = nums.get(i);
30
                double num2 = nums.get(j);
31
​
32
                if (num1 == 0 || num2 == 0) {
33
                    continue;
34
                }
35
​
36
                // i is greater than j, so removing element at i won't effect the position of nums.get(j)
37
                nums.remove(i);
38
                nums.remove(j);
39
​
40
                for (double nextNum : compute(num1, num2)) {
41
                    nums.add(nextNum);
42
​
43
                    if (getPoint24(nums)) {
44
                        return true;
45
                    }
46
                    nums.remove(nums.size() - 1);
47
                }
48
​
49
                nums.add(j, num2);
50
                nums.add(i, num1);
51
            }
52
        }
53
        return false;
54
    }
55
​
56
    public double[] compute(double num1, double num2) {
57
        return new double[] {num1 + num2, num1 - num2, num2 - num1, num1 * num2, num1 / num2, num2 / num1};
58
    }
59
}
Copied!
3. Time & Space Complexity
Backtracking: 时间复杂度O(1) ? 空间复杂度O(1)?

526 Beautiful Arrangement

691 Stickers to Spell Word

Last modified 2yr ago

Copy link

Contents

679. 24 Game

1. Question

2. Implementation

3. Time & Space Complexity

679. 24 Game​

1. Question

2. Implementation

3. Time & Space Complexity

679. 24 Game