leetcode 964

问题

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:

1
2
3
Input: x = 3, target = 19
Output: 5
Explanation: 3 * 3 + 3 * 3 + 3 / 3.  The expression contains 5 operations.

Example 2:

1
2
3
Input: x = 5, target = 501
Output: 8
Explanation: 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5.  The expression contains 8 operations.

Example 3:

1
2
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

分析

代码

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
class Solution {
public:
    int leastOpsExpressTarget(int x, int target) {
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        unordered_set<int> v;
        pq.emplace(0, target);
        while (!pq.empty()) {
            auto [c, t] = pq.top();
            pq.pop();
            if (t == 0) return c-1;
            if (v.find(t) != v.end())
                continue;
            v.insert(t);
            
            int k = log(t)/log(x);
            int l = t - pow(x, k);
            if (v.find(l) == v.end())
                pq.emplace(c+(k==0? 2: k), l);
            int r = (long long)pow(x, k+1)-t;
            if (v.find(r) == v.end())
                pq.emplace(c + k + 1, r);
        }
        return -1;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    unordered_map<int,int> mp;
    int leastOpsExpressTarget(int x, int target) {
        return dp(x, target);
    }
    int dp(int x, int t) {
        if (t == 0) return 0;
        if (t < x) return min(2*t-1, 2*(x-t));
        if (mp.find(t) != mp.end())
            return mp[t];
        
        int k = log(t)/log(x);
        long long p = pow(x, k);
        if (t == p)
            return mp[t] = k-1;
        int ans = dp(x, t-p) + k;
        long long left = p*x-t;
        if (left < t)
            ans = min(ans, dp(x, left) + k + 1);
        return mp[t] = ans;
    }
};

代码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
// 没有ac的代码，要看看为什么  125 / 159 test cases passed.
class Solution {
public:
    unordered_map<int,int> mp;
    int leastOpsExpressTarget(int x, int target) {
        mp.clear();
        return dp(x, target);
    }
    int dp(int x, int t) {
        if (mp.find(t) != mp.end())
            return mp[t];
        mp[t] = 0x3f3f3f3f;
        if (x == t) return mp[t] = 0;
        if (t == 1) return 1;
        if (t < x) {
             return mp[t] = min(t*2-1, (x-t)*2);
        }
        int k = log(t) / log(x);
        long long p = pow(x, k);
        if (p == t) return mp[t] = k-1;
        return mp[t] = min(k + dp(x, t-p),
                  k+1+dp(x, p*x - t));
    }
};