0964：表示数字的最少运算符（2594 分）

力扣第 116 场周赛第 4 题

题目

给定一个正整数 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 * 108

分析

• 将连乘的 x 和 x/x 看作 1 块，显然值就是 x^i
  • 为了方便，表达式第一个 x 前看作有个加号
  • 那么对于 x^i，要用到 i 个符号，（1 特殊，要用 2 个）
• 问题转为用这些块拼出 target，符号最少
• 首先算出 r=target%x
  • 要么用 r 个 1，转为求 t=target-r
  • 要么用 x-r 个 1，转为求 t=target+x-r
• 剩下的不需要用 1 了，继续算 r=t//x%x，讨论要用多少个 x
  • 注意只需要 t//x 的值了，所以上一步可以直接传 t//x
• 因此令 dfs(t,i) 代表 t*x^i 用 >=x^i 的块拼的最少数，即可递归
• 注意终止条件，当 x^i>=target*x 时，用 x^i 显然是浪费的，无需考虑

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        @cache
        def dfs(t,i):
            if t==0:
                return 0
            if i>ma:
                return inf
            w = i if i>0 else 2
            q,r = divmod(t,x)
            return min(r*w+dfs(q,i+1),(x-r)*w+dfs(q+1,i+1))
        ma = ceil(log(target,x))
        return dfs(target,0)-1

0 ms