前言

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人，人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。

整体评价

哈哈，手速场，t3思维题，t4经典DP，感觉大家都变强了。

附带上比赛时的第一次AC代码(Java，Go为后续补充)，不优雅之处请包容.

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

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

简单模拟题，但是易错，因为编号是打散的.

时间复杂度为 $O (n)$

Java

class Solution {
    
    public int hardestWorker(int n, int[][] logs) {

        int ltime = 0, ans = -1;
        int last = 0;
        for (int[] log: logs) {
            if (log[1] - last > ltime) {
                ltime = log[1] - last;
                ans = log[0];
            } else if (log[1] - last == ltime && log[0] < ans) {
                ans = log[0];
            }
            last = log[1];
        }
        
        return ans;
        
    }
    
}

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

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

还原题吧，经典异或特性，偶数次出现为0，奇数次出现为本身

时间复杂度为 $O (n)$

Java

class Solution {
    
    public int[] findArray(int[] pref) {
        int n = pref.length;
        int[] res = new int[n];
        res[0] = pref[0];
        
        int xor = res[0];
        for (int i = 1; i < n; i++) {
            res[i] = xor ^ pref[i];
            xor ^= res[i];
        }
        
        return res;
        
    }
    
}

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

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

可以注意字符串t的操作描述，尾部追加，尾部弹出，FILO，这不是栈吗？

思维的难度，主要在于字符串最小的构造上，这题妥妥的贪心，历来贪心解不好证明.

这题从弹栈顶的角度出发，就容易搞定，只要判定该栈顶元素，比后续的元素都要小于/等于，则弹出，这样的贪心策略，一定可以构建最小字符串。

把握这个原则，就能把这题构造出来了。

不过这边最小值判定，用了字母表计数hash，一次需要 $O (26)$

整体的时间复杂度为 $O (26 n)$ , 这部分可以优化。

Java

class Solution {
    
    boolean isSmall(int[] tabs, char c) {
        int p = c - 'a';
        for (int i = 0; i < p; i++) {
            if (tabs[i] > 0) return false;
        }
        return true;
    }
    
    // 栈的使用吗？贪心？
    public String robotWithString(String s) {
        
        char[] buf = s.toCharArray();
        
        int[] tabs = new int[26];
        for (char c: buf) {
            tabs[c - 'a']++;
        }
        
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < buf.length; i++) {
            stack.push(buf[i]);
            tabs[buf[i] - 'a']--;
            
            while (!stack.isEmpty() && isSmall(tabs, stack.peek())) {
                sb.append(stack.peek());
                stack.pop();
            }
        }
        while (!stack.isEmpty()) {
            sb.append(stack.peek());
            stack.pop();
        }
        
        return sb.toString();
        
        
    }
    
}

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

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

经典DP题，k值较小，就取同余。

构建三维DP， $o pt [s] [i] [j], s 为路径和对 k 取余后的值， i 为行， j 为列$

$o pt [(s + g r i d [i] [j]) % k] [i] [j] = o pt [s] [i - 1] [j] + o pt [s] [i] [j - 1]$

初始为 $o pt [g r i d [0] [0] % k] [0] [0] = 1$

最终结果为 $o pt [0] [n - 1] [m - 1]$

总的时间复杂度为 $O (mnk)$

写的不是那么优雅，for循环有点多，T_T.

Java

class Solution {
    
    final int mod = 10_0000_0007;
    
    public int numberOfPaths(int[][] grid, int k) {

        int r = grid.length;
        int c = grid[0].length;
        
        int[][][] opt = new int[k + 1][r][c];
        
        opt[grid[0][0] % k][0][0] = 1;
        
        
        for (int i = 1; i < c; i++) {
            int v = grid[0][i];
            for (int j = 0; j < k; j++) {
                opt[(v + j) % k][0][i] = (opt[(v + j) % k][0][i] + opt[j][0][i - 1]) % mod;
            }
        }
        
        for (int i = 1; i < r; i++) {
            for (int j = 0; j < c; j++) {
                int v = grid[i][j];
                for (int t = 0; t < k; t++) {
                    if (j > 0)
                        opt[(v + t) % k][i][j] = (opt[(t + v) % k][i][j] + opt[t][i][j - 1]) % mod;
                }
                
                // 来自上方
                for (int t = 0; t < k; t++) {
                    opt[(v + t) % k][i][j] = (opt[(t + v) % k][i][j] + opt[t][i - 1][j]) % mod;
                }
            }
        }
        
        return opt[0][r - 1][c - 1];
        
    }
    
}