[LeetCode] 964. Least Operators to Express Number

[grandyang]

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:

1. The division operator (/) returns rational numbers.
2. There are no parentheses placed anywhere.
3. We use the usual order of operations: multiplication and division happens before addition and subtraction.
4. 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 同步地址:

#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 题目讲解汇总(持续更新中...)【】