链接：LeetCode
[Leetcode]2432. 处理用时最长的那个任务的员工
共有 n 位员工，每位员工都有一个从 0 到 n - 1 的唯一 id 。
给你一个二维整数数组 logs ，其中 logs[i] = [idi, leaveTimei] ：
- idi 是处理第 i 个任务的员工的 id ，且
- leaveTimei 是员工完成第 i 个任务的时刻。所有 leaveTimei 的值都是 唯一 的。
注意，第 i 个任务在第 (i - 1) 个任务结束后立即开始，且第 0 个任务从时刻 0 开始。
返回处理用时最长的那个任务的员工的 id 。如果存在两个或多个员工同时满足，则返回几人中 最小 的 id 。
遍历即可。
class Solution {
public int hardestWorker(int n, int[][] logs) {
int mxWorker = logs[0][1];
int res = logs[0][0];
for(int i=1;i<logs.length;++i) {
int useTime = logs[i][1] - logs[i-1][1];
if(useTime == mxWorker) res = Math.min(res, logs[i][0]);
if(useTime > mxWorker) {
mxWorker = useTime;
res = logs[i][0];
}
}
return res;
}
}
[Leetcode]2433. 找出前缀异或的原始数组
给你一个长度为 n 的 整数 数组 pref 。找出并返回满足下述条件且长度为 n 的数组 arr ：
pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].
注意 ^ 表示 按位异或（bitwise-xor）运算。
可以证明答案是 唯一 的。
问题本质上是给你前缀和，还原回原数组。
由于前缀和的差分是原数组，因此直接两两异或即可。
class Solution {
public int[] findArray(int[] pref) {
int n = pref.length;
int[] res = new int[n];
res[0] = pref[0];
for(int i=1;i<n;++i) {
res[i] = pref[i-1] ^ pref[i];
}
return res;
}
}
[Leetcode]2434. 使用机器人打印字典序最小的字符串
给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：
- 删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
- 删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。
请你返回纸上能写出的字典序最小的字符串。
贪心模拟。难点是需要记录每次弹出字符后，后续可能会出现的最小字符。
我们首先将题目描述进行转化：有一个初始为空的栈，给定字符的入栈顺序，求字典序最小的出栈序列。
当一个字符入栈后，我们持续检查栈顶元素 c。设还未入栈的字符中，字典序最小的字符是 m，有以下两种情况。
- \(c \le m\)：此时弹出 cc 最优。如果此时按兵不动，下一个出栈的将会是大等于 c 的字符，答案不会变优。
- \(c > m\)：此时不弹出 c，等待后续更小的字符入栈。
所有字符都入栈后，栈内的剩余字符按顺序弹出即可。复杂度 \(\mathcal{O}(n)\)。
class Solution {
public String robotWithString(String s) {
int n = s.length();
int[] f = new int[n+1];
f[n] = 26;
for(int i=n-1;i>=0;--i) f[i] = Math.min(f[i+1], s.charAt(i) - 'a');
ArrayDeque<Character> queue = new ArrayDeque<>();
StringBuilder sb = new StringBuilder();
for(int i=0;i<n;++i) {
queue.push(s.charAt(i));
while(!queue.isEmpty() && queue.peek()-'a' <= f[i+1])
sb.append(queue.poll());
}
return sb.toString();
}
}
[Leetcode] 2435. 矩阵中和能被 K 整除的路径
给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往 下 或者往 右 ，你想要到达终点 (m - 1, n - 1) 。
请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 \(10^9 + 7\) 取余 的结果。
二维动态规划，dp[i][j][t]表示到[i, j]处路径和余k为t的路径数目
状态转移方程为dp[i + 1][j + 1][(grid[i][j] + t) % k] = (dp[i][j + 1][t] + dp[i + 1][j][t]) % mod，但是要判断数组下标是否越界
class Solution {
private int MODE = (int)1e9 + 7;
public int numberOfPaths(int[][] grid, int num) {
int n = grid.length, m = grid[0].length;
int[][][] dp = new int[n+1][m+1][num];
for(int i=1;i<n+1;++i) {
for(int j=1;j<m+1;++j) {
if(i == 1 && j == 1) {
dp[1][1][grid[0][0] % num] = 1;
continue;
}
int mod = grid[i-1][j-1] % num;
for(int k=0;k<num;++k) {
int need = (k+num-mod) % num;
dp[i][j][k] = (dp[i-1][j][need] + dp[i][j-1][need]) % MODE;
}
}
}
return dp[n][m][0];
}
}