且听疯吟

leetcode contest 314

2022-11-02

leetcode contest 314

第三题竟然时最难的题目了，第四题确实太简单了一点。

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

题目

共有 n 位员工，每位员工都有一个从 0 到 n - 1 的唯一 id 。

给你一个二维整数数组 logs ，其中 logs[i] = [idi, leaveTimei] ：

  • idi 是处理第 i 个任务的员工的 id ，且
  • leaveTimei 是员工完成第 i 个任务的时刻。所有 leaveTimei 的值都是 唯一 的。
    注意，第 i 个任务在第(i - 1)个任务结束后立即开始，且第 0 个任务从时刻 0 开始。

返回处理用时最长的那个任务的员工的 id 。如果存在两个或多个员工同时满足，则返回几人中 最小 的 id 。

示例 1：

输入：n = 10, logs = [[0,3],[2,5],[0,9],[1,15]]
输出：1
解释：
任务 0 于时刻 0 开始，且在时刻 3 结束，共计 3 个单位时间。
任务 1 于时刻 3 开始，且在时刻 5 结束，共计 2 个单位时间。
任务 2 于时刻 5 开始，且在时刻 9 结束，共计 4 个单位时间。
任务 3 于时刻 9 开始，且在时刻 15 结束，共计 6 个单位时间。
时间最长的任务是任务 3 ，而 id 为 1 的员工是处理此任务的员工，所以返回 1 。

示例 2：

输入：n = 26, logs = [[1,1],[3,7],[2,12],[7,17]]
输出：3
解释：
任务 0 于时刻 0 开始，且在时刻 1 结束，共计 1 个单位时间。
任务 1 于时刻 1 开始，且在时刻 7 结束，共计 6 个单位时间。
任务 2 于时刻 7 开始，且在时刻 12 结束，共计 5 个单位时间。
任务 3 于时刻 12 开始，且在时刻 17 结束，共计 5 个单位时间。
时间最长的任务是任务 1 ，而 id 为 3 的员工是处理此任务的员工，所以返回 3 。

示例 3：

输入：n = 2, logs = [[0,10],[1,20]]
输出：0
解释：
任务 0 于时刻 0 开始，且在时刻 10 结束，共计 10 个单位时间。
任务 1 于时刻 10 开始，且在时刻 20 结束，共计 10 个单位时间。
时间最长的任务是任务 0 和 1 ，处理这两个任务的员工的 id 分别是 0 和 1 ，所以返回最小的 0 。

提示：

  • 2 <= n <= 500
  • 1 <= logs.length <= 500
  • logs[i].length == 2
  • 0 <= idi <= n - 1
  • 1 <= leaveTimei <= 500
  • idi != idi + 1
  • leaveTimei 按严格递增顺序排列

地址

https://leetcode.cn/problems/the-employee-that-worked-on-the-longest-task/

题意

直接模拟

思路

  1. 题目比较怪异，不是很好的题目，直接模拟即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 为数组的长度。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int hardestWorker(int n, vector<vector<int>>& logs) {
        int m = logs.size();
        int time = 0;
        int idx = n;
        int maxCost = 0;
        for (int i = 0; i < m; i++) {
            int cost = logs[i][1] - time;
            if (cost > maxCost ) {
                maxCost = cost;
                idx = logs[i][0];
            } else if (cost == maxCost && logs[i][0] < idx) {
                idx = logs[i][0];
            }
            time = logs[i][1];
        }
        return idx;
    }
};

6201. 找出前缀异或的原始数组

题目

给你一个长度为 n 的 整数 数组 pref 。找出并返回满足下述条件且长度为 n 的数组 arr ：

pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].
注意 ^ 表示 按位异或（bitwise-xor）运算。

可以证明答案是 唯一 的。

示例 1：

输入：pref = [5,2,0,3,1]
输出：[5,7,2,3,2]
解释：从数组 [5,7,2,3,2] 可以得到如下结果：
- pref[0] = 5
- pref[1] = 5 ^ 7 = 2
- pref[2] = 5 ^ 7 ^ 2 = 0
- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3
- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1

示例 2：

输入：pref = [13]
输出：[13]
解释：pref[0] = arr[0] = 13

提示：

  • 1 <= pref.length <= 105
  • 0 <= pref[i] <= 106

地址

https://leetcode.cn/problems/find-the-original-array-of-prefix-xor/

题意

数学问题

思路

  1. 非常简单的踢腿公式即可。我们知道 $arr[0] = pref[0]$，根据题意可知 $pref[i] = arr[0] \oplus arr[1] \cdots arr[i]$，所以可以知道:
    $$
    arr[i] = pref[i] \oplus arr[0] \oplus arr[1] \cdots arr[i - 1]
    $$
    我们根据上述公式依次求出 $arr$ 即可。
  2. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(n)$，其中 $n$ 表示数组的长度。
  • 空间复杂度：空间复杂度为 $O(1)$。

代码

class Solution {
public:
    vector<int> findArray(vector<int>& pref) {
        int n = pref.size();
        vector<int> res(n);
        res[0] = pref[0];
        int tot = res[0];
        for (int i = 1; i < n; i++) {
            res[i] = tot ^ pref[i];
            tot = tot ^ res[i];
        }
        return res;
    }
};

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

