LeetCode --- 443周赛

题目列表

Q1. 到达每个位置的最小费用
Q2. 子字符串连接后的最长回文串 I
Q3. 子字符串连接后的最长回文串 II
Q4. 使 K 个子数组内元素相等的最少操作数

一、到达每个位置的最小费用

题目要求返回从队尾到达任意位置的最小费用，规则：如果下标 $i$ 在前面，则与 $i$ 交换位置需要 $cost[i]$，如果如果下标 $i$ 在后面，交换位置不用支付费用。
贪心：对于任意位置 $i$，我们不能先去 $j(j>i)$，再到 $i$，这样的方案不如直接到达 $i$，但是如果 $j\le i$，则可以考虑，因为从 $j\to i$ 不用支付费用，所以这题的本质就是求前缀最小值

代码如下

// C++
class Solution {
public:vector<int> minCosts(vector<int>& cost) {int n = cost.size();for(int i = 1; i < n; i++){cost[i] = min(cost[i], cost[i-1]);}return cost;}
};

# Python
class Solution:def minCosts(self, cost: List[int]) -> List[int]:return list(accumulate(cost, min))

二、子字符串连接后的最长回文串 I & II

题目要求我们从字符串 $s$ 和 $t$ 中各自选出一个子串拼接成一个回文串
思路如下：

• 分类讨论：设 $s^{\prime }$ 是 $s$ 的子串，$t^{\prime }$ 是 $t$ 的子串

  • 如果 $len(s^{\prime })=len(t^{\prime })$，则将 $t$ 反转之后，就是求 $s$ 和 $t$ 中最长公共子串，做法类似 718. 最长重复子数组，可以用动态规划来解决

    • 设 $f[i][j]$ 表示 $s$ 中以 $s[i]$ 为结尾的子串与 $t$ 中以 $t[j]$ 为起始的子串(倒序)的最长匹配长度
    • 如果 $s[i]==t[j]$，则 $f[i][j]=f[i-1][j+1]+2$，否则 $f[i][j]=0$
    • 为了防止越界，将 $i+1$，得 $f[i+1][j]=f[i][j+1]+2$

  • 如果 $len(s^{\prime })>len(t^{\prime })$，令 $s^{\prime }=s_1^{\prime }+s_2^{\prime }$ 且 $len(s_1^{\prime })=len(t^{\prime })$，则 $s_1^{\prime }+s_2^{\prime }+t^{\prime }$ 是回文的，所以 $s_2^{\prime }$ 本身应该是回文的，而 $s_1^{\prime }$ 和 $t^{\prime }$ 依旧是求最长公共子串。这里我们用中心扩展法枚举 $s_2^{\prime }$ 回文串，然后统计最长的 $s_1^{\prime }+s_2^{\prime }+t^{\prime }$。

    • 贪心：对于以 $i$ (或者 $i、i+1$) 为中心的回文串 $s_2^{\prime }$，我们只要看最长的那个回文串就行。比如 $...abcba...$，以 $c$ 为中心扩展，我们不需要统计 $s_1^{\prime }+c+t^{\prime }$ 和 $s_1^{\prime }+bcb+t^{\prime }$ 的长度，而只需要统计 $s_1^{\prime }+abcba+t^{\prime }$ 的长度即可
    • 因为对于相同长度的 $s_1^{\prime }+s_2^{\prime }+t^{\prime }$，$s_2^{\prime }$ 越长，则 $s_1^{\prime }$ 和 $t^{\prime }$ 的长度就越短，则更有可能从字符串 $s$ 和 $t$ 中找出符合条件的 $s_1^{\prime }$ 和 $t^{\prime }$
    • 那么有没有可能 $s_2^{\prime }$ 短，$s_1^{\prime }$ 很长，导致 $s_1^{\prime }+s_2^{\prime }+t^{\prime }$ 的长度很长呢？不可能，以 $...ddabcbae...$ 为例，设 $s_1^{\prime }=...ddab，s_2^{\prime }=c，t=badd...$ 和 $s_1^{\prime \prime }=...dd，s_2^{\prime \prime }=abcba，t^{\prime \prime }=dd...$，由于 $s_1^{\prime \prime }$ 是 $s_1^{\prime }$ 的前缀，所以 $s_2^{\prime }$ 短，$s_1^{\prime }$ 很长的策略最多和我们的贪心策略得到的长度一致，不可能优于我们的贪心策略，故我们的贪心是正确的

  • 如果 $len(s^{\prime })<len(t^{\prime })$，同上

代码如下

