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

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）➤GitHub地址：https://github.com/strengthen/LeetCode➤原文地址：https://www.cnblogs.com/strengthen/p/10498335.html ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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, 1, 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, 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, 1, 2], we cannot write this as 12 + 12.

---

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

示例 1:

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

示例 2:

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

注意:

除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。你不能将数字连接在一起。例如，输入为 [1, 2, 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, i, j, {$0*$1}) 33 if judgePoint24Internal(arr!) == true { 34 return true 35 } 36 37 arr = oneOperation(nums, i, j, {$0-$1}) 38 if judgePoint24Internal(arr!) == true { 39 return true 40 } 41 42 arr = oneOperation(nums, i, j, {$1 != 0 ? $0/$1 : nil}) 43 if let arr = arr, judgePoint24Internal(arr) == true { 44 return true 45 } 46 arr = oneOperation(nums, i, j, {$1-$0}) 47 if judgePoint24Internal(arr!) == true { 48 return true 49 } 50 51 arr = oneOperation(nums, i, j, {$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 }

 

转载于:https://www.cnblogs.com/strengthen/p/10498335.html

相关资源：ios初学者代码24个专题