题目

给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：

  • 删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
  • 删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。
    请你返回纸上能写出的字典序最小的字符串。

示例 1：

输入：s = "zza"
输出："azz"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="zza" ，t="" 。
执行第一个操作三次，得到 p="" ，s="" ，t="zza" 。
执行第二个操作三次，得到 p="azz" ，s="" ，t="" 。

示例 2：

输入：s = "bac"
输出："abc"
解释：用 p 表示写出来的字符串。
执行第一个操作两次，得到 p="" ，s="c" ，t="ba" 。
执行第二个操作两次，得到 p="ab" ，s="c" ，t="" 。
执行第一个操作，得到 p="ab" ，s="" ，t="c" 。
执行第二个操作，得到 p="abc" ，s="" ，t="" 。

示例 3：

输入：s = "bdda"
输出："addb"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="bdda" ，t="" 。
执行第一个操作四次，得到 p="" ，s="" ，t="bdda" 。
执行第二个操作四次，得到 p="addb" ，s="" ，t="" 。

提示：

  • 1 <= s.length <= 105
  • s 只包含小写英文字母。

地址

https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string/

题意

贪心

思路

  1. 经典的贪心算法问题，即求最大或者最小出栈顺序，我们可以将 $t$ 看做一个栈，求字典序最小的出栈顺序；往上可以搜到原题。
  2. 为保证出栈顺序最小，我们首先将元素压入到栈中，如果发现剩余未入栈的字符串中没有比当前元素更小的字符时，应该将栈顶元素出栈。
  3. 复杂度分析
  • 时间复杂度：时间复杂度为 $O(n)$，$n$ 为字符串的长度。
  • 空间复杂度：时间复杂度为 $O(n)$，$n$ 为字符串的长度。

代码

class Solution {
public:
    string robotWithString(string s) {
        int n = s.size();
        vector<char> rmin(n);
        rmin[n - 1] = s[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rmin[i] = min(s[i], rmin[i + 1]);
        }
        stack<char> st;
        string res;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && st.top() <= rmin[i]) {
                res.push_back(st.top());
                st.pop();
            }
            st.emplace(s[i]);
        }
        while (!st.empty()) {
            res.push_back(st.top());
            st.pop();
        }
        return res;
    }
};

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

题目

给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往 下 或者往 右 ，你想要到达终点 (m - 1, n - 1) 。

请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 109 + 7 取余 的结果。

示例 1：

输入：grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
输出：2
解释：有两条路径满足路径上元素的和能被 k 整除。
第一条路径为上图中用红色标注的路径，和为 5 + 2 + 4 + 5 + 2 = 18 ，能被 3 整除。
第二条路径为上图中用蓝色标注的路径，和为 5 + 3 + 0 + 5 + 2 = 15 ，能被 3 整除。

示例 2：

输入：grid = [[0,0]], k = 5
输出：1
解释：红色标注的路径和为 0 + 0 = 0 ，能被 5 整除。

示例 3：

输入：grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
输出：10
解释：每个数字都能被 1 整除，所以每一条路径的和都能被 k 整除。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 5 * 104
  • 1 <= m * n <= 5 * 104
  • 0 <= grid[i][j] <= 100
  • 1 <= k <= 50

地址

https://leetcode.cn/problems/maximum-deletions-on-a-string/description/

题意

动态规划

思路

  1. 太常规的题目了，基本上看到就知道思路的题目，设 $dp[i][j][s]$ 表示经过 $(i,j)$ 且路径和对 $k$ 取模为 $s$ 的路径数目，则可以知道递推公式:
    $$
    dp[i][j][k] = dp[i-1][j][(k - grid[i][j]) \mod k] + dp[i][j][(k - grid[i][j]) \mod k]
    $$
    非常简单的动态规划的思路，没有太大难度。
  2. 复杂度分析：
  • 时间复杂度：$O(m \times n \times k)$，其中 $m,n$ 表示给定的矩阵的行数与列数。
  • 空间复杂度：$O(m \times n)$，其中 $m,n$ 表示给定的矩阵的行数与列数。

代码

class Solution {
public:
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        long long dp[m][n][k];
        long long mod = 1e9 + 7;
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    dp[0][0][grid[0][0] % k]++;
                    continue;
                }
                for (int s = 0; s < k; s++) {
                    if (i - 1 >= 0 && dp[i-1][j][s] > 0) {
                        dp[i][j][(s + grid[i][j]) % k] = (dp[i][j][(s + grid[i][j]) % k] + dp[i-1][j][s]) % mod;
                    }
                    if (j - 1 >= 0 && dp[i][j - 1][s] > 0) {
                        dp[i][j][(s + grid[i][j]) % k] = (dp[i][j][(s + grid[i][j]) % k] + dp[i][j-1][s]) % mod;
                    }
                }
            }
        }
        return dp[m-1][n-1][0];
    }
};

欢迎关注和打赏，感谢支持！

Tags: 力扣周赛
← leetcode biweekly contest 88 leetcode contest 315 →

扫描二维码，分享此文章