Leet Code Weekly Contest 294

1. Percentage of Letter in String

Naive.

c++

class Solution {
public:
    int percentageLetter(string s, char letter) {
        int cnt = 0, len = s.length();
        for (auto &c : s) {
            if (c == letter) {
                cnt++;
            }
        }
        return 100 * cnt / len;
    }
};

2. Maximum Bags With Full Capacity of Rocks

Greedy.

c++

class Solution {
public:
    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
        int n = capacity.size();
        for (int i = 0; i < n; i++) {
            capacity[i] -= rocks[i];
        }
        sort(capacity.begin(), capacity.end());
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int d = min(capacity[i], additionalRocks);
            capacity[i] -= d;
            additionalRocks -= d;
            if (capacity[i] == 0) {
                ans++;
            }
        }
        return ans;
    }
};

3. Minimum Lines to Represent a Line Chart

Sort.

c++

class Solution {
public:
    int minimumLines(vector<vector<int>>& stockPrices) {
        map<int, int> points;
        for (auto &stock : stockPrices) {
            points[stock[0]] = stock[1];
        }
        vector<pair<int, int>> pixels;
        for (auto &pair : points) {
            pixels.push_back(make_pair(pair.first, pair.second));
        }
        int prevDx = 0, prevDy = 0, ans = 0;
        for (int i = 1; i < pixels.size(); i++) {
            int dx = pixels[i].first - pixels[i - 1].first;
            int dy = pixels[i].second - pixels[i - 1].second;
            int d = gcd(dx, dy);
            dx /= d;
            dy /= d;
            if (dx != prevDx || dy != prevDy) {
                ans++;
                prevDx = dx;
                prevDy = dy;
            }
        }
        return ans;
    }
};

4. Sum of Total Strength of Wizards

Given element strength[i], we can find two positions L and R, where
- L is either 0 or the largest one where strength[L - 1] <= strength[i];
- R is either n - 1 or the smallest one where strengt[R + 1] > strength[i];
And we know, for any subarray [P, Q] (L <= P <= i and i <= Q <= R), the first minimum element is strength[i].
Now given strength[i], L and R, the answer contributed by strength[i] should be A + B where

A = \sum_{j = L}^{i} \text{strength}_{j} \times (j - L + 1) \times (R - i + 1)

B = \sum_{j = i + 1}^{R} \text{strength}_{j} \times (i - L + 1) \times (R - j + 1)

Now, if we have two generated sequences (which can be initialized in O(n)):

F_{i} = \sum_{j = 0}^{i} \text{strength}_{j}

G_{i} = \sum_{j = 0}^{i} \text{strength}_{j} \times j

We can then further simply the formula:

A = (R - i + 1) \times ((G_i - G_{L - 1}) + (1 - L) \times (F_i - F_{L - 1}))

B = (i - L + 1) \times ((G_R - G_i) + (R + 1) \times (F_R - F_i))

We can initialize L and R for each i with Monotone Stacks.
Now, we got an O(n) solution.

c++

typedef long long ll;

const ll kMod = 1E9 + 7;

class Solution {
private:
    ll n_;
    vector<ll> sum_, sum2_, prev_, next_;
    
    ll getSum(int l, int r) {
        if (l <= r) {
            return sum_[r + 1] - sum_[l];
        }
        return 0;
    }
    
    ll getSum2(int l, int r) {
        if (l <= r) {
            return sum2_[r + 1] - sum2_[l];
        }
        return 0;
    }
    
public:
    int totalStrength(vector<int>& strength) {
        n_ = strength.size();
        
        sum_ = { 0 };
        for (auto &x : strength) {
            sum_.push_back((sum_.back() + x) % kMod);
        }
        
        sum2_ = { 0 };
        for (ll i = 0; i < n_; i++) {
            sum2_.push_back((sum2_.back() + (i * strength[i])) % kMod);
        }
        
        prev_ = vector<ll>(n_);
        next_ = vector<ll>(n_);
        
        stack<ll> s;
        
        s = stack<ll>();
        for (ll i = 0; i < n_; i++) {
            while (!s.empty() && strength[s.top()] > strength[i]) s.pop();
            prev_[i] = s.empty() ? 0 : s.top() + 1;
            s.push(i);
        }
        
        s = stack<ll>();
        for (ll i = n_ - 1; i >= 0; i--) {
            while (!s.empty() && strength[s.top()] >= strength[i]) s.pop();
            next_[i] = s.empty() ? (n_ - 1) : s.top() - 1;
            s.push(i);
        }
        
        ll ans = 0;
        
        for (ll i = 0; i < n_; i++) {
            ll l = prev_[i], r = next_[i];
            
            ans += (strength[i] * (r - i + 1) % kMod) * (( getSum2(l, i) - (l - 1) * getSum(l, i) ) % kMod);
            ans += (strength[i] * (i - l + 1) % kMod) * (( (r + 1) * getSum(i + 1, r) - getSum2(i + 1, r) ) % kMod);
            
            ans = ans % kMod;
            ans = ans + kMod;
            ans = ans % kMod;
        }
        
        return ans;
    }
};

Leet Code Weekly Contest 294

1. Percentage of Letter in String

2. Maximum Bags With Full Capacity of Rocks

3. Minimum Lines to Represent a Line Chart

4. Sum of Total Strength of Wizards

COMMAND INTERFACE

:help aguang.xyz