LeetCode 964: Least Operators to Express Number

发表于 | | 阅读次数:
字数统计: 982 | 阅读时长 ≈ 4

题目链接

https://leetcode.com/problems/least-operators-to-express-number/

题意

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

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

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

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

题目类型

动态规划

题目分析

一道有点像数位DP的动态规划题，但是总体来说强度还行。

因为操作的正整数只有一个，所以拿到该题的第一反应就是把target按求x进制的方式拆分为多个x的幂之和。

首先来设想假设没有减号(-)的情况，不难发现如果不是为了得到1使用除号都只能增加运算符却对结果没有帮助。同时，表达式中一定有一个正数。把target按x的幂级数分解后，需要的运算符数就是 (达到该幂级数所需运算符数)*(该位上的数字) 之和。

举个例子:
x = 3, target = 19
按位分解后得到 [1, 0, 2] (从低到高), $19=1+0 \ast 3+2 \ast 3^{2}$
需要的运算符数为 2 + 2 * 2 - 1 = 5
即为 + 3 / 3 + 3 * 3 + 3 * 3，去掉最首的’+’号答案-1

接下来考虑表达式中存在减号(-)的情况。存在减号时，假设某位的数字为t，得到数字t可以有两种方式：

  1. 加上t个该级数的数字
  2. 由高位减去该级数的数字，减去的个数为(x-t)个

定义f数组值为需要的最小运算符数，a[i]为i位上的数字，bit(i)为得到i位的幂级数所需的运算符数字(含开头的符号)，f[i][0]为在第i位使用第一种方式，f[i][1]为第二种方式，不难推出转移方程为：
$f[i][0]=min(f[i - 1][0], f[i - 1][1]) + bit(i) \ast a[i]$
$\begin{split}
f[i][1]=&min(f[i - 1][0] + (x - a[i]) * bit(i) + bit(i + 1), f[i - 1][1] + \\ &(x - a[i] - 1) \ast bit(i) + bit(i + 1) - bit(i))
\end{split}$

f[i][0]的转移方程不难理解，主要说一下f[i][1]:

假设低位是没被减的，那么该位就是 高位 - 低位 的运算符之和。

假设低位是被减的，那么该位转移时要将低位所使用的被减数换成高一位的被减数，也即是bit(i + 1) - bit(i)部分。

同时因为低位已经减掉了一部分，所以这一位是从x-1开始的，也即是(x - a[i] - 1)的来历。

时间复杂度

$O(N ^ {3})$

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int get_bit(int i) {
        i--;
        if (i == 0)
            return 2;
        return i;
    }
    int leastOpsExpressTarget(int x, int target) {
        int t = target;
        vector<int>a, b;
        while (t > 0) {
            b.push_back(t % x);
            t /= x;
        }
        a.push_back(0);
        for (int i : b)
            a.push_back(i);
        int f[30][2];
        memset(f, 0, sizeof(f));
        for (int i = 1; i < a.size(); i++) {
            f[i][0] = min(f[i - 1][0], f[i - 1][1]) + get_bit(i) * a[i];
            f[i][1] = f[i - 1][0] + (x - a[i]) * get_bit(i) + get_bit(i + 1);
            if (i > 1)
                f[i][1] = min(f[i][1], f[i - 1][1] + (x - a[i] - 1) * get_bit(i) + get_bit(i + 1) - get_bit(i));
        }
        return min(f[a.size() - 1][1], f[a.size() - 1][0]) - 1;
    }
};
0%