leetcode第318场周赛：模拟专场、又见安排邮筒问题

字数统计: 4.8k字 | 阅读时长: 20分

2022-11-06

摘要: 本文是 leetcode 第 318 周赛的记录。主要涉及的算法包括模拟、滑动窗口、哈希表、堆、动态规划

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

总览

2022 年 11 月 06 日进行了 leetcode 第 318 场周赛，之前参加了这场比赛但是文章一直拖着没有写，这里补一下。本场比赛由 Airwallex 空中云汇公司赞助，奖品如下：

工作机会奖励力度还是挺大的，一般都是前 200 名给内推，这里直接前 300 给内推，前 5 免第一轮笔试。

Airwallex 空中云汇是一家金融科技公司。通过搭建数字化的跨境支付和金融基础设施，助力企业进行线上收单，实现全球收付款并简化企业的财务运营，以一站式的科技平台帮助现代化企业实现全球业务成长。2015 年成立，目前 E 轮融资估值 55 亿美元，全球 19 个办公地，共 1200 员工。中国在北京、上海、深圳都有，业务覆盖亚太、欧洲、北美。详见官网：

1	https://www.airwallex.com.cn/

本场比赛的前三题比较简单，考察了模拟, 滑动窗口、堆、哈希表等基础算法点，第四题用双串线性 DP 解决，但是状态设计以及对应的最优子结构依赖于一些数学性质，类似于安排邮筒的问题，比赛时没写出来。

成绩如下：

由于第四题挺难的，这次比赛 45 分钟（含罚时）解决三个题的名词还是挺靠前的，635/5670。当年的 5670 参赛人数现在看来也是小高峰了，但在 2022 年也就是普通，现在不论经济还是行业都进入下行周期，leetcode 周赛的参赛人数基本回落到 3500 左右了。以后有时间可以多参加参加周赛，以侧面感受算法技术穿越牛熊的过程。

另外第四题还有很多优化的解法，涉及一些高阶的算法点，比如双端队列优化DP、决策单调性、模拟费用流等。本文不涉及。

各个题目涉及到的知识点汇总如下：

A题: 模拟
- 参考: leetcode模拟问题汇总
B题: 滑动窗口、哈希表
- 参考: 滑动窗口
C题: 模拟、堆
- 参考: 二叉堆
D题: 动态规划
- 参考: 货仓选址与安排邮筒

往期参加比赛的记录如下：

【连载】leetcode周赛

A 题

2460. 对数组执行操作

给你一个下标从 0 开始的数组 nums ，数组大小为 n ，且由非负整数组成。

你需要对数组执行 n - 1 步操作，其中第 i 步操作（从 0 开始计数）要求对 nums 中第 i 个元素执行下述指令：

如果 nums[i] == nums[i + 1] ，则 nums[i] 的值变成原来的 2 倍，nums[i + 1] 的值变成 0 。否则，跳过这步操作。
在执行完全部操作后，将所有 0 移动到数组的末尾。

例如，数组 [1,0,2,0,0,1] 将所有 0 移动到末尾后变为 [1,2,1,0,0,0] 。
返回结果数组。

注意操作应当依次有序执行，而不是一次性全部执行。

提示：

1 2	2 <= nums.length <= 2000 0 <= nums[i] <= 1000

示例 1：
输入：nums = [1,2,2,1,1,0]
输出：[1,4,2,0,0,0]
解释：执行以下操作：

i = 0: nums[0] 和 nums[1] 不相等，跳过这步操作。

i = 1: nums[1] 和 nums[2] 相等，nums[1] 的值变成原来的 2 倍，nums[2] 的值变成 0 。数组变成 [1,4,0,1,1,0] 。

i = 2: nums[2] 和 nums[3] 不相等，所以跳过这步操作。

i = 3: nums[3] 和 nums[4] 相等，nums[3] 的值变成原来的 2 倍，nums[4] 的值变成 0 。数组变成 [1,4,0,2,0,0] 。

i = 4: nums[4] 和 nums[5] 相等，nums[4] 的值变成原来的 2 倍，nums[5] 的值变成 0 。数组变成 [1,4,0,2,0,0] 。
执行完所有操作后，将 0 全部移动到数组末尾，得到结果数组 [1,4,2,0,0,0] 。

示例 2：
输入：nums = [0,1]
输出：[1,0]
解释：无法执行任何操作，只需要将 0 移动到末尾。

算法: 模拟

按要求模拟即可。

代码(C++)

class Solution {
public:
    vector<int> applyOperations(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n - 1; ++i)
        {
            if(nums[i] == nums[i + 1])
            {
                nums[i] *= 2;
                nums[i + 1] = 0;
            }
        }
        vector<int> result(n);
        int j = 0;
        for(int i = 0; i < n; ++i)
            if(nums[i] != 0)
                result[j++] = nums[i];

