力扣周赛318题解

Posted on | Post modified:

力扣周赛318题解

对数组执行操作

题意：略

题解：

  • 直接按照题意模拟即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> applyOperations(vector<int>& nums) {
        int n = (int)nums.size();
        for(int i = 0; i + 1 < n; i++){
            if(nums[i] == nums[i + 1]){
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
        }
        vector<int> ans;
        for(int v: nums){
            if(v) ans.push_back(v);
        }
        for(int v: nums){
            if(v == 0) ans.push_back(v);
        }
        return ans;
    }
};

长度为 K 子数组中的最大和

简要题意：

对于一个长度为$n$的数组，求和最大的长度为$k$的不存在重复元素的子数组的和。

题解：

  • 使用set和map维护长度为$k$的窗口
  • 前缀和

代码：

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
class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        int n = (int)nums.size();
        vector<long long> pre(n + 1);
        for(int i = 1; i <= n; i++){
            pre[i] = pre[i - 1] + nums[i - 1];
        }
        
        long long ans = 0;
        set<long long> st;
        map<int, int> mps;
        for(int i = 0; i < k; i++) st.insert(nums[i]), mps[nums[i]]++;
        if((int)st.size() == k){
            ans = max(ans, pre[k]);
        }
        for(int i = k + 1; i <= n; i++){
            mps[nums[i - k - 1]]--;
            if(mps[nums[i - k - 1]] == 0){
                auto it = st.find(nums[i - k - 1]);
                st.erase(it);
            }
            st.insert(nums[i - 1]);
            mps[nums[i - 1]]++;
            if((int)st.size() == k){
                ans = max(ans, pre[i] - pre[i - k]);
            }
        }
        return ans;
    }
};

雇佣 K 位工人的总代价

简要题意：

对于一个长度为$n$的序列，每次在前$m$个元素和后$m$个元素中选择最小的删除，求$k$次的和。

题解：

  • 使用两个优先队列维护前$m$个元素和后$m$个元素
  • 双指针来拓展这两个优先队列

代码：

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


class Solution {
public:
    struct node{
        int id;
        int val;
        friend bool operator < (node a,node b){
            if(a.val == b.val){
                return a.id > b.id;
            }
            return a.val > b.val;
        }
    };
    long long totalCost(vector<int>& cost, int k, int m) {
        int n = (int)cost.size();
        int L = m - 1;//<=L
        int R = n - m;//>=R
        vector<pair<int, int> > tot;
        priority_queue<node> A, B;
        for(int i = 0; i <= L; i++){
            node p;
            p.id = i;
            p.val = cost[i];
             A.push(p);
        }
        for(int i = R; i < n; i++){
            node p;
            p.id = i;
            p.val = cost[i];
            B.push(p);
        }
        long long ans = 0;
        map<int, bool> vis;
        for(int steps = 1; steps <= k; steps++){
            if(A.empty()){
                ans += B.top().val;
                vis[B.top().id] = 1;
                B.pop();
                R--;
                while(R >= 0 && vis[R]) R--;
                if(R >= 0){
                    B.push({R, cost[R]}); 
                }
                continue;
            }
            if(B.empty()){
                ans += A.top().val;
                vis[A.top().id] = 1;
                A.pop();
                L++;
                while(L < n && vis[L]) L++;
                if(L < n){
                    A.push({L, cost[L]});
                }
                continue;
            }
            auto l = A.top();
            auto r = B.top();
            // cout << steps << "Lval: " << l.val << "Lid " << l.id << "Rval " << r.val << "Rid " << r.id <<  endl;
            if(l.val == r.val){
                if(l.id < r.id){
                    vis[A.top().id] = 1;
                    A.pop();
                    ans += l.val;
                    L++;
                    while(L < n && vis[L]) L++;
                    if(L < n){
                        A.push({L, cost[L]});
                    }
                }
                if(l.id > r.id){
                    vis[B.top().id] = 1;
                    B.pop();
                    ans += r.val;
                    R--;
                    while(R >= 0 && vis[R]) R--;
                    if(R >= 0){
                        B.push({R, cost[R]}); 
                    }
                }
                if(l.id == r.id){
                    vis[A.top().id] = 1;
                    A.pop();B.pop();
                    ans += l.val;
                    L++;
                    while(L < n && vis[L]) L++;
                    if(L < n){
                        A.push({L, cost[L]});
                    }
                    R--;
                    while(R >= 0 && vis[R]) R--;
                    if(R >= 0){
                        B.push({R, cost[R]}); 
                    }
                }
            }else if(l.val < r.val){
                vis[A.top().id] = 1;
                A.pop();
                ans += l.val;
                L++;
                while(L < n && vis[L]) L++;
                if(L < n){
                    A.push({L, cost[L]});
                }
            }else{
                vis[B.top().id] = 1;
                B.pop();
                ans += r.val;
                R--;
                while(R >= 0 && vis[R]) R--;
                if(R >= 0){
                    B.push({R, cost[R]}); 
                }
            }
        }
        return ans;
    }
};

最小移动总距离

简要题意：

$n$个坏掉的机器人， 第$i$个机器人的位置在$p_{i}$，有$m$个修理厂，第$i$个的修理厂位置在$x_{i}$，最多能修理$y_{i}$个机器人。机器人从$x$移动到$y$需要的距离是$|x - y|$。

求修复好所有机器人最小的移动距离。

题解：

  • 将机器人和修理厂按位置排序，一个修理厂一定是修复连续的一段机器人

  • 动态规划，考虑$dp[i][j]$表示前$i$个修理厂修复了前$j$个机器人最小的移动距离，则有

其中$cost[i][j]$表示第$j$个机器人移动到第$i$个修理厂需要的距离。

  • 时间复杂度$O(n ^ 3)$

代码：

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
class Solution {
public:
    long long cost[111][111];
    long long dp[111][111];
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(robot.begin(), robot.end());
        sort(factory.begin(), factory.end());
        long long ans = 0;
        int m = (int)robot.size();
        int n = (int)factory.size();
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cost[i][j] = abs(robot[j - 1] - factory[i - 1][0]);
            }
        }
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= m; j++) dp[i][j] = 1e18;
        }
        dp[0][0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= m; j++){
                long long now = 0;
                dp[i][j] = min(dp[i][j], dp[i - 1][j]);
                for(int k = 1; k <= factory[i - 1][1] && j + k <= m; k++){
                    now += cost[i][j + k];
                    dp[i][j + k] = min(dp[i][j + k], dp[i - 1][j] + now);
                }
            }
        }
        return dp[n][m];
    }
};

彩蛋

xXz04x.jpg