leetcode 周赛 490

零、背景

这次比赛在农历新年初六，早上5点就出门办事了，晚上10点才回家。
第二天抽空补做了四道题。

本场题型概览如下。
A 题：模拟。
B 题：贪心。
C 题：贪心。
D 题：搜索。

最终排名：未参赛。
代码仓库：详见 https://github.com/tiankonguse/leetcode-solutions。

一、计算比赛分数差

题意：给一个比赛得分列表和两个选手，从左到右按规则比赛，主动玩家获取对应位置的得分，问最终第一个选手比第二个选手多多少分。
规则：默认第一个选手是主动玩家，如果遇到奇数得分，主动玩家切换为另外一个选手；所有的第6场比赛切换主动玩家。

思路：模拟。

按题意循环模拟，计算两个选手的得分。

注意事项：遇到奇数的同时遇到第6场比赛，需要切换两次，等价于不切换。

二、阶数数字排列

题意：给一个数字 n，判断是否存在 n 的任意排列（包括原始顺序），可以形成一个阶数数字。
如果一个数字的所有位数的阶乘之和等于数字本身，则称其为阶数数字。

思路：贪心。

先计算数字 n 所有位数的阶乘之和 N，然后判断 N 是否与 n 的某个排列相等。

快速判断方法：排序后比较。

三、重新排列后的最大按位异或值

题意：给两个长度相等的二进制字符串 s 和 t，问对 t 进行重新排列，然后与 s 进行异或，得到的最大值是多少。

思路：贪心。

由于 t 是可以任意排列的，所以可以对 t 进行统计，然后根据 s 的每一位，尽可能选择 t 中对应位置的相反位来进行异或，以获得更大的结果。

四、统计结果等于 K 的序列数目

题意：给一个序列和一个整数 K，对于每个序列值，可以选择乘法、除法、不选择三种操作，问有多少个操作序列，使得最终结果等于 K。

思路：搜索。

方法1：暴力搜索。

按题意进行 DFS 搜索。
复杂度：O(3^n)。
得分：955 / 998，超时。

ll Dfs(int p, ll A, ll B) {
  auto [a, b] = Smp(A, B);
  if (p == n) {
    return a == K && b == 1 ? 1 : 0;
  }
  ll v = nums[p];
  return Dfs(p + 1, a * v, b) + Dfs(p + 1, a, b * v) + Dfs(p + 1, a, b);
}

方法2：记忆化搜索。

DFS 搜索时，如果同一位置遇到相同的 (a, b) 时，没必要重复计算，可以记录下来。
得分：998 / 998 AC，耗时 543ms。

map<tuple<int, ll, ll>, ll> memo; // (p,a,b) -> cnt

方法3：BFS 动态规划。

可以发现，每个序列位置只与前一个位置有关，所以可以使用动态规划。

状态定义：S(i) 表示前 i 个位置的操作序列得到的有理数与个数。
状态转移方程：S(i) = S(i-1) * v + S(i-1) / v + S(i-1)。

得分：998 / 998 AC，耗时 354ms。

方法4：剪枝。

DFS 与 BFS 搜索的时候，都是枚举到最后。
如果在某个位置发现当前的有理数已经无法达到 K 了，那么后续的操作也不可能达到 K，因此可以直接剪枝。

剪枝1：后续全部选择乘法，依旧无法得到整数，那么直接剪枝。
剪枝2：可以整除，但是全部选择乘法，结果小于 K，那么直接剪枝。
剪枝3：除法与乘法一样，后续都选择乘法需要可以得到整数且不小于 K。

这样剪枝后，BFS 动态规划耗时从 354ms 降低到 87ms。
DFS 记忆化搜索耗时从 543ms 降低到 170ms。

方法5：对半搜索。

对于搜索，复杂度是指数级的，即复杂度最坏情况下是 3^n。
起点和终点是确定的，此时可以使用对半搜索，这样复杂度就降低为 3^(n/2)。
耗时：67ms。

五、最后

这次比赛最后一题出的比较简单，第一感觉想到的是 BFS 可能会超时，没想到就可以通过了。
若再加强一下数据，来考察折半搜索的话，就是一道不错的题目。

《完》。

-EOF-

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