        return result;
    }
};

B 题

2461. 长度为 K 子数组中的最大和

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

子数组的长度是 k，且
子数组中的所有元素各不相同。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

子数组是数组中一段连续非空的元素序列。

提示：

1 2	1 <= k <= nums.length <= 1e5 1 <= nums[i] <= 1e5

示例 1：
输入：nums = [1,5,4,2,9,9,9], k = 3
输出：15
解释：nums 中长度为 3 的子数组是：

[1,5,4] 满足全部条件，和为 10 。

[5,4,2] 满足全部条件，和为 11 。

[4,2,9] 满足全部条件，和为 15 。

[2,9,9] 不满足全部条件，因为元素 9 出现重复。

[9,9,9] 不满足全部条件，因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。

示例 2：
输入：nums = [4,4,4], k = 3
输出：0
解释：nums 中长度为 3 的子数组是：

[4,4,4] 不满足全部条件，因为元素 4 出现重复。
因为不存在满足全部条件的子数组，所以返回 0 。

算法: 定长滑动窗口、哈希表

在文章滑动窗口中我们系统总结过定长滑动窗口的题目。一般这种定长滑动窗口的题目，在推进两个指针的过程中，一般都有辅助数据结构，这里用的是哈希表。

代码(C++)

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> mapping;
        long long sum = 0;
        long long ans = 0;
        for(int i = 0; i < k; ++i)
        {
            sum += nums[i];
            mapping[nums[i]]++;
        }
        if(mapping.size() == k)
            ans = max(ans, sum);
        for(int i = k; i < n; ++i)
        {
            sum -= nums[i - k];
            mapping[nums[i - k]]--;
            if(mapping[nums[i - k]] == 0)
                mapping.erase(nums[i - k]);
            sum += nums[i];
            mapping[nums[i]]++;
            if(mapping.size() == k)
                ans = max(ans, sum);
        }
        return ans;
    }
};

C 题

2462. 雇佣 K 位工人的总代价

给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。

同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人：

总共进行 k 轮雇佣，且每一轮恰好雇佣一位工人。
在每一轮雇佣中，从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
- 比方说，costs = [3,2,7,7,1,2] 且 candidates = 2 ，第一轮雇佣中，我们选择第 4 位工人，因为他的代价最小 [3,2,7,7,1,2] 。
- 第二轮雇佣，我们选择第 1 位工人，因为他们的代价与第 4 位工人一样都是最小代价，而且下标更小，[3,2,7,7,2] 。注意每一轮雇佣后，剩余工人的下标可能会发生变化。
如果剩余员工数目不足 candidates 人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
一位工人只能被选择一次。

返回雇佣恰好 k 位工人的总代价。

提示：

1
2
3

1 <= costs.length <= 1e5 
1 <= costs[i] <= 1e5
1 <= k, candidates <= costs.length

示例 1：
输入：costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
输出：11
解释：我们总共雇佣 3 位工人。总代价一开始为 0 。

第一轮雇佣，我们从 [17,12,10,2,7,2,11,20,8] 中选择。最小代价是 2 ，有两位工人，我们选择下标更小的一位工人，即第 3 位工人。总代价是 0 + 2 = 2 。

第二轮雇佣，我们从 [17,12,10,7,2,11,20,8] 中选择。最小代价是 2 ，下标为 4 ，总代价是 2 + 2 = 4 。

第三轮雇佣，我们从 [17,12,10,7,11,20,8] 中选择，最小代价是 7 ，下标为 3 ，总代价是 4 + 7 = 11 。注意下标为 3 的工人同时在最前面和最后面 4 位工人中。
总雇佣代价是 11 。

示例 2：
输入：costs = [1,2,4,1], k = 3, candidates = 3
输出：4
解释：我们总共雇佣 3 位工人。总代价一开始为 0 。

第一轮雇佣，我们从 [1,2,4,1] 中选择。最小代价为 1 ，有两位工人，我们选择下标更小的一位工人，即第 0 位工人，总代价是 0 + 1 = 1 。注意，下标为 1 和 2 的工人同时在最前面和最后面 3 位工人中。

第二轮雇佣，我们从 [2,4,1] 中选择。最小代价为 1 ，下标为 2 ，总代价是 1 + 1 = 2 。

第三轮雇佣，少于 3 位工人，我们从剩余工人 [2,4] 中选择。最小代价是 2 ，下标为 0 。总代价为 2 + 2 = 4 。
总雇佣代价是 4 。

算法: 模拟、堆

本题的本质是一道模拟题，题目中把模拟过程已经明确给出了，按照给定的描述进行模拟即可。

过程中维护一个候选池子，每一轮从池子中选择一位工人，共执行 k 轮选择。选择的标准是代价最小，下标更小。这一步需要用堆来维护候选池子。

池子是前 candidates 位以及后 candidates 位。每一轮选择后，根据所选工人是前半部分还是后半部分，从对应的部分中补一位进入池子。

代码(C++)

struct Item {
    int idx;
    int cost;
    Item(){}
    Item(int idx, int cost):idx(idx),cost(cost){}
    bool operator<(const Item& item) const
    {
        if(cost == item.cost)
            return idx > item.idx;
        return cost > item.cost;
    }
};

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        int n = costs.size();
        int left = candidates - 1;
        int right = n - candidates;
        priority_queue<Item> pq;
        if(right - left > 1)
        {
            for(int i = 0; i <= left; ++i)
                pq.push(Item(i, costs[i]));
            for(int i = right; i < n; ++i)
                pq.push(Item(i, costs[i]));
        }
        else
        {
            for(int i = 0; i < n; ++i)
                pq.push(Item(i, costs[i]));
        }

        long long ans = 0;
        while(k > 0)
        {
            Item cur = pq.top();
            pq.pop();
            ans += cur.cost;
            --k;
            if(right - left <= 1)
                continue;
            if(cur.idx <= left)
            {
                ++left;
                pq.push(Item(left, costs[left]));
            }
            else
            {
                --right;
                pq.push(Item(right, costs[right]));
            }
        }
        return ans;
    }
};

D 题

2463. 最小移动总距离

X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ，其中 factory[j] = [positionj, limitj] ，表示第 j 个工厂的位置在 positionj ，且第 j 个工厂最多可以修理 limitj 个机器人。

每个机器人所在的位置互不相同。每个工厂所在的位置也互不相同。注意一个机器人可能一开始跟一个工厂在相同的位置。

所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向。当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动。

任何时刻，你都可以设置部分机器人的移动方向。你的目标是最小化所有机器人总的移动距离。

请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。

注意：

所有机器人移动速度相同。
如果两个机器人移动方向相同，它们永远不会碰撞。
如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过。
如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动。
机器人从位置 x 到位置 y 的移动距离为 |y - x| 。

提示：

1 <= robot.length, factory.length <= 100
factory[j].length == 2
-1e9 <= robot[i], positionj <= 1e9
0 <= limitj <= robot.length
测试数据保证所有机器人都可以被维修。

示例 1：

输入：robot = [0,4,6], factory = [[2,2],[6,2]]
输出：4
解释：如上图所示：

第一个机器人从位置 0 沿着正方向移动，在第一个工厂处维修。

第二个机器人从位置 4 沿着负方向移动，在第一个工厂处维修。

第三个机器人在位置 6 被第二个工厂维修，它不需要移动。
第一个工厂的维修上限是 2 ，它维修了 2 个机器人。
第二个工厂的维修上限是 2 ，它维修了 1 个机器人。
总移动距离是 |2 - 0| + |2 - 4| + |6 - 6| = 4 。没有办法得到比 4 更少的总移动距离。

示例 2：

输入：robot = [1,-1], factory = [[-2,1],[2,1]]
输出：2
解释：如上图所示：

第一个机器人从位置 1 沿着正方向移动，在第二个工厂处维修。

第二个机器人在位置 -1 沿着负方向移动，在第一个工厂处维修。
第一个工厂的维修上限是 1 ，它维修了 1 个机器人。
第二个工厂的维修上限是 1 ，它维修了 1 个机器人。
总移动距离是 |2 - 1| + |(-2) - (-1)| = 2 。没有办法得到比 2 更少的总移动距离。

算法: 动态规划

类似题目货仓选址与安排邮筒。

在安排邮筒的题目中，给出了 n 个房屋的位置，安排 k 个邮筒，k 个邮筒随便放，使得房屋到邮筒的距离之和最小。

定义 $dp[i][k]$ 表示对于前 $i$ 个房屋，安排 $k$ 个邮筒解决前 $i$ 个房屋的最小距离和。

每个邮筒会覆盖一段连续的范围，假如两个邮筒 T1，T2 相邻，它们分别负责数轴上一段连续的房子，如下图：

假如 $T_{1} < T_{2}$，而 $x_{i}$ 由 $T_{1}$ 负责，$x_{j}$ 由 $T_{2}$ 负责，那么为了让距离和最小就就一定有 $x_{i} < x_{j}$。

由于以上每个邮筒的覆盖范围连续的特性，$k$ 个邮筒如何负责前 $i$ 个房屋就容易枚举出来了。

对于本题，一个自然的想法是把工厂视为邮筒，把机器人视为房子。本题与上面安排邮筒问题的房子都是固定的，区别在于邮筒。

上面的问题中邮筒容量无限，且可以改变位置，而本题中邮筒位置固定，且有容量限制，这就造成了一个房子 $x$ 离某个邮筒 $T$ 最近，但是邮筒 $T$ 却不能负责房子 $x$ 的情况。

但本题中邮筒覆盖的范围依然具有连续的特性，也就是假如 $T_{1}$，$T_{2}$ 是两个邮筒，它们在各自能力范围内分别负责数轴上的一些房子，还是下面的图：

假如 $x_{i}$ 由 $T_{1}$ 负责（隐含了 $T_{1}$ 有服务能力）、$x_{j}$ 由 $T_{2}$ 负责（隐含了 $T_{2}$ 有服务能力），$T_{1} < T_{2}$，那么就一定有 $x_{i} < x_{j}$。

因为如果 $x_{i} > x_{j}$，由于 $T_{1}$ 和 $T_{2}$ 各自有服务至少一个的能力，那么将服务对象改为 $T_{2}$ 服务 $x_{i}$、$T_{1}$ 服务 $x_{j}$，由于各邮筒（工厂）位置不重合，各房子（机器人）位置也不重合，最终的距离和不会更大，有可能会更小。也就是以下不等式：

$|T_{1} - x_{i}| + |T_{2} - x_{j}| \leq |T_{1} - x_{j}| + |T_{2} - x_{i}| \quad\quad (T_{1} < T_{2}, x_{i} < x_{j})$

按照 $T_{1} < T_{2}$ 与 $x_{i} < x_{j}$ 的位置关系分类讨论将绝对值打开，可以证明以上不等式。

因此，每个工厂修复的机器人都是连续的一段，这里工厂的容量不一定用满，比如工厂如果修复了 3 个机器人，那这 3 个一定是挨着的。

后面动态规划的最优子结构需要基于以上特性。

将工厂位置与机器人位置排序。

然后将每个工厂的容量展开，比如 factory[i] 的位置为 p，容量为 c，那么就将其视为有 c 个工厂，每个的位置都是 p，展开后的工厂位置记为 fac_pos，长度为 m。

预处理工厂 fac_pos[j] 到机器人 robot[i] 的距离 d[i][j]。

仿照安排邮筒问题，定义 $dp[i][j]$ 表示使用 fac_pos[0..j] 这些工厂负责 robot[0..i] 这些机器人的最小距离和。

我们要求的答案就是 dp[n - 1][m - 1]，初始值如下：

$dp[i][i] = \sum\limits_{k=0}\limits^{k=i}d[k][k]$

状态转移时有两种决策，一种是 robot[i] 由 fac_pos[j] 负责，此时 dp[i][j] = dp[i - 1][j - 1] + d[i][j]；另一种是 robot[i] 不由 fac_pos[j] 负责，此时 dp[i][j] = dp[i][j - 1]，综上，状态转移方程如下：

$dp[i][j] = \min (dp[i-1][j-1] + d[i][j], dp[i][j - 1])$

代码(C++)

时间复杂度 $O(N^{2}M)$，$N$ 为 robot 长度，$M$ 为 factory 长度。

using ll = long long;

class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(robot.begin(), robot.end());
        sort(factory.begin(), factory.end());
        int n = robot.size();
        vector<int> fac_pos;
        for(const vector<int>& fac: factory)
        {
            for(int i = 0; i < fac[1]; ++i)
                fac_pos.push_back(fac[0]);
        }
        int m = fac_pos.size();
        vector<vector<ll>> d(n, vector<ll>(m));
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                d[i][j] = abs(robot[i] - fac_pos[j]);
            }

        // dp[i][j] := robot[0..i] 由 factory[0..j] 负责，最短距离和。需要 i <= j
        vector<vector<ll>> dp(n, vector<ll>(m));
        dp[0][0] = d[0][0];
        for(int i = 1; i < n; ++i)
            dp[i][i] = dp[i - 1][i - 1] + d[i][i];
        for(int i = 0; i < n; ++i)
        {
            for(int j = i + 1; j < m; ++j)
            {
                dp[i][j] = dp[i][j - 1];
                if(i > 0)
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + d[i][j]);
                else
                    dp[i][j] = min(dp[i][j], d[i][j]);
            }
        }
        return dp[n - 1][m - 1];
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法leetcode

leetcode第318场周赛：模拟专场、又见安排邮筒问题

总览

A 题

算法: 模拟

代码(C++)

B 题

算法: 定长滑动窗口、哈希表

代码(C++)

C 题

算法: 模拟、堆

代码(C++)

D 题

算法: 动态规划

代码(C++)