[LeetCode] 964. Least Operators to Express Number 表示数字的最少运算符

刷尽天下 2020-12-09

237

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 operators 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通过一些运算组成另一个正整数 target，这里的x可以不限次数使用，运算只包括加减乘除，不带括号，但需要满足乘除优先的基本规律。并且这里的除法是整数除法，减号不能当作负数符号使用，让我们求要组成 target 的最少的运算符的使用个数。虽然题目很长不好理解，但是通过例子还是不难理解题意的，难就难在如何解题。博主看了一会儿，发现没思路就直接放弃了，直奔论坛上找解法。这里直接参考 donggua_fu
大神的解法吧，首先处理 edge cases，当 x 等于 target 的话，不用加任何运算符，返回0即可。若 x 大于 target，比如 x=5，target=3，我们其实可以迅速的求出运算符的个数，因为5比3大，要凑3就只能先变成1，这里就有两种变法，一种是全部都变成1，然后来凑3，即 5/5+5/5+5/5
，这时的运算符个数是 target*2-1
，因为加号的个数总是比除号少一个。另一种凑法就是 5-5/5-5/5
，这时候的运算符个数是 (x-target)*2
，此时的加号和除号的个数相同，均为x和 target 的差值。

接下来就要处理 x 小于 target 的情况了，此时由于不知道x到底比 target 小多少，若差距太大的话，肯定不能用加号，所以应该先用乘号来让x变大，直到刚好大于等于 target 停止，并每次增加次数 cnt。若此时 sum 正好等于 target，太幸运了，直接返回 cnt。但通常情况下 sum 会大于 target，此时 sum-target
的差值就需要另行计算了。这里差值跟 target 的大小关系又要分为两种情况来讨论，当 sum-target<target
时，比如 x=5，sum=25，target=15，则 sum - target=10，就是说现在已经乘到了 25，但需要再减去 10，这个差值 10 可以再次调用原函数来计算，此时新的 target 代入 10 即可，记得返回值要加上 cnt。当然之后还是要再计算一下另一种凑的方法，由于 sum 超过了 target，所以回退一个x，变成 sum/x
，此时小于 target，那么它们的差值 target-(sum/x)
就可以通过再次调用函数来计算，注意这里加上 cnt 之后还要减去1，因为回退了一个x，少了一个乘号。最终二者的较小值即为所求，记得要加上个1，以为多加了个运算符，参见代码如下：

class Solution {
public:
    int leastOpsExpressTarget(int x, int target) {
        if (x == target) return 0;
        if (x > target) {
            return min(target * 2 - 1, (x - target) * 2);
        }
        long sum = x;
        int cnt = 0;
        while (sum < target) {
            sum *= x;
            ++cnt;
        }
        if (sum == target) return cnt;
        int res1 = INT_MAX, res2 = INT_MAX;
        if (sum - target < target) {
            res1 = leastOpsExpressTarget(x, sum - target) + cnt;
        }
        res2 = leastOpsExpressTarget(x, target - (sum / x)) + cnt - 1;
        return min(res1, res2) + 1;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/964

参考资料：

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

https://leetcode.com/problems/least-operators-to-express-number/discuss/208445/c%2B%2B-recursive-easy-to-understand

https://leetcode.com/problems/least-operators-to-express-number/discuss/208349/JavaC%2B%2BPython-O(logY)-Time-and-O(1)-Space

LeetCode All in One 题目讲解汇总(持续更新中...)

数据库

文章转载自刷尽天下，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

[LeetCode] 964. Least Operators to Express Number 表示数字的最少运算符

评论