leetcode 第 397 场算法比赛

零、背景

这次比赛最后一题有思路时，通过的人不超过10个。
结果看错题了，没注意到需要输出字典序最小的答案，导致浪费一些时间。
在比赛最后 5 分钟的时候敲完，结果超时了。
vector 换成数组后，就通过了，不过此时比赛已经结束了。

A: 字符统计。
B: 简单一维DP，逆序循环，逆序递归。
C: 简单二维DP，正序逆序都可以。
D: 数位DP。

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

一、两个字符串的排列差

题意：给两个字符串，字符串内字符互不重复，两个字符串集合相同。问两个字符串相同字符的距离和。

思路：统计第一个字符串各字符的位置，第二个字符来计算距离和。

二、从魔法师身上吸取的最大能量

题意：给一个数组，每个位置可以往后跳 K 步，经过的位置元素和为代价，问选择哪个起始位置，跳到最后的代价最小。

思路：简单一维DP。

装填：f(n) 以 n 为起始位置的代价。
状态转移方程：f(n) = V[n] + f(n+k)

求出所有位置为起始位置的代价，求最小值即可。

三、矩阵中的最大得分

题意：给一个二维矩阵，只能向右与向下走，得分为终点值减起始点值，求最大得分。

思路：简单二维DP。

状态1：f(x,y) 以 (x,y)为矩阵右下角的整个左上矩阵的最小值。
状态2: F(x,y) 以(x,y) 为终点的最大得分。

状态1转移方程：f(x,y) = min(V(x,y), f(x-1, y), f(x, y-1))
状态2转移方程：F(x,y) = V(x,y) - min(f(x-1, y), f(x, y-1))

四、找出分数最低的排列

题意：给一个排列，求一个新的排列，使得新的排列的得分最小，如果存在多个，返回字典序最小的的那个。

得分：score(p) = |p[0] - V[p[1]]| + |p[1] - V[p[2]]| + ... + |p[n - 1] - V[p[0]]|

思路：枚举排列必然超时。

超时的原因是存在很多重复子项，所以可以使用二进制位来储存子项状态，从而避免重复计算。

状态定义：f(mask, pi, p0) 第一个枚举数字是 p0, 最后一次枚举数字是 pi 时，剩余子序列 mask 的最优答案。

f(mask, pi, p0)=
  |pi - V[p[i]]| 
+ |p[i] - V[p[i]]| 
  ... 
+ |p[n - 1] - V[p0]|

状态转移方程：枚举 mask 的所有值数字，递归计算，保留最小值。

状态个数：O(1<<14 * 14 * 14)
时间复杂度：O(1<<14 * 14 * 14 * 14)

上面这个算法，我使用 vector 竟然超时了。
比赛的时候，我是选择把 vector 换成数组来通过这道题的。

写题解时，观察排列，循环左右移动，竟然不影响答案。
所以字典项最小的肯定是以 0 开始的，即枚举 0 肯定可以得到最优答案。
因此，对于第一项，直接枚举 0 即可，复杂度降低一个数量级。
这样 vector 也可以通过这道题了。

五、最后

这次比赛最后一题有点可惜，比赛是算法常数有点大，超时了。

《完》

-EOF-

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