leetcode 第 314 场算法比赛

零、背景

四道题都很简单。

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

题意：按时间顺序给出任务的完成时间，上个任务完成时下个任务才开始。
第一个任务开始时间是 0 时刻，问处理时间最长的那个任务，如果有多个，输出id 较小的那个。

思路：循环计算出任务时长，比大小即可。

二、找出前缀异或的原始数组

题意：给出一个数组所有的前缀异或值，求原数组。

思路：相邻前缀异或值进行异或，就可以得到后面位置的值。
循环进行异或即可。

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

题意：给一个字符串 s 和一个空字符串 t，有两个操作：
1）将 s 字符串的首个字母移动到 t 字符串最后。
2）将 t 字符串最后的字符删除。
求删除的字符顺序的最小字典序。

思路：

对于 t 串，后进先出，是一个栈。
栈删除字母的顺序是固定的。

对于 s 串，可以通过栈来调整删除字母的顺序，顺序是可以调整的。

想要字典序最小，删除的首个字母肯定是整个串中最小的。
所以可以按下面步骤操作。

1) 循环删除 t 串，直到遇到第一个最小的字符，并删除。
2) 最小的删除后，对于栈下个删除的是栈顶字符，对于 s 串，可以选择剩余里面最小的字符。
2.1) 如果栈顶更小，那就删除栈顶。此时依旧在步骤 2 里面判断。
2.2) 如果 s 串中的更小，则进入步骤1 进行操作。

对于上面的算法，需要从后到前预处理得到 s 后缀中的第一个最小字符的位置。

复杂度：O(n)

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

题意：给一个矩阵，问从左上角到右下角的路径和里，可以整除 K 的路径有多少。

思路：动态规划。

状态定义： dp(k, x, y) 代表从左上角到 (x,y) 的路径和为 k 的路径数。

状态转移方程：

dp(k, x, y) = dp(k-val(x,y), x-1, y) + dp(k-val(x,y), x, y-1)

五、最后

这次比赛的题目很简单，第三题比第四题难点。

Leetcode 秋季团队赛的题解晚点才能写出来，如果一周内没写出来，那可能就不会写了。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code