Skip to content

第 314 场周赛

比赛链接

Date: 2022-10-09（高铁上参加）

A 处理用时最长的那个任务的员工

暴力

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int hardestWorker(int n, vector<vector<int>>& logs) {
        int mx = 0, st = 0, res = 0;
        for (int i = 0; i < logs.size(); i++) {
            int cur = logs[i][1] - st;
            if (cur > mx) {
                mx = cur;
                res = logs[i][0];
            } else if(cur == mx) {
                res = min(res, logs[i][0]);
            }
            st = logs[i][1];
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def hardestWorker(self, n: int, logs: List[List[int]]) -> int:
        mx, st, res = 0, 0, 0
        for i in range(len(logs)):
            if i == 0:
                cur = logs[i][1]
            else:
                cur = logs[i][1] - logs[i - 1][1]
            if cur > mx:
                mx = cur
                res = logs[i][0]
            elif cur == mx and res > logs[i][0]:
                res = logs[i][0]
        return res

B 找出前缀异或的原始数组

根据异或的可消性，从后往前推导即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    vector<int> findArray(vector<int>& pref) {
        int n = pref.size();
        vector<int> res(n);
        for (int i = n - 1; i >= 0; i--) {
            if (i == 0) {
                res[i] = pref[i];
            } else {
                res[i] = pref[i] ^ pref[i - 1];
            }
        }
        return res;
    }
};

1
2
3
4
5
6
7
class Solution:
    def findArray(self, pref: List[int]) -> List[int]:
        n = len(pref)
        res = pref
        for i in range(n - 1, 0, -1):
            res[i] = pref[i] ^ pref[i - 1]
        return res

C 使用机器人打印字典序最小的字符串

机器人就是栈，当栈中元素小于等于当前后缀的最小值时，可以弹出。时间复杂度为 \(O(n)\)

 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
class Solution {
public:
    string robotWithString(string s) {
        int n = s.size();
        vector<char> ms(n, 'z');
        for (int i = n - 1; i >= 0; i--) {
            if (i == n - 1) {
                ms[i] = s[i];
            } else {
                ms[i] = min(ms[i + 1], s[i]);
            }
        }
        stack<char> stk;
        string res;
        for (int i = 0; i < n; i++) {
            while (stk.size() && stk.top() <= ms[i]) {
                res += stk.top();
                stk.pop();
            }
            stk.push(s[i]);
        }
        while (stk.size()) {
            res += stk.top();
            stk.pop();
        }
        return res;
    }
};

D 矩阵中和能被 K 整除的路径

动态规划，复杂度 \(O(nmk)\)

class Solution {
public:
    int numberOfPaths(vector<vector<int>>& g, int k) {
        int n = g.size(), m = g[0].size();
        const int MOD = 1E9 + 7;
        vector<vector<vector<int>>> d(n + 1, vector<vector<int>>(m + 1, vector<int>(k, 0)));
        d[0][1][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int val = g[i - 1][j - 1];
                for (int p = 0; p < k; p++) {
                    int x = (val + p) % k;
                    d[i][j][x] += (d[i - 1][j][p] + d[i][j - 1][p]) % MOD;
                    d[i][j][x] %= MOD;
                }
            }
        }
        return d[n][m][0];
    }
};
本文访问 次