leetcode 第 394 场算法比赛

零、背景

这次比赛题目不难，都做完了，但是手速平不过大家。

A: 统计题。
B: 统计题。
C: 动态规划。
D: 最短路。

排名：320
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/3/394

一、统计特殊字母的数量 I

题意：给一个字符串，问大小写字母同时出现的字母个数。

思路：字母放入到集合里，枚举所有字母，判断大小写字母是否都出现。

二、统计特殊字母的数量 II

题意：给一个字符串，问哪些字母大小写都出现，且小写字母都出现在大写字母前面。

思路：统计聚合每个字母出现的位置列表与大小写，然后枚举判断每个字母是否都出现大小写且小写字母都在前面。

优化1：聚合字母时，相邻字母大小写相同，可以保留一个即可。
优化2：优化1去重合，聚合的字母个数大于2时显然不是答案，不需要再聚合。

优化后，空间复杂度由 O(n) 降低到 O(26)

三、使矩阵满足条件的最少操作次数

题意：给一个矩阵，可以修改一位置的元素值，问至少修改多少个，可以使得所有列的值相等，相邻列的值不等。

思路：动态规划。

值数据范围：[0,9]

显然，每一列的值要么是 [0,9]，极端情况下，可能值都被使用，所以下一列就需要使用数据范围之外的其他任意值，不妨用 10 表示。
极端情况下，相邻列可能都是任意值，所以至少需要两个任意值，分别使用 10 和 11 表示。

总结下，数据的值范围变成了 [0,11]。

状态定义：dp[i][v] 第 i 列值都为 v 时前 i 列的最小修改次数。

状态转移方程：dp[i][v] = min(dp[i-1][V] + n - count[i][v])

方程含义：第i列值都是v时，当前列的代价是 n - count[i][v]。
当前状态可以由前一列值不是 v 的状态转移得到，所有状态里取 min。

预处理：count[i][v] 可以预处理统计得到。

复杂度：O(12 * 12 * m)

思考题1：是否可以证明只使用 [0,9] 就可以构造出最优答案。
思考题2：值范围很大时，如何处理呢？

四、最短路径中的边

题意：给一个无向带权重的图，起点到终点有一个最短路，问哪些边在最短路的路径上。

思路：使用 Dijkstra 计算出所有单源最短路 dist 数组。

模板：https://github.com/tiankonguse/leetcode-solutions/blob/master/doc/graph/dijkstra.cpp

如果起点与终点联通，则 dfs 重点寻找路径上的边。

dfs 条件：假设当前点 a 在路径上，则所有相邻边 b 需要满足 dist[b] + cost[a,b] = dist[a]。
满足了，则前驱 b 也是路径的点，递归处理即可。

五、最后

这次比赛比较简单，动态规划倒是有两个思考题，大家可以思考一下。

思考题1：是否可以证明只使用 [0,9] 就可以构造出最优答案。
思考题2：值范围很大时，如何处理呢？

《完》

-EOF-

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