[Swift]LeetCode679. 24点游戏 | 24 Game

发布时间：2020-12-14 05:02:58 所属栏目：百科来源：网络整理

导读：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: Input: [4,1,8,7]Output: TrueExplanation: (8-4) * (7-1) = 24 Example

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:

Input: [4,1,8,7]
Output: True
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1,2,2]
Output: False?

Note:

The division operator?/?represents real division,not integer division. For example,4 / (1 - 2/3) = 12.
Every operation done is between two numbers. In particular,we cannot use?-?as a unary operator. For example,with?[1,1]?as input,the expression?-1 - 1 - 1 - 1?is not allowed.
You cannot concatenate numbers together. For example,if the input is?[1,2],we cannot write this as 12 + 12.

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过?*，/，+，-，(，)?的运算得到 24。

示例 1:

输入: [4,7]
输出: True
解释: (8-4) * (7-1) = 24

示例 2:

输入: [1,2]
输出: False

注意:

除法运算符?/?表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
每个运算符对两个数进行运算。特别是我们不能用?-?作为一元运算符。例如，[1,1]?作为输入时，表达式?-1 - 1 - 1 - 1?是不允许的。
你不能将数字连接在一起。例如，输入为?[1,2]?时，不能写成 12 + 12 。

16ms

 1 class Solution {
 2     func oneOperation(_ nums: [Double],_ i: Int,_ j: Int, 3                       _ op: (Double,Double)->Double?) -> [Double]? {
 4         var arr = [Double]()
 5         for k in 0..<nums.count {
 6             if k != i && k != j {
 7                 arr.append(nums[k])
 8             } 
 9         }
10         if let num = op(nums[i],nums[j]) {
11             arr.append(num)
12             return arr
13         } else {
14             return nil
15         }
16     }
17     func judgePoint24Internal(_ nums: [Double]) -> Bool {
18         if nums.count == 2 {
19             return nums[0]*nums[1] == 24 || nums[0]+nums[1] == 24 
20                 || nums[0] - nums[1] == 24 || nums[1] - nums[0] == 24
21                 || (nums[0] != 0 && 24.0-0.00001 < nums[1]/nums[0] && nums[1]/nums[0] < 24.0 + 0.0000001) 
22                 || (nums[1] != 0 && fabs(nums[0]/nums[1]-24.0) < 0.00001)
23         }
24              
25         for i in 0..<nums.count-1 {
26             for j in i+1..<nums.count {
27                 var arr = oneOperation(nums,i,j,{$0+$1})
28                 if judgePoint24Internal(arr!) == true {
29                     return true
30                 }
31                 
32                 arr = oneOperation(nums,{$0*$1})
33                 if judgePoint24Internal(arr!) == true {
34                     return true
35                 }
36                 
37                 arr = oneOperation(nums,{$0-$1})
38                 if judgePoint24Internal(arr!) == true {
39                     return true
40                 }
41                 
42                 arr = oneOperation(nums,{$1 != 0 ? $0/$1 : nil})
43                 if let arr = arr,judgePoint24Internal(arr) == true {
44                     return true
45                 }
46                 arr = oneOperation(nums,{$1-$0})
47                 if judgePoint24Internal(arr!) == true {
48                     return true
49                 }
50                 
51                 arr = oneOperation(nums,{$0 != 0 ? $1/$0 : nil})
52                 if let arr = arr,judgePoint24Internal(arr) == true {
53                     return true
54                 }
55             }
56         }
57         return false
58     }
59     
60     func judgePoint24(_ nums: [Int]) -> Bool {
61         return judgePoint24Internal(nums.map{Double($0)})
62     }
63 }

40ms

 1 class Solution {
 2     func judgePoint24(_ nums: [Int]) -> Bool {
 3         return solve(nums.map { Double($0) })
 4     }
 5     
 6     private func solve(_ nums: [Double]) -> Bool {
 7         guard nums.count > 1 else {
 8             return abs(nums[0] - 24.0) < 1e-6
 9         }
10         
11         for i in 0..<nums.count {
12             for j in 0..<nums.count {
13                 guard i != j else {
14                     continue
15                 }
16                 
17                 var newNums = [Double]()
18                 for k in 0..<nums.count where k != i && k != j {
19                     newNums.append(nums[k])
20                 }
21                 
22                 for k in 0..<4 {
23                     switch k {
24                     case 0:
25                         newNums.append(nums[i] + nums[j])
26                     case 1:
27                         newNums.append(nums[i] - nums[j])
28                     case 2:
29                         newNums.append(nums[i] * nums[j])
30                     case 3:
31                         if nums[j] != 0.0 {
32                             newNums.append(nums[i] / nums[j])
33                         } else {
34                             continue
35                         }
36                     default:
37                         continue
38                     }
39                     if solve(newNums) {
40                         return true
41                     }
42                     newNums.removeLast()
43                 }
44             }
45         }
46         return false
47     }
48 }

44ms

 1 class Solution {    
 2     private let esp: Double = 0.001
 3     
 4     func judgePoint24(_ nums: [Int]) -> Bool {
 5         var nums = nums.map { return Double($0) }
 6         return dfs(nums)
 7     }
 8     
 9     private func dfs(_ nums: [Double]) -> Bool {
10         if nums.count == 1 {
11             if abs(nums.first! - 24) <= esp {
12                 return true
13             } else {
14                 return false
15             }
16         }
17         
18         for i in 0 ..< nums.count {
19             for j in i + 1 ..< nums.count {
20                 var next: [Double] = []
21                 
22                 for k in 0 ..< nums.count {
23                     if k != i && k != j {
24                         next.append(nums[k])
25                     }
26                 }
27                 
28                 let p1 = nums[i]
29                 let p2 = nums[j]
30                 let combines = [p1 + p2,p1 - p2,p2 - p1,p1 * p2,p1 / p2,p2 / p1]
31                 
32                 for c in combines {
33                     next.append(c)
34                     if dfs(next) {
35                         return true
36                     }
37                     next.removeLast()
38                 }
39             }
40         }        
41         return false
42     }
43 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!