leetcode 周赛 496

零、背景

这次比赛刚好在清明假期，一家人去了重庆武隆的仙女山。
在回深圳的机场，补做了一下这次比赛。

本场题型概览如下。
A 题：统计。
B 题：离线计算。
C 题：贪心。
D 题：贪心DP。

一、镜像频次距离

题意：给一个字符串，求所有字符与镜像字符的频率之差的绝对值之和。

思路：统计。

先统计所有字符的个数，然后枚举所有字符，依次计算字符与镜像字符的频率之差。
对于已经计算过的字符和镜像字符，标记已访问即可。

二、可由多种立方和构造的整数

题意：如果至少存在两组不同的 (a,b) 满足 x = a^3 + b^3，则称 x 为好整数。
求小于等于 x 的所有好整数。

思路：离线计算。

由于数据范围是 10^9，二元组中每个数的三次方不超过 x，因此二元组的值不超过 1000。

离线枚举计算所有二元组，统计并标记好整数即可。

unordered_map<ll, int> cnt;
set<ll> s; // 答案，有序
void Init() {
  if (!cnt.empty()) return;
  const ll maxn = 1000 * 1000 * 1000;
  for (ll i = 1; i <= 1000; i++) {
    for (ll j = i; j <= 1000; j++) {
      ll x = i * i * i + j * j * j;
      if (x > maxn) break; // 剪枝
      cnt[x]++;
      if (cnt[x] > 1 && s.count(x) == 0) {
        s.insert(x);
      }
    }
  }
}

三、最大化特殊下标数目的最少增加次数

题意：给一个数组，求使数组的特殊下标数目最多时所需的最小操作数。
特殊下标：当前下标的值严格大于相邻下标的值。
操作：对某个下标的值加一。

思路：贪心一维DP。

特殊下标称为波峰，其他下标称为波谷。

可以先确定一些基本性质。
第一、下标的值只加不减，波谷的值不操作时是最优的，故只需要对波峰的值进行操作。
第二、第一个下标和最后一个下标肯定不是波峰。
第三、一个特殊下标至少需要 3 个位置。
第四、在已存在特殊下标的基础上，再增加两个位置就可以新增一个特殊下标。

基于第三和第四条性质，可以推导出：当元素个数为奇数时，肯定可以得到 (n-1)/2 个特殊下标，此时所有位置都能被利用上。

当元素个数为偶数时，会有一个下标是空闲的。

基于以上分析，可以写出贪心动态规划的转移方程。

状态定义：dp[i] 表示前 i 个元素的最小操作数。
波峰代价函数：Cost(i) 表示位置 i 作为波峰的最低代价。

如果 i 是奇数，则状态转移方程如下：

dp[i] = dp[i-2] + Cost(i-1)

如果 i 是偶数，最后一个位置可以不选择，也可以选择作为波谷。

dp[i] = min(dp[i-1], dp[i-2] + Cost[i-1]);

Cost(i) 函数比较简单：与两个相邻波谷的最大值加一进行比较，差多少就补多少。

复杂度：O(n)。

四、产生至少 K 个峰值的最少操作次数

题意：与第三题类似，但数组改成循环数组，要求波峰至少出现 K 次，问最小操作数。

思路：贪心二维DP。

由于是循环数组，偶数个元素最多可以得到 n/2 个波峰；奇数个元素会浪费一个位置，最多也是 n/2 个波峰。

当 K 等于 0 时，显然答案是 0。
当 K 大于 n/2 时，显然没有答案。
其他情况肯定存在答案，但需要使用二维 DP 来求最优解。

状态定义：dp[k][n] 表示前 n 个元素中至少得到 k 个波峰的最小操作数。

先不考虑循环数组，可以得到下面的状态转移方程。

dp[k][n] = min(
  dp[k][n-1], // 不选择
  dp[k-1][n-2] + Cost(n-1) // 选择
);

再考虑循环数组，分两种情况。

情况一：第一个位置是波峰，最后一个位置是波谷。
这种情况单独计算 Cost(1) 即可，剩下的与非循环数组完全一致。

情况二：第一个位置是波谷，最后一个位置也是波谷。
这种情况在数组末尾追加一个元素，值与第一个元素相等，之后与非循环数组完全一致。

由此，这道题就解决了。
复杂度：O(n*k)。

五、最后

这次比赛后两题本质上区别不大。
一个是求最大值，直接一维 DP；另一个是不大于 K，需要二维 DP。
两种 DP 都是很常见的题型，都属于基础动态规划。

《完》。

-EOF-

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