[Swift Weekly Contest 116]LeetCode964. 表示数字的最少运算符 | Least Operators to Express Number

概述Given a single positive integer x, we will write an expression of the form x (op1) x (op2) x (op3) x ... where each operator op1, op2, etc. is either addition, subtraction, multiplication, or division

Given a single positive integer x,we will write an Expression of the form x (op1) x (op2) x (op3) x ... where each operator op1, op2,etc. is either addition,subtraction,multiplication,or division (+, -, *,or /).  For example,with x = 3,we might write 3 * 3 / 3 + 3 - 3 which is a value of 3.

When writing such an Expression,we adhere to the following conventions:

The division operator (/) returns rational numbers. There are no parentheses placed anywhere. We use the usual order of operations: multiplication and division happens before addition and subtraction. It‘s not allowed to use the unary negation operator (-).  For example,"x - x" is a valID Expression as it only uses subtraction,but "-x + x" is not because it uses negation.

We would like to write an Expression with the least number of operators such that the Expression equals the given target.  Return the least number of Expressions used.

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:

2 <= x <= 100 1 <= target <= 2 * 10^8

给定一个正整数 x，我们将会写出一个形如 x (op1) x (op2) x (op3) x ... 的表达式，其中每个运算符 op1，op2，… 可以是加、减、乘、除（+，-，*，或是 /）之一。例如，对于 x = 3，我们可以写出表达式 3 * 3 / 3 + 3 - 3，该式的值为 3 。

在写这样的表达式时，我们需要遵守下面的惯例：

除运算符（/）返回有理数。 任何地方都没有括号。 我们使用通常的 *** 作顺序：乘法和除法发生在加法和减法之前。 不允许使用一元否定运算符（-）。例如，“x - x” 是一个有效的表达式，因为它只使用减法，但是 “-x + x” 不是，因为它使用了否定运算符。 

我们希望编写一个能使表达式等于给定的目标值 target 且运算符最少的表达式。返回所用运算符的最少数量。

示例 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 个运算符。

提示：

2 <= x <= 100 1 <= target <= 2 * 10^8

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 /= x12         }13         self.best = Int.max14         dfs(List,0,0)15         return best - 116     }17     18     func dfs(_ List:[Int],_ k:Int,_ add:Int,_ count:Int)19     {20         var add = add21         if count >= best22         {23             return24         }25         if add == 0 && k >= List.count26         {27             best = min(best,count)28             return29         }30         31         if k < List.count32         {33             add += List[k]34         }35         var cost:Int = k == 0 ? 2 : k36         var cur:Int = add % x37         add /= x38         dfs(List,k + 1,add,count + cost * cur)39         if cur != 0 && k <= List.count + 240         {41             dfs(List,1,count + cost * (x - cur))42         }43     }44 }

@H_233_404@ 总结

以上是内存溢出为你收集整理的[Swift Weekly Contest 116]LeetCode964. 表示数字的最少运算符 | Least Operators to Express Number全部内容，希望文章能够帮你解决[Swift Weekly Contest 116]LeetCode964. 表示数字的最少运算符 | Least Operators to Express Number所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。