CP Wiki

# Leetcode 第230场周赛题解

# Problem A - 统计匹配检索规则的物品数量 (opens new window)

按要求模拟即可。

  • 时间复杂度O(N)\mathcal{O}(N)。
  • 空间复杂度O(1)\mathcal{O}(1)。
参考代码（C++） 
class Solution {
public:
    int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
        int ans = 0;
        int n = items.size();
        unordered_map<string, int> mp = {{"type", 0}, {"color", 1}, {"name", 2}};
        int key = mp[ruleKey];
        for (int i = 0; i < n; ++i)
            if (items[i][key] == ruleValue)
                ans++;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

# Problem B - 最接近目标价格的甜点成本 (opens new window)

本题数据范围很小，暴力枚举辅料组合就可以通过，但时间复杂度为指数级。

把问题转化为背包问题，可以将时间复杂度降低到多项式级别。

  • 因为每种辅料最多可以用两次，所以直接把每种辅料变成两个。
  • 基料必须且只能选一种，可以首先处理好。

之后就按照0-1背包问题的一般做法，依次枚举辅料即可。

  • 时间复杂度O(N+M⋅MAXC)\mathcal{O}(N + M\cdot MAXC)。其中MAXCMAXC为背包的最大容量。本题中MAXC=20000MAXC=20000，因为答案不可能超过2000020000。
  • 空间复杂度O(MAXC)\mathcal{O}(MAXC)。
参考代码（C++） 
class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        vector<bool> can(20001);
        for (int base : baseCosts)
            can[base] = true;
        toppingCosts.insert(toppingCosts.end(), toppingCosts.begin(), toppingCosts.end());
        for (int topping : toppingCosts) {
            for (int i = 20000; i >= topping; --i)
                can[i] = can[i] || can[i - topping];
        }
        int min_gap = INT_MAX, ans = 0;
        for (int i = 1; i <= 20000; ++i)
            if (can[i] && abs(i - target) < min_gap) {
                ans = i;
                min_gap = abs(i - target);
            }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Problem C - 通过最少操作次数使数组的和相等 (opens new window)

我们可以发现：

  • 如果min⁡(N,M)∗6<max⁡(N,M)\min(N,M)*6<\max(N,M)则无解，因为此时即使把数少的那边都变成66，同时数多的那边都变成11，也不能使两侧相等。
  • 增大nums1nums1中的一个数，就等于减小nums2nums2中的一个数。
  • 在有多个数可以选择的情况下，增大时应该优先增大较小的数（上升空间大）；同理，减小时应当优先减小较大的数（下降空间大）。

因此，我们统计出增长空间incinc和减小空间decdec。

  • 如果∑nums1>∑nums2\sum_{nums1}>\sum_{nums2}，我们应当进行减小操作（减小nums1nums1中的数或增大nums2nums2中的数），直到∑nums1≤∑nums2\sum_{nums1}\leq\sum_{nums2}。
  • 反之，我们进行增大操作，直到∑nums1≥∑nums2\sum_{nums1}\geq\sum_{nums2}。

直接对incinc或decdec降序排序就可以通过；而利用计数排序，我们可以将时间复杂度进一步优化到线性时间。

  • 时间复杂度O(N+M)\mathcal{O}(N + M)。
  • 空间复杂度O(∣∑∣)\mathcal{O}(|\sum|)。
参考代码（C++） 
class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        if (n > m * 6 || m > n * 6)
            return -1;
        int s1 = 0, s2 = 0;
        vector<int> inc(6), dec(6);
        for (int num : nums1) {
            s1 += num;
            if (num < 6)
                inc[6 - num]++;
            if (num > 1)
                dec[num - 1]++;
        }
        for (int num : nums2) {
            s2 += num;
            if (num < 6)
                dec[6 - num]++;
            if (num > 1)
                inc[num - 1]++;
        }
        if (s1 == s2)
            return 0;
        
        int cnt = 0;
        if (s1 > s2) {
            for (int i = 5; i >= 1; --i) {
                while (dec[i]) {
                    s1 -= i;
                    dec[i]--;
                    cnt++;
                    if (s1 <= s2)
                        return cnt;
                }
            }
        } else {
            for (int i = 5; i >= 1; --i) {
                while (inc[i]) {
                    s1 += i;
                    inc[i]--;
                    cnt++;
                    if (s1 >= s2)
                        return cnt;
                }
            }
        }
        
        return -1;
    }
};
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

# Problem D - 车队 II (opens new window)

因为每次发生相遇之后，都可能发生速度的变化，所以我们需要按照时间顺序来处理所有的事件。

# 方法一：优先队列+并查集

  • 时间复杂度O(Nlog⁡N)\mathcal{O}(N\log N)。
  • 空间复杂度O(N)\mathcal{O}(N)。
