leetcode 第 223 场算法比赛

零、背景

继续参加 leetcode 的周赛。
最后一题一开始没想法，使用暴力搜索来做的，超时后发现是动态规划，时间已经不够了。

相关源代码： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/223

一、解码异或后的数组

题意：给一个加密后的数组和加密前第一个数组的值，求加密前的数组。
加密规则：相邻两位异或得到一个加密的数字，加密后数组长度少一位。

思路：依次异或得到下一个加密前的数字即可。

二、交换链表中的节点

题意：给一个链表，要求交换第 k 个与倒数第 k 个节点。

思路：一开始我看错题意了，以为是必须交换节点（删除再添加），不能交换值。
敲完了，发现可以只交换值。

那循环三遍即可。
第一遍计算出链表长度与两个需要交换的位置。 第二遍找到第一个节点。
第三遍找到第二个节点。
进行 swap 即可。

三、执行交换操作后的最小汉明距离

题意：给两个长度相同的数组，和一些交换规则。
问任意次数交换后，两个数组相同位置值不同的个数。

交换规则：对一个数组两个位置的值进行交换。

思路：很容易发现，交换规则组成若干个联通分支。

可以证明下面两个结论。
不同联通分支的位置互不影响。
相同联通分支内的位置，可以任意交换。

对于每个联通分支，我们分别对两个数组里的节点集合取交集，交集的个数就是匹配的个数，剩下的就是不匹配的个数。

PS：这道题我手残敲错一个地方，调试了半个小时。

四、完成所有工作的最短时间

题意：给一个任务列表，分配给 k 个人，每个人只能干完一个任务才能干下个任务。
问怎么分配才能让这些人的最大工作时间最小。

思路：一看是就想使用动态规划做。
但是一看是最大值里的最小，又想使用二分做。
最后一个数据量比较小，就决定使用暴力搜索加剪枝做了。

对于二分，每个回合需要求 k 次背包，还不能证明其正确性。

对于搜索，对于每个工人需要枚举所有子状态。
这个在《leetcode 第 218 场算法比赛》第四题分享过一个高效枚举子集的方法。

另外，搜索在极端情况下，复杂度是O(n^k)
之所有会这样，是因为有很多重复计算。

所以，最终方法还是需要需要使用动态规划来消除重复。

状态定义：dp[i][mask] 为前 i 个人干完 mask 工作的最优值。
通过枚举 mask 就很容易求出这个最优值。

int minimumTimeRequired(vector<int>& jobs, int k) {
  int n = jobs.size();
  vector<vector<int>> dp(k);

  dp[0].resize(1 << n, 0);
  for (int mask = 1; mask < (1 << n); mask++) {
    int pre = mask & (mask - 1);
    int now = __builtin_popcount(mask ^ (mask - 1));
    dp[0][mask] = dp[0][pre] + jobs[now - 1];
  }

  for (int i = 1; i < k; i++) {
    dp[i].resize(1 << n, 0);
    for (int mask = 1; mask < (1 << n); mask++) {
      // 前 i 个人，选择 mask 的最优解

      int now = dp[i - 1][mask];
      for (int j = mask; j; j = (j - 1) & mask) {
        now = min(now, max(dp[0][j], dp[i - 1][mask ^ j]));
      }
      dp[i][mask] = now;
    }
  }
  return dp[k - 1][(1 << n) - 1];
}

复杂度：O(k * 2^n * 2^n)

五、最后

这次比赛的题还不错，再次遇到枚举子状态的题。

这种题我还是做得少，后面还是要多练练。

对了，告诉大家一个好消息：昨天我跑步，5 公里在 20 分钟跑完了，完成了 2020 年的目标。
接下来目标是 19 分钟内跑完。

加油，算法人。

《完》

-EOF-

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