// C++
class Solution {
public:int longestPalindrome(string s, string t) {auto f = [](const string& s, const string& t)->int{int n = s.size(), m = t.size();int ans = 0;vector dp(n + 1, vector<int>(m + 1));vector<int> mx(n + 1); // mx[i+1] 记录以 s[i] 为结尾的子串与 t 中任意位置为起始位置的最长公共子串的擦汗高难度// dp[i][j] = dp[i-1][j+1] + 2 if s[i] == t[j]// 防止越界 dp[i+1][j] = dp[i][j+1] + 2 if s[i] == t[j]for(int i = 0; i < n; i++){for(int j = m - 1; j >= 0; j--){if(s[i] == t[j]) dp[i+1][j] = dp[i][j+1] + 2;mx[i+1] = max(dp[i+1][j], mx[i+1]);ans = max(ans, dp[i+1][j]);}}for(int i = 0, l, r; i < n; i++){// 以 i 为中心，进行中心扩展for(l = i - 1, r = i + 1; l >= 0 && r < n && s[l] == s[r]; l--, r++);ans = max(ans, r - l - 1 + mx[l+1]);// 以 i,i+1 为中心，进行中心扩展for(l = i, r = i + 1; l >= 0 && r < n && s[l] == s[r]; l--, r++);ans = max(ans, r - l - 1 + mx[l+1]);}return ans;};int ans = f(s, t);// 由于 len(s') < len(t') 和 len(s') < len(t') 是同一个逻辑，可以倒序后，复用代码逻辑ranges::reverse(s);ranges::reverse(t);return max(ans, f(t, s)); }
};

# Python
def max2(x:int, y:int)->int:return x if x > y else y
class Solution:def f(self, s:str, t:str)->int:n, m = len(s), len(t)dp = [[0]*(m+1) for _ in range(n+1)]mx = [0]*(n+1)ans = 0for i in range(n):for j in range(m-1, -1, -1):if s[i] == t[j]:dp[i+1][j] = dp[i][j+1] + 2mx[i+1] = max2(mx[i+1], dp[i+1][j])ans = max2(ans, dp[i+1][j])for i in range(n):l = r = iwhile l >= 0 and r < n and s[l] == s[r]:l -= 1r += 1ans = max2(ans, r - l - 1 + mx[l+1])l, r = i, i + 1while l >= 0 and r < n and s[l] == s[r]:l -= 1r += 1ans = max2(ans, r - l - 1 + mx[l+1])return ansdef longestPalindrome(self, s: str, t: str) -> int:return max2(self.f(s, t), self.f(t[::-1], s[::-1]))

三、使 K 个子数组内元素相等的最少操作数

看到将数组划分为多个子数组，很容易想到 $划分型DP$，基本的状态定义为 $f[i][j]$ 表示将前 $i$ 个数划分为 $j$ 个子数组所需的最少操作次数。本题也是同理。

• 动态规划

  • 状态定义：设 $f[i][j]$ 表示将前 $i$ 个数划分出 $j$ 个长度恰好为 $x$ 的子数组(子数组中元素相同)所需的最少操作次数
  • 状态转移：依旧是选或不选的思路
    • 选以 $nums[i]$ 为右端点的长度为 $x$ 的子数组，则 $f[i][j]=f[i-x][j-1]+ops[i]$，其中 $ops[i]$ 表示让区间 $[i-x+1,i]$ 内元素相同的最小操作次数
    • 不选以 $nums[i]$ 为右端点的长度为 $x$ 的子数组，则 $f[i][j]=f[i-1][j]$
    • 故 $f[i][j]=max(f[i-1][j],f[i-x][j-1]+ops[i])$
  • 初始化
    • 当 $j=0$ 时，$f[i][0]=0$，因为不需要进行任何操作
    • 当 $i<j\ast x$ 时，$f[i][j]=inf$，因为元素不足以分成 $j$ 个长度为 $x$ 的子数组

• 如何求解 $ops[i]?$，即如何快速计算出将 $[i-x+1,i]$ 区间中的数变成同一个数字的最小操作次数

  • 给定一些数字，每次可以对一个数进行 $+1/-1$ 的操作，让它们都变成哪个数字，进行的操作次数最小？中位数贪心
    

  • 如何求解操作次数？

    • 根据上图，操作次数为 $x-nums[0]+x-nums[1]+...+x-nums[j]+nums[j+1]-x+nums[j+2]-x+...+nums[n-1]-x=(j+1)\ast x-pre[j]+pre[n]-pre[j+1]-(n-j-1)\ast x，j=n/2$
    • 但是题目所给的数组是无序的，并且我们需要维护动态区间 $[i-x+1,i]$ 中的中位数
      可以用对顶堆来维护第 $n/2$ 个数，即中位数，同时维护 $pre[j]、pre[n]-pre[j+1]$，即维护两个堆的元素和
      

具体代码如下

// C++
class Solution {using LL = long long;
public:long long minOperations(vector<int>& nums, int x, int k) {// 对顶堆int K = (x + 1) / 2;multiset<int> stL, stR; // 由于 nums 中可能有重复元素，所以用 multisetLL sumL = 0, sumR = 0;auto add = [&](int x){// 优先向 stL 中插入数据if(stL.size() < K){stL.insert(x);sumL += x;return;}stR.insert(x);sumR += x;auto mn = stR.begin();auto mx = prev(stL.end());if(*mx > *mn){sumL += *mn - *mx;sumR += *mx - *mn;stL.insert(*mn);stR.insert(*mx);stL.erase(mx);stR.erase(mn);}};auto remove = [&](int x){auto it = stR.find(x);if(it != stR.end()){stR.erase(it);sumR -= x;return;}it = stL.find(x);stL.erase(it);sumL -= x;int mn = *stR.begin();stL.insert(mn);sumL += mn;stR.erase(stR.begin());sumR -= mn;};int n = nums.size();vector<LL> ops(n);for(int i = 0; i < n; i++){add(nums[i]);if(i >= x - 1){int mid = *stL.rbegin();ops[i] = 1LL * K * mid - sumL + sumR - 1LL * (x - K) * mid;remove(nums[i - x + 1]);}}vector f(n + 1, vector<LL>(k + 1, LLONG_MAX/2));for(int i = 0; i <= n; i++) f[i][0] = 0;for(int j = 1; j <= k; j++){for(int i = x*j; i <= n; i++){f[i][j] = min(f[i-1][j], f[i-x][j-1] + ops[i-1]);}}return f[n][k];}
};