leetcode 第 430 场算法比赛，排名44

背景

这次比赛难度增加了不少，不需要和大家拼手速了。
但不幸的是我感冒了，最终排名 44，不感冒的话应该可以更靠前。

A: 签到题
B: 暴力或后缀数组 C: 枚举+前缀统计
D: 找规律(动态规划)

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

Q1. 使每一列严格递增的最少操作次数

题意：给一个矩阵，每次可以选择一个位置加1，问最少多少次可以所得所有列严格递增。

思路：贪心

枚举每一列，从小到大判断，如果不满足，就加到满足，加的次数是 a[i-1]+1 - a[i]。

Q2. 从盒子中找出字典序最大的字符串

题意：给一个长度为 n 的字符串，拆分为 k 个非空子串，问所有拆分中，字典序最大的子串是哪个。

前提：拆分为k个非空子串，子串的最长长度为 n-(k-1)。

思路1：暴力枚举

枚举位置为起始位置的子串，判断是否比当前答案更优。
复杂度：O(n^2)

思路2：后缀数组
复杂度：O(n log(n))

显然字典序最大的就是后缀数组中排名最后的那个，即取 rk[n-1]。
然后判断这个位置的子串是否大于n-(k-1)，大于了进行截断即可。

word.push_back('$');
SuffixArray(str, n, sa, rk);
// BuildHeight(str, n, sa, rk, height);
// BuildST(height, st);
int p = sa[n - 1];
int maxLen = n - 1 - (m - 1);
word.pop_back();
return word.substr(p, maxLen);

PS：后面有机会了，单独写一篇文章分享一下后缀数组。

Q3. 统计特殊子序列的数目

题意：給一个数组，问存在多少四元组，满足下面关系。

p + 1 < q 
q + 1 < r 
r + 1 < s
V[p] * V[r] == V[q] * V[s]

思路：枚举

等式四个位置的顺序不是有序的，所以需要转换一下，如下

V[p] / V[q] == V[s] / V[r]

基本思路是枚举 r 和 s，看前面有多少个 V[p] / V[q]满足答案。

由于V[p] / V[q]是除法，存在小数，所以需要保存二元组 {V[p], V[q]}。
又由于二元组同时乘以一个数字不影响除法的结果，所以需要除以 gcd，保存最简二元组。

对于二元组，我使用 hash 储存的。

unordered_map<ll, ll> H;
ll Hash(int a, int b) { return a * 10000 + b; }

然后，枚举 r， 更新前缀的统计，再枚举 s 看有多少答案。

for (int p2 = 0; p2 < n; p2++) {
  // update p0 / p1
  int p1 = p2 - 2;
  for (int p0 = 0; p0 + 1 < p1; p0++) {
    Add(nums[p0], nums[p1]);
  }
  // search p3 / p2
  for (int p3 = p2 + 2; p3 < n; p3++) {
    ans += Search(nums[p3], nums[p2]);
  }
}

Q4. 统计恰好有 K 个相等相邻元素的数组数目

题意：问可以构造多少个长度为n，值域为m，恰好有 k个相邻元素相等的数组。

思路：动态规划

状态定义: f(n,k,v) 最后一个元素值为v时的最优值

状态转移方程

i = [0,m-1] && i != v
f(n,k,v) = f(n-1,k-1,v) + sum(f(n-1,k,i))

方程解释：要么前一个元素相等，则k 少一个，要么前一个元素不等，则k不变。
不等时，共有 m-1 种情况。
空间复杂度：O(n^3)

等价交换原则：f(n,k,1) 与 f(n,k,2) 本质上是没区别的。
因为我们把 v=1 的所有答案里的 1 与 2 进行交换，必然就是 v=2 的答案。

故状态转移方程可以简化为

f(n,k) = f(n-1,k-1) + (m-1) * f(n-1,k)

纸上画出这个方程，可以发现关于m-1幂相关的规律。
具体来说，是 (m-1)^(n-1-k)

把 m-1 去掉，再来看剩下的公式，就是f(n,k) = f(n-1,k-1) + f(n-1,k)

可能模版用多了，面对这个公式，我有种很熟悉的感觉，但是没有第一时间想到是什么。
于是就自己去推导规律，最终推导出这个就是组合数，浪费不少时间。

至此，完整的公式就出来了，代码也很简单。

if (m == 1) {
  return n == k + 1;
}
InitA(n); // 用于快速计算 C(n,k)
ll ans = (m * qpow(m-1, n - 1 - k)) % mod;
return (ans * C(n - 1, k)) % mod;

最后

回顾看这次比赛，后两题还是比较有难度的。
第三题很经典，动态维护前缀信息，查找后缀出现的次数。
第四题根据动态规划推出公式，最终套公式即可，这要求你会求大数据范围的C(n,m)。

《完》

-EOF-

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