leetcode 第 428 场算法比赛

零、背景

这次比赛难度还好，但是总是想着去贪心，就容易发现有反例，使用dp或者暴力就简单多了。

A: 循环
B: 枚举+BFS 拓扑图
C: 枚举+hash
D: 枚举+dp

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

一、按下时间最长的按钮

题意：给一个数组，问相邻差最小的位置。

思路：相邻求差，求最小值。

二、两天自由外汇交易后的最大货币数

题意：起初有人民币1元钱，每天给出一个最新的汇率表，问第二天结束之后，可以得到多少人民币。

思路：枚举。

题目保证有向图没有环，所以是一个有向拓扑图。

第一天，bfs 得到所有币种最多可以换取得到多少钱。
对于拓扑图，bfs 到达一个币种，如果有更优值，需要重新递归 bfs。

第二天，枚举第一天得到的所有币种，继续 bfs 一天，求出所有币种的最大值。

图的边大小为 10
第一天复杂度：O(2^10)
第二天复杂度：O(10 * 2^10)

实际复杂度远远小于预估复杂度。

三、统计数组中的美丽分割

题意：给一个数组，问是否可以拆分为3个子数组，使得第一个子数组是第二个子数组的前缀，或者第二个子数组是第三个子数组的前缀。
如果可以，问有多少拆法。

思路：枚举+hash

数据范围 5000，可以枚举所有拆法，判断是否满足前缀关系即可。
判断两段区间是否相等，可以通过预处理数组的 hash，然后O(1)获取指定区间的hash。

区间 hash 模版如下，BASE 是基底。
数值需要从1开始，所以 BASE 比值域大 1。
例如数字，BASE 是 11，值域 [0,9] 都需要加1，转化为 值域 [1,10]。
例如字母，BASE 是 29, [0,25] 都需要加1，转化为 [0,26] , 选取下个素数当做基底。
这道题值域是[0,50]，加1就是[1,51]，52 不是素数，选择下个素数 53。

const ll BASE = 53;

ll h[max3];
ll qpowCache[max3];

ll H(int l, int r) {
  if (l == 0) return h[r];
  ll pre = h[l - 1] * qpowCache[r - l + 1] % mod1e7;
  return (h[r] - pre + mod1e7) % mod1e7;
}

void Init(const vector<int>& str, int n) {
  qpowCache[0] = 1;
  for (int i = 1; i <= n; i++) {
    qpowCache[i] = (qpowCache[i - 1] * BASE) % mod1e7;
  }

  ll pre = 0;
  for (int i = 0; i < n; i++) {
    pre = (pre * BASE + (str[i] + 1)) % mod1e7;
    h[i] = pre;
  }
}

四、使字符频率相等的最少操作次数

题意：给一个字符串，问最少执行多少次操作，才能使得字符串所有字符次数相等。
操作1：删除一个字符
操作2：增加一个字符
操作3：一个字符的值修改为字典序下一个字符

思路：枚举+DP

首先预处理字符串，统计各个字符出现的次数，共 26 个字符。
然后枚举最优答案各个字符的次数。

答案的字符个数确定了，大部分字符的处理方式是多退少补。
特殊的处理方式是相邻字符打包处理，即前一个删除后一个增加时，替换为操作2的修改。

什么时候打包处理呢？
打包处理的答案更优时才行。

处理打包时，很容易去贪心
即判断两个打包处理，是不是比分别处理更优。

但是存在一个反例：当前位置打包不一定更优。
即当前位置独立处理，下个位置和下下个位置打包处理，可能比当前位置打包处理更优。
而下个位置和下个位置打包是否更优，也是无法判断的，这是一个向后的递归过程。

所以，我们需要使用动态规划来判断哪种情况更优。

状态定义：f(i) 第i个字符开始，操作完后面所有字符使得个数为枚举值的最少操作数。

状态转移方程分几种情况：

情况1: 高度为0，不需要处理 f(i) = f(i+1)
情况2: 高度为 h，不需要处理 f(i) = f(i+1)
情况3：全部删除 f(i) = v + f(i+1)
情况4: 不足h，添加 f(i) = h - v + f(i+1)
情况5: 超过h，删除 f(i) = v - h + f(i+1)

当后一个不足h的时候，才可以打包，分为两种情况。

情况6: 不足h都删除+打包 f(i) = max(v, h-nums[i+1]) + dfs(i+2)
情况6: 超过h删除部分+打不 f(i) = max(v-h, h-nums[i+1]) + dfs(i+2)

复杂度： O(26 n)

int Dfs(int i, int h) {
  if (i >= 26) return 0;
  int& ret = dp[i];
  if (ret != -1) return ret;
  const int v = nums[i];
  ret = INT_MAX;
  if (v == 0 || v == h) {  // 已经满足
    return ret = Dfs(i + 1, h);
  }
  // 独自处理, 多了删除，少了添加
  ret = min(ret, min(abs(h - v), v) + Dfs(i + 1, h));
  // 与下一个一起处理
  if (i + 1 < 26 && nums[i + 1] < h) {
    int minNow = v;
    if (v > h) {
      minNow = min(minNow, v - h);
    }
    ret = min(ret, max(minNow, h - nums[i + 1]) + Dfs(i + 2, h));
  }
  return ret;
}

五、最后

这次比赛最后一题我一直在想着贪心来做，浪费了大量的时间。
最后10分钟想到只能使用 DP，但是 6 种情况我使用 max/min 合并处理，漏了一种，提交没通过。
赛后老老实实写各种 if/else，然后就通过了。

《完》

-EOF-

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