[数据结构与算法]leetcode竞赛：20220918双周赛

leetcode 周赛

题目一

日期问题：
区间问题：求交集

class Solution {
public:
    int arr[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
        for (int i = 1; i <= 12; i++) {
            arr[i] += arr[i - 1];
        }
        int a, b, c, d;
        process(arriveAlice, leaveAlice, a, b);
        process(arriveBob, leaveBob, c, d);
        // cout << a << " " << b << endl;
        // cout << c << " " << d << endl;
        if (b < c || d < a) return 0;
        if (a <= c) {
            return min(b, d) - c + 1;
        } else {
             return min(b, d) - a + 1;
        }
        return 0;
        
    }
    
    void process(string& a, string& b, int& c, int& d) {
        int x = (a[0] - '0') * 10 + (a[1] - '0');
        int y = (a[3] - '0') * 10 + (a[4] - '0');
        c = arr[x - 1] + y;
        x = (b[0] - '0') * 10 + (b[1] - '0');
        y = (b[3] - '0') * 10 + (b[4] - '0');
        d = arr[x - 1] + y; 
    }
};

题目二

贪心算法
匈牙利算法

class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        sort(players.begin(), players.end());
        sort(trainers.begin(), trainers.end());
        int n = players.size(), m = trainers.size();
        int res = 0;
        for (int i = 0, j = 0; i < n && j < m;) {
            int a = players[i], b = trainers[j];
            if (a <= b) {
                res++;
                i++, j++;
                continue;
            } else {
                j++;
            }
        }
        return res;
    }
};

题目三

class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> x(32, vector<int>(n + 1));
        nums.push_back(INT_MAX);
        vector<int> ret;
        for (int i = n; i >= 0; i--) {
            int res = 1;
            for (int j = 0; j < 31; j++) {
                if (i == n) {
                    x[j][i] = n;
                    continue;
                }
                if (nums[i] & (1 << j)) x[j][i] = i; 
                else x[j][i] = x[j][i + 1];
                if (x[j][i] == n) continue;
                res = max(x[j][i] - i + 1, res);
            }
            ret.push_back(res);
        }
        reverse(ret.begin(), ret.end());
        ret.pop_back();
        return ret;
    }
};

题目四

没写出来.看答案是比较难想的一种枚举。对于任意一遍交易，对于其中的交易$i$，必须满足等式
$money?(a_0?b_0)?(a_1?b_1)?(a_2?b_2)....>=a_i$（注意0， 1， 不是数组顺序，而是任意一种交易顺序）。整理一下有：
$money>=(a_0?b_0)+(a_1?b_1)+(a_2?b_2)....+a_i$。
可以看到等式有两部分，前面的每笔交易结果之和与第$i$笔交易需要的钱的和。这时候转换思维，想象$a_i$不是第$i$笔交易，而是对于交易$i$,我的money最少需要准备多少钱，才能满足最坏情况的交易$i$，那应该是右边最大。$a_i$是固定的，那么只需要前面的和最大。前面和最大，要把所有$a>b$的交易加起来，答案就呼之欲出了。
贴一个学会之后自己写的代码。

typedef long long LL;
class Solution {
public:
    long long minimumMoney(vector<vector<int>>& transactions) {
        LL sum = 0;
        for (auto &ii : transactions) {
            int a = ii[0], b = ii[1];
            if (a > b) sum += a - b;
        }
        LL res = 0;
        for (auto &ii : transactions) {
            int a = ii[0], b = ii[1];
            if (a > b) res = max(res, a + sum - a + b);
            else res = max(res, a + sum); 
        }
        return res;
    }
};