TNotes.leetcode

Appearance

⏰0964. 表示数字的最少运算符【困难】

0964. 表示数字的最少运算符【困难】 ​

1. 📝 题目描述 ​

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

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

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

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

示例 1：

txt
输入：x = 3, target = 19
输出：5

解释：
3 * 3 + 3 * 3 + 3 / 3。
表达式包含 5 个运算符。

示例 2：

txt
输入：x = 5, target = 501
输出：8

解释：
5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5。
表达式包含 8 个运算符。

示例 3：

txt
输入：x = 100, target = 100000000
输出：3

解释：
100 * 100 * 100 * 100。
表达式包含 3 个运算符。

提示：

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

2. 🎯 s.1 - 数位 DP ​

js
/**
 * @param {number} x
 * @param {number} target
 * @return {number}
 */
var leastOpsExpressTarget = function (x, target) {
  // cost(k) = 一个 x^k 项的代价（含前导连接符）
  // k=0: x/x 需要 2 个符号（/ 和前导 +/-）
  // k>=1: x^k 需要 k 个符号（k-1 个 * 和 1 个前导 +/-）
  const cost = (k) => (k === 0 ? 2 : k)

  // pos: 正向构建当前值的最小代价
  // neg: 借位构建当前值的最小代价（需要向高位借一个 x^(k+1)）
  let pos = 0,
    neg = 0
  let k = 0

  while (target > 0) {
    const d = target % x
    target = Math.floor(target / x)

    if (k === 0) {
      // 第一位
      pos = d * cost(0) // 用 d 个 x/x
      neg = (x - d) * cost(0) // 借位：用 (x-d) 个 x/x 表示负项
    } else {
      const c = cost(k)
      const newPos = Math.min(
        pos + d * c, // 不借位：前面正向 + d 个 x^k
        neg + (d + 1) * c, // 前面借位：需要 d+1 个 x^k 来补偿
      )
      const newNeg = Math.min(
        pos + (x - d) * c, // 开始借位：正向 + (x-d) 个负项 x^k
        neg + (x - d - 1) * c, // 连续借位：已借位 + (x-d-1) 个负项
      )
      pos = newPos
      neg = newNeg
    }
    k++
  }

  // 如果有借位，需要补上最高位的 x^k
  return Math.min(pos, neg + cost(k)) - 1 // -1 去掉第一项的前导连接符
}
  • 时间复杂度：O(logx⁡target)，将 target 转为 x 进制逐位处理
  • 空间复杂度：O(1)，只使用常数额外空间

算法思路：

  • 将 target 看作 x 进制数，逐位处理，每位系数 d 满足 0≤d<x
  • 代价函数：x0 需要 2 个运算符（x/x），xk (k≥1) 需要 k 个运算符（k-1 个乘法 + 1 个加减法）
  • 状态定义：pos 表示正向构建的最小代价，neg 表示借位构建的最小代价（向高位借一个 xk+1）
  • 状态转移：每位有两种选择——直接用 d 个 xk 或借位用 (x-d) 个 xk
  • 最终答案取 min(pos, neg + cost(k)) - 1，减 1 是去掉首项前的运算符