参考代码（C++） 
struct DSU {
    vector<int> p, sz, speed, left, right;
    vector<double> pos, speed_change;
    
    DSU(vector<int> &speed, vector<double> &pos): speed(speed), pos(pos) {
        int n = speed.size();
        p = vector<int>(n);
        left = vector<int>(n);
        right = vector<int>(n);
        speed_change = vector<double>(n);
        for (int i = 0; i < n; ++i)
            p[i] = left[i] = right[i] = i;
        sz = vector<int>(n, 1);
    }
    
    int find(int i) {
        return p[i] == i ? i : p[i] = find(p[i]);
    }
    
    void merge(int i, int j) {
        int pi = find(i), pj = find(j);
        if (pi == pj)
            return;
        int spd = min(speed[pi], speed[pj]);
        int l = min(left[pi], left[pj]);
        int r = max(right[pi], right[pj]);
        double ps = max(pos[pi], pos[pj]);
        double spc = max(speed_change[pi], speed_change[pj]);
        if (sz[pi] >= sz[pj]) {
            speed[pi] = spd;
            left[pi] = l;
            right[pi] = r;
            pos[pi] = ps;
            speed_change[pi] = spc;
            sz[pi] += sz[pj];
            p[pj] = pi;
        } else {
            speed[pj] = spd;
            left[pj] = l;
            right[pj] = r;
            pos[pj] = ps;
            speed_change[pj] = spc;
            sz[pj] += sz[pi];
            p[pi] = pj;
        }
    }
    
    int get_speed(int idx) {
        return speed[find(idx)];
    }
    
    double get_pos(int idx) {
        return pos[find(idx)];
    }
    
    int get_left(int idx) {
        return left[find(idx)];
    }
    
    int get_right(int idx) {
        return right[find(idx)];
    }
    
    double get_speed_change(int idx) {
        return speed_change[find(idx)];
    }
    
    void set_pos(int idx, double ps) {
        pos[find(idx)] = ps;
    }
    
    void set_speed_change(int idx, double spc) {
        speed_change[find(idx)] = spc;
    }
    
    void move(int idx, double t) {
        if (t < get_speed_change(idx))
            return;
        double delta = t - get_speed_change(idx);
        pos[find(idx)] += get_speed(idx) * delta;
        speed_change[find(idx)] = t;
    }
};

class Solution {
public:
    vector<double> getCollisionTimes(vector<vector<int>>& cars) {
        int n = cars.size();
        vector<double> ans(n, -1.0);
        priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> pq;
        vector<int> speed(n);
        vector<double> time(n, -1.0), speed_change(n), pos(n);
        for (int i = 0; i < n; ++i)
            pos[i] = cars[i][0], speed[i] = cars[i][1];
        for (int i = 0; i < n - 1; ++i) {
            if (cars[i][1] > cars[i + 1][1]) {
                double t = (pos[i + 1] - pos[i]) / (cars[i][1] - cars[i + 1][1]);
                pq.emplace(t, i);
                time[i] = t;
            }
        }
        DSU dsu(speed, pos);
        while (!pq.empty()) {
            auto [t, idx] = pq.top();
            pq.pop();
            if (abs(t - time[idx]) > 1e-6 || ans[idx] > 0)
                continue;
            ans[idx] = t;
            int L = dsu.get_left(idx) - 1, R = dsu.get_right(idx + 1) + 1;
            dsu.move(idx, t), dsu.move(idx + 1, t);
            dsu.merge(idx, idx + 1);
            if (L >= 0 && ans[L] < 0) {
                dsu.move(L, t), dsu.move(L + 1, t);
                int sp0 = dsu.get_speed(L), sp1 = dsu.get_speed(L + 1);
                if (sp0 > sp1) {
                    double nxt = t + (dsu.get_pos(L + 1) - dsu.get_pos(L)) / (sp0 - sp1);
                    pq.emplace(nxt, L);
                    time[L] = nxt;
                } else {
                    time[L] = -1.0;
                }
            }
            if (R < n && ans[R - 1] < 0) {
                dsu.move(R - 1, t), dsu.move(R, t);
                int sp0 = dsu.get_speed(R - 1), sp1 = dsu.get_speed(R);
                if (sp0 > sp1) {
                    double nxt = t + (dsu.get_pos(R) - dsu.get_pos(R - 1)) / (sp0 - sp1);
                    pq.emplace(nxt, R - 1);
                    time[R - 1] = nxt;
                } else {
                    time[R - 1] = -1.0;
                }
            }
        }
        return ans;
    }
};
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

# 方法二：单调栈（待补）

← Leetcode 第229场周赛题解 →