leetcode 周赛 509 - 回文串

零、背景

这个周末回了一趟重庆和河南，所以没有参加比赛。

本场题型概览如下。
A 题：循环。
B 题：前后缀。
C 题：质因子与 Kadane 算法。
D 题：马拉车回文串。

一、最大数字范围的整数之和

题意：给一个数组，问数组中与元素最大价值相等的元素之和。
价值定义：十进制数字中最大数字减去最小数字。

思路：循环

一边循环计算价值，一边更新最大价值与元素和。

const int digitRange = DigitRange(a);
if (digitRange > maxValDigitRange) {
  maxValDigitRange = digitRange;
  sum = a;
} else if (digitRange == maxValDigitRange) {
  sum += a;
}

二、一次替换后的子序列

题意：给两个字符串，问第一个字符串修改一个下标的字符后，是否可以成为第二个字符串的子序列。

思路：前后缀匹配

思考1：怎么判断一个字符串是不是另外一个字符串的子序列？
算法：逐个字符进行匹配
复杂度 O(n)

思考2：怎么判断一个字符串的前缀是不是另外一个字符串的子序列？
算法：逐个字符进行匹配时记录匹配的首个位置，然后 O(1) 判断。
预处理复杂度：O(n)
查询复杂度：O(1)

思考3：如何修改一个位置后，是否是子序列？
算法：枚举修改位置，然后需要满足三个条件。
条件1）修改之前的前缀需要匹配。
条件2）修改之后的后缀需要匹配。
条件3）修改之前匹配位置与修改之后匹配位置中间至少有一个位置。
预处理复杂度：前后缀都是 O(n)
枚举复杂度：O(n)

三、可整除游戏

题意：给一个数组，选择一个 k 与区间，区间内可以被 k 整除的数字减去不可以整除的数字为得分。
求最大得分，如果得分相等选择最小的 k。
返回最大得分与所选 k 的乘积，最后取模。
值域：10^6
元素个数：1000

思路：质因数分解

想要答案最大，显然 k 必须是质数。
证明：假设选择的 k 是合数，将 k 修改为这个合数的质因子，增加的得分可能更大，减去的得分可能更小，故最终得分可能更大。

假设选择的是 k，则可以使用 Kadane 最大子数组和算法计算出答案。

一个数字因子个数不超过 log(n) 个。
故总质因子个数不超过 n log(n) 个。
枚举质因子复杂度为 O(n^2 * log(n))

如何快速求出一个数字的质因子呢？

第一种是枚举，单次复杂度 sqrt(n)。
综合复杂度 O(n^2 * sqrt(n))，可能会超时。

第二种是利用筛法，求质数时顺便记录一个质因子，从而可以 log(n) 找到所有质因子。
综合复杂度 O(n^2 * log(n))，可能会超时。

for (const ll v : nums) {
  if (flag[v]) continue; // 剪枝
  ll V = v;
  while (V > 1) {
    int k = randFactor[V];
    if (flag[k] == 0) {
      flag[k] = 1; // 剪枝
      Solver(k);
    }
    V /= k;
  }
}

四、回文子数组求和

题意：给一个数组，问最大的回文串子数组和是多少。

思路：马拉车算法

马拉车核心思路：DP 思想，利用对称性，快速确定当前位置的已经确定的回文半径，然后再往两边扩展。
复杂度：O(n)

子数组和核心思路：对于每个中心的所有回文串中，最大的回文串的和最大。
计算出每个中心的最大半径后，再利用前缀和计算区间和即可。

五、最后

这次比赛难度适中，没想到四道题都过的人挺多的。
第三题过的人那么多，那应该根号算法求因子没有被卡超时。

《完》

-EOF-

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