leetcode 第 295 场算法比赛 排名68/6444

零、背景

这次比赛我喜欢，因为第三题有难度，这样我的手速就不是问题了。

遗憾的是，昨天晚上运动完就半夜十二点多了，之后又约朋友去吃夜宵，吃到两点多。
回来洗澡、做了两个攀岩视频、刷了一会短视频，睡的就非常晚。

今天早上起来头脑昏沉沉的，比赛就拖沓了，错误百出。

我想好了，以后要进行时间管理，保证睡眠。

一、重排字符形成目标字符串

题意：给一个字符串，问挑出的字符可以组成几个目标字符串。

思路：木桶短板理论，统计每个字母并相除分别计算当前单词可以组成几个，取最小值即可。

二、价格减免

题意：给一个单词由空格连接组成的句子，对于 $[0-9]+ 的单词，是价格，需要进行打折。
打折后的价格单词格式是 $[0-9]+.[0-9]{2}，即保留两位小数。
求打折后的句子。

思路：分隔单词，依次判断是否是价格，是了进行打折转化即可。

注意实现：使用 long long 进行计算，否则会越界。

三、使数组按非递减顺序排列

题意：给一个数组，每一轮按照规则删除一些数字，问最多删除几轮后，数组就保持不变了。
删除规则：对于相邻两个数字，如果前一个大于后一个，删除后一个。

样例：5 3 4 2
第一轮删除：5 4
第二轮删除：5

思路：循环模拟，最坏复杂度是O(n^2)。

比赛的时候，我最开始尝试使用 map 记录需要删除的索引，复杂度O(n)。

敲了一半时突然发现可以使用单调栈来贪心，于是代码删除重写。
可能贪心没想好，提交后错误了一次，于是只好老老实实使用索引法来做了。

所谓的索引，就是需要删除节点的上个节点。
索引法的复杂度分析：遍历索引法的一个节点就删除一个数字，最多遍历 n 次。
故索引法的总复杂度为 O(n)

四、到达角落需要移除障碍物的最小数目

题意：给一个矩阵，有一些障碍物，问至少删除多少个障碍物才能从左上角到达右下角。

思路：大水题，矩阵转化为图，就是求最小路径了。

一个优先队列搞定。

五、最后

这次比赛我喜欢，可惜我没状态，没能进去前 50 名，遗憾。

加油，算法人。

《完》

-EOF-

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