A. Check if Number Has Equal Digit Count and Digit Value (opens new window)

Count frequency of each digit.

DETAILS

class Solution:
    def digitCount(self, num: str) -> bool:
        d = collections.Counter(num)
        for i in range(len(num)):
            if int(num[i])!=d.get(str(i), 0):
                return False
        return True

B. Sender With Largest Word Count (opens new window)

Count the number of words in each string.

DETAILS

class Solution {
public:
    string largestWordCount(vector<string>& M, vector<string>& S) {
        map<string, int> mp;
        string ans;
        int maxx = -1;
        for (int i = 0; i < M.size(); ++i) {
            int cur = count(M[i].begin(), M[i].end(), ' ') + 1;
            mp[S[i]] += cur;
            if (mp[S[i]] > maxx) {
                maxx = mp[S[i]];
                ans = S[i];
            }
            else if (mp[S[i]] == maxx)
                ans = max(ans, S[i]);
        }
        return ans;
    }
};

C. Maximum Total Importance of Roads (opens new window)

Sort nodes by degree, assign the highest importance to the node with the maximum degree.

DETAILS

#define ll long long
class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& R) {
        map<int, ll> mp;
        for (auto r : R) {
            mp[r[0]]++;
            mp[r[1]]++;
        }
        vector<ll> A;
        for(const auto &x : mp) A.push_back(x.second);
        sort(A.begin(), A.end());
        ll idx = 1 + n - A.size(), ans = 0;
        for (auto a : A) {
            ans += a * idx;
            idx++;
        }
        return ans;
    }
};

D. Booking Concert Tickets in Groups (opens new window)

We need to get the sum of all empty seats, and the maximum empty seats in a single row (remaining positions) from row 0 to row maxRow. The previous value (sum of all the empty seats) can be solved only using prefix sum, thus we can use BIT. However the second query can't be done only using prefix sum, thus we can use Segment Tree.

(No need to use lazy propagation, since we are only updating single value each time.)

We maintain two values for queries: max and sum. For the first kind of query, in order to locate the first row that having k empty seats, we can use binary search on row numbers. For the second query, if there are enough empty scattered seats, we will fill them from from to back (as required), this step only takes O(1) amortized time.

DETAILS

#define ll long long
#define vl vector<ll>
#define vi vector<int>
#define vpl vector<pair<ll, ll>>
class BookMyShow {
    ll n, m, sz;
    vpl tree;
    vi curr;
public:
    void build(int p, int s, int t) {
        if (s == t) {
            tree[p].first = m;
            tree[p].second = m;
            return;
        }
        int m = s + ((t - s) >> 1);
        build(p * 2 + 1, s, m);
        build(p * 2 + 2, m + 1, t);
        tree[p].first = max(tree[2 * p + 1].first, tree[2 * p + 2].first);
        tree[p].second = tree[2 * p + 1].second + tree[2 * p + 2].second;
    }
    ll getmax(int p, int start, int end, int L, int R) {   
        if (L <= start && end <= R) return tree[p].first;
        int mid = ((start + end) >> 1);
        ll maxx = INT_MIN;
        if (L <= mid) maxx = max(maxx, getmax(p * 2 + 1, start, mid, L, R));
        if (R > mid) maxx = max(maxx, getmax(p * 2 + 2, mid + 1, end, L, R));
        return maxx;
    }
    ll getsum(int p, int start, int end, int L, int R) {
        if (L <= start && end <= R) return tree[p].second;
        int mid = ((start + end) >> 1);
        ll summ = 0;
        if (L <= mid) summ += getsum(p * 2 + 1, start, mid, L, R);
        if (R > mid) summ += getsum(p * 2 + 2, mid + 1, end, L, R);
        return summ;
    }
    /* query with result*/
    int qmax(int p, int start, int end, int k, int RR) {
        if (start > RR || tree[p].first < k) return -1;
        if (start == end) return start;
        int mid = ((start + end) >> 1);
        int res = qmax(2 * p + 1, start, mid, k, RR);
        if (res == -1) 
            res = qmax(2 * p + 2, mid + 1, end, k, RR);
        return res;
    }
    /* update single node */
    void update_s(int p, int start, int end, int idx, int val) {
        if (start == end) {
            tree[p].first = val;
            tree[p].second = val;
            return;
        } 
        int mid = ((start + end) >> 1);
        if (idx <= mid) 
            update_s(p * 2 + 1, start, mid, idx, val);
        else 
            update_s(p * 2 + 2, mid + 1, end, idx, val);    
        
        tree[p].first = max(tree[2 * p + 1].first, tree[2 * p + 2].first);
        tree[p].second = tree[2 * p + 1].second + tree[2 * p + 2].second;
    }
    
    BookMyShow(int nn, int mm) {
        n = nn, m = mm, sz = 1;
        while (sz < nn * 2) sz *= 2;
        tree.assign(sz, {0, 0});
        curr.resize(n, m);
        build(0, 0, n - 1);
    } 
    vector<ll> gather(int k, int maxRow) {
        int idx = qmax(0, 0, n - 1, k, maxRow);
        if (idx != -1) {
            int remain = curr[idx];
            update_s(0, 0, n - 1, idx, remain - k);
            curr[idx] -= k;
            return {idx, m - remain};
        }
        return {};
    }    
    bool scatter(int k, int maxRow) {
        ll ss = getsum(0, 0, n - 1, 0, maxRow);
        if (ss >= 1LL * k) {
            int idx = 0;
            while (idx <= maxRow && k > 0) {
                int res = curr[idx];
                int amt = min(res, k);
                update_s(0, 0, n - 1, idx, res - amt);
                curr[idx] -= amt;
                k -= amt;
                if (k > 0) idx++;
            }
            return true;
        }
        return false;
    }
};