leetcode 周赛 501

零、背景

这次比赛最后一题是全源最短路，看错数据范围了，错了两次。

本场题型概览如下。
A 题：翻转。
B 题：分割字符串。
C 题：因子分解。
D 题：全源最短路。

一、连接逆序数组

题意：给一个数组，求原数组与翻转数组拼接后的数组。

思路：按题意原数组与翻转数组相连即可。

二、有效单词计数

题意：给若干字符串，问这些字符串拼接到一起后，进行分词统计，问指定的单词分别出现几次。
单词定义：字母与连接符组成，连接符左右必须是字母。

思路：分割字符串

双层循环遍历字符串数组，把字符尝试追加到单词上。
如果得到新的单词，更新单词的频率。

四种情况算单词结束。

1）遇到空格 2）前缀单词为空，遇到连接符 3）前缀单词最后一个字符是连接符，再次遇到连接符 4) 输入结束

auto Add = [&](char c) {
  if (c == ' ') {
    Flush();
  } else if (c == '-') {
    if (!s.empty() && s.back() == '-') {
      s.push_back(c);
    } else {
      Flush();
    }
  } else {
    s.push_back(c);
  }
};

单词识别结束时，还需要判断有没有后缀连接符，有的话需要删除。

auto Flush = [&]() {
  if (!s.empty() && s.back() == '-') {
    s.pop_back();
  }
  if (!s.empty()) {
    cnt[s]++;
    s.clear();
  }
};

三、可整除替换后的数组最小元素和

题意：给一个数组，如果数组中存在一个数字是自己的因子，则自己可以使用因子进行替换。
问不断替换，最终可以得到的最小数组和。

思路：因数分解

显然，对于一个数组，使用数组中出现过的最小因子进行替换，才能得到最小数组和。
故，问题转化为找到数字在数组中出现的最小因子。

可以先对数组排序，从小到大处理，这样因子分解时，就知道因子是否出现过了。

因子分解可以使用根号算法 sqrt(n) 来做。
复杂度：O(n sqrt(n))

扩展：数据范围不大，除了进行质因数分解，还可以使用筛法。
即如果一个数字不存在更小的因子，则把这个数字所有的倍数都标记。
复杂度保持不变。

四、购买苹果的最低成本 II

题意：给两个完全一样的无向图 G1 和 G2，权值不一样。
问对于每个节点 a，通过图 G1 到达任意节点，再通过图 G2 返回到 a 的最小代价。
数据范围：点 1000 个，边 2000 条。

思路：Dijkstra 单源最短路

按题意构造两个图，分别求 n 次单源最短路，再枚举求最小答案即可。

PS：一开始看错题意了，看成点是 100，直接 floyd 超时了。

五、最后

这次比赛很简单，第二题解析字符串、第三题因数分解、第四题最短路，都基础题。

《完》

-EOF-

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