Leet Code Weekly Contest 288

1. Largest Number After Digit Swaps by Parity

Well, just sort :)

c++

class Solution {
public:
    int largestInteger(int num) {
        string digits = to_string(num);
        for (int i = 0; i < digits.length(); i++) {
            for (int j = i + 1; j < digits.length(); j++) {
                int x = digits[i] - '0', y = digits[j] - '0';
                if (x % 2 == y % 2 && y > x) {
                    swap(digits[i], digits[j]);
                }
            }
        }
        return stoi(digits);
    }
};

2. Minimize Result by Adding Parentheses to Expression

Brute-force is enough.

c++

class Solution {
public:
    string minimizeResult(string expression) {
        int plusPos;
        for (int i = 0; i < expression.size(); i++) {
            if (expression[i] == '+') {
                plusPos = i;
            }
        }
        int ans = INT_MAX;
        string str = "";
        for (int i = 0; i < plusPos; i++) {
            for (int j = plusPos + 1; j < expression.size(); j++) {
                string a = expression.substr(0, i);
                string b = expression.substr(i, plusPos - i);
                string c = expression.substr(plusPos + 1, j - plusPos);
                string d = expression.substr(j + 1, expression.size() - j - 1);
                
                if (b.length() == 0 || c.length() == 0 || b[0] == '0' || c[0] == '0') {
                    continue;
                }
                
                if (a.length() > 0 && a[0] == '0') {
                    continue;
                }
                
                if (d.length() > 0 && d[0] == '0') {
                    continue;
                }
                
                int tmp = stoi(b) + stoi(c);
                string now = "(" + b + "+" + c + ")";
                
                if (a.length() > 0) {
                    tmp = tmp * stoi(a);
                    now = a + now;
                }
                
                if (d.length() > 0) {
                    tmp = tmp * stoi(d);
                    now = now + d;
                }
                
                if (tmp < ans) {
                    ans = tmp;
                    str = now;
                }
            }
        }
        return str;
    }
};

3. Maximum Product After K Increments

Greedy, increment the smallest number every time.

c++

typedef long long ll;

const ll kModulo = 1000000007;

class Solution {
public:
    int maximumProduct(vector<int>& nums, int k) {
        priority_queue<ll, vector<ll>, greater<ll>> pq;
        for (auto &num : nums) {
            pq.push(num);
        }
        while (k--) {
            ll x = pq.top(); pq.pop();
            pq.push(x + 1);
        }
        ll ans = 1;
        while (!pq.empty()) {
            ans = (ans * pq.top()) %kModulo;
            pq.pop();
        }
        return ans;
    }
};

4. Maximum Total Beauty of the Gardens

Assume k gardens will be completed, we know we'd better choose the top-k gardens so we can have most number of new flowers left (greedy).
Then we should use the new flowers left to maximize the minimum number of flowers in incomplete gardeens.
Making the first l-smallest gardens to have $\text{flowers}_{l}$ flowers requires $\text{flowers}_{l} \times l - \sum_{i=1}^{l}{\text{flowers}_i}$ new flowers.
We can binary search for the max l every time.
Time complexity: $O(n \times log(n))$ .

c++

typedef long long ll;

class Solution {
public:
    
    ll maximumBeauty(vector<int>& flowers, long long newFlowers, int target, int full, int partial) {
        ll n = flowers.size();
        
        for (ll i = 0; i < n; i++) {
            flowers[i] = min(flowers[i], target);
        }
        
        sort(flowers.begin(), flowers.end());
        
        vector<ll> sum(n + 1, 0);
        for (ll i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + flowers[i];
        }
        
        vector<ll> fill(n, 0);
        for (ll i = 0; i < n; i++) {
            fill[i] = (i + 1) * flowers[i] - sum[i + 1];
        }
        
        ll ans = 0;
        
        for (ll completeCnt = 0; completeCnt <= n; completeCnt++) {
            ll needForComplete = (completeCnt * target) - (sum[n] - sum[n - completeCnt]);
            if (needForComplete > newFlowers) {
                break;
            }
            
            // If all full.
            if (completeCnt == n) {
                ans = max(ans, completeCnt * full);
                continue;
            }
            
            ll restForPartial = newFlowers - needForComplete;
            
            ll lastPartial = -1;
            
            for (ll low = 0, high = (n - completeCnt - 1); low <= high; ) {
                ll mid = (low + high) / 2;
                if (flowers[mid] < target && fill[mid] <= restForPartial) {
                    low = mid + 1;
                    lastPartial = mid;
                } else {
                    high = mid - 1;
                }
            }
            
            if (lastPartial == -1) {
                continue;
            }
            
            ll restForPartial2 = restForPartial - fill[lastPartial];
            ll lastElem = (restForPartial2) / (lastPartial + 1) + flowers[lastPartial];
            
            if (lastElem >= target) {
                lastElem = target - 1;
            }
            
            if (lastElem >= target) {
                continue;
            }
            
            ll score1 = completeCnt * full;
            ll score2 = lastElem * partial;
            ll score = score1 + score2;
            
            ans = max(ans, score);
        }
        
        return ans;
    }
};

Leet Code Weekly Contest 288

1. Largest Number After Digit Swaps by Parity

2. Minimize Result by Adding Parentheses to Expression

3. Maximum Product After K Increments

4. Maximum Total Beauty of the Gardens

COMMAND INTERFACE

:help aguang.xyz