[Swift Weekly Contest 116]LeetCode964. 表示数字的最少运算符
Given a single positive integer? When writing such an expression,we adhere to the following conventions:
We would like to write an expression with the least number of operators such that the expression equals the given? Example 1: Input: x = 3,target = 19 Output: 5 Explanation: 3 * 3 + 3 * 3 + 3 / 3. The expression contains 5 operations.
Example 2: Input: x = 5,target = 501 Output: 8 Explanation: 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5. The expression contains 8 operations.
Example 3: Input: x = 100,target = 100000000 Output: 3 Explanation: 100 * 100 * 100 * 100. The expression contains 3 operations.
Note:
给定一个正整数? 在写这样的表达式时,我们需要遵守下面的惯例:
我们希望编写一个能使表达式等于给定的目标值? 示例 1: 输入:x = 3,target = 19 输出:5 解释:3 * 3 + 3 * 3 + 3 / 3 。表达式包含 5 个运算符。 示例 2: 输入:x = 5,target = 501 输出:8 解释:5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5 。表达式包含 8 个运算符。 示例 3: 输入:x = 100,target = 100000000 输出:3 解释:100 * 100 * 100 * 100 。表达式包含 3 个运算符。 提示:
100ms 1 class Solution { 2 var x:Int = 0 3 var best:Int = 0 4 func leastOpsExpressTarget(_ x: Int,_ target: Int) -> Int { 5 var target = target 6 self.x = x 7 var list:[Int] = [Int]() 8 while(target != 0) 9 { 10 list.append(target % x) 11 target /= x 12 } 13 self.best = Int.max 14 dfs(list,0,0) 15 return best - 1 16 } 17 18 func dfs(_ list:[Int],_ k:Int,_ add:Int,_ count:Int) 19 { 20 var add = add 21 if count >= best 22 { 23 return 24 } 25 if add == 0 && k >= list.count 26 { 27 best = min(best,count) 28 return 29 } 30 31 if k < list.count 32 { 33 add += list[k] 34 } 35 var cost:Int = k == 0 ? 2 : k 36 var cur:Int = add % x 37 add /= x 38 dfs(list,k + 1,add,count + cost * cur) 39 if cur != 0 && k <= list.count + 2 40 { 41 dfs(list,1,count + cost * (x - cur)) 42 } 43 } 44 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |