leetcode 第 308 场算法比赛

零、背景

这次比赛题目都比较简单，又到拼手速的时候了。

这次比赛不少题还有多种思路，然后就会纠结使用哪种，犹豫就会败北。

一、和有限的最长子序列

题意：给一个数组，以及若干询问。
求子序列和不超过询问值的最大长度。

思路：子序列对数组元素的顺序无要求，答案肯定由最小的元素集合组成。
所以可以对数组排序，预处理出所有前缀和。

方法一：枚举。
对于每个询问，从前到后枚举前缀和，找到最后一个满足大小的长度。

方法二：二分查找。
对于每个询问，使用 upper_bound - 1 来代替二分查找即可。

二、从字符串中移除星号

题意：给一个含有星号的字符串。
每个星号字符可以消除左部相邻的非星号字符。
所有星号消除完字符后，求剩余的字符串。

思路：维护一个栈即可。

三、收集垃圾的最少总时间

题意：垃圾分为金属、纸和玻璃三个分类，给出 n 个垃圾堆三种垃圾个数，以及相邻垃圾堆之间的距离。
收集一个垃圾的代价是1，垃圾车行驶一单位距离的代价也是1。
三个垃圾车从 0 号垃圾堆触发，顺序去收集垃圾，问收集完所有垃圾的最小代价是多少？

思路：对于三个分类的垃圾个数，直接求和即可。
三个垃圾车的行驶距离肯定是该分类垃圾所在的最后一个垃圾堆。

所以找到每个分类垃圾最后出现的位置，求前缀距离和即可。

四、给定条件下构造矩阵

题意：n个互不相同的数字，放在 n*n 的矩阵中。
现在给出数字行之间的上下关系，以及列之间的左右关系。
求构造出符号关系的矩阵，不存在返回空。

思路：每行和每类互相独立，分别计算拓扑关系。

如果行和列拓扑关系不存在环，则存在答案。

确定拓扑关系后，行和列随意生成一组顺序。
每个数字在行和列中的位置，就是矩阵的下标。

五、最后

这次比赛很简单，最后一题给大家出一个扩展题：求满足关系的矩阵个数。

加油，算法人。

《完》

-EOF-

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