leetcode 第 294 场算法比赛

零、背景

这次比赛最后一题有点难度，我很喜欢。

但是我思路比较混乱，比赛期间没做出来，比较遗憾。

复盘一下是因为公式太复杂。
而我只是纸上简单画一下，大脑里推导出公式，没有在纸上写出完整的公式。
最终导致反复在大脑中推导公式，竟然来了四五轮。

赛后，耐下心来纸上写出完整的公式，一下就通过了。

一、字母在字符串中的百分比

题意：问指定的字符出现的频率。

思路：循环统计，除以总个数即可。

二、装满石头的背包的最大数量

题意：有若干容量有限的背包和石头，问最多可以装满多少个背包。

思路：背包排序，从小到大装即可。

三、表示一个折线图的最少线段数

题意：给若干坐标，问从头到尾连线，有多少线段。

思路：按横坐标轴排序，然后判断相邻三点是否在一条直线上即可。

PS：昨晚睡得晚，网页上修改完代码后，本地没修改，导致这道题我错了四次。

四、巫师的总力量和

题意：给一个数组，求所有子数组的魔法值之和。
子数组魔法值定义：子数组之和乘以子数组的最小值。

思路：有O(n^2)个子数组，数据范围是10^5，显然不能暴力计算。

所以我们需要思考，如何才能在 O(n) 或者 O(n log(n)) 时间复杂度内计算出答案。

要降低复杂度，必然涉及到不同子数组之间有公共部分，可以进行合并计算。

显然，公共部分就是最小值，最小值相等的子数组，可以累积求和，最后再乘以这个最小值。

所以问题转化为了，枚举每个位置的值，快速求出以这个位置为最小值的子数组之和的和。

对于这个子问题，其实纸上画画也不难，先求出所有当前最小值为后缀的和，然后是后面一个的和，直到最后一个。
之后就是合并通用项，最终可以推导出一个公式来。

推导过程如下图：

注意实现：对于相等的两个，我们可以定义左边的更小。
即有子数组覆盖两个最小值时，这个子数组划分到左边的最小值。

五、最后

这次比赛第三题太不细心了，第四题没有在纸上推导出公式，只在大脑里推导，吃了大亏。

经验总结就是，以后要细心，以后要先在纸上推导出公式。

加油，算法人。

《完》

-EOF-

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