leetcode 第 297 场算法比赛 排名37/5915

零、背景

这次比赛比之前的比赛有难度。

也许是这个缘故，我的手速就不是瓶颈点，最后排名比较好，进入前 50 名，具体是 37 名。

一、计算应缴税款总额

题意：给一个税率表，即将正整数划分为若干区间，每个区间会有一个税率。

税率计算公式如下。
如果工资完全覆盖一个税率区间，则扣税是完整的区间金额乘以对应的税率。
如果工资处于一个税率区间，则扣税是超出的金额乘以对应的税率。

现在给你一个工资，问会扣多少税。

思路：税率区间从小到大依次扣税，累计求和即可。

二、网格中的最小路径代价

题意：给一个矩阵，我们可以从上一行的任意一列位置移动到下一行的任意一列位置。
移动代价为移动前的位置值 + 移动后位置的位置值 + 两个值的移动代价。

求从第一行的某列移动到最后一行某列的最小移动代价。

思路：经典的动态规划题。

状态定义f(i, j)：从第一行某列到达第 i 行第 j 列的最低移动代价。

状态转移方程如下：

f(i, j)= min(f(i-1, k) + V[i, j] + C[V[i-1][k]][j])。  

每个状态，只与上一行的所有状态有关，与其他行的状态无关。
所以，我们可以从上到下依次计算每一行的状态。

复杂度：O(n^3)

由于数据量不大，直接暴力计算即可。

三、公平分发饼干

题意：有 n 袋零食包，每包有若干个零食。
现在需要把这个 n 袋零食包分给 k 个人。
对于一袋零食包只能分给一个人，问如何分配，才能是最终某个人获得的零食最大值最小。

思路：数据量不大，暴力排列组合枚举所有情况，计算最小值即可。

四、公司命名

题意：给一些单词列表，现在需要从里面挑两个单词，来尝试拼出一个有效的公司的名字。

有效定义：如果挑选的两个单词的首字母互换，形成的新单词都不再原来的单词列表中，两个单词组成的名字就是有效的

思路：数据量很大，暴力计算的话，肯定会超时。

简单分析一下，发现一个单词是否可以组成公司名的一部分，只有首字母有关。

假设首字母为 a 的单词可以有效替换为首字母为 b 的单词为 A 个。
首字母为 b 的单词可以有效替换为首字母为 a 的单词为 B 个。

则首字母为 a 的单词在前面，首字母为 b 的单词在后面，组成的有效的公司名字是 A*B 个。

所以我们可以预处理每个单词有效替换为另外一个首字母单词的个数。
之后，枚举所有的字母组合，累计求和可以组成的有效公司即可。

五、最后

这次比赛其实还算有难度。
第二题动态规划。
第三题排列组合。
第四题算是综合体。

对于 leetcode ，这次的比赛也许确实会比较难吧。

加油，算法人。

《完》

-EOF-

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