题目列表

3442. 奇偶频次间的最大差值 I
3443. K 次修改后的最大曼哈顿距离
3444. 使数组包含目标值倍数的最少增量
3445. 奇偶频次间的最大差值 II

一、奇偶频次间的最大差值I

统计字母出现次数，然后分别统计出现偶数次的最小值和出现奇数次的最大值，将两者相减即可，代码如下

// c++
class Solution {
public:int maxDifference(string s) {int cnt[26]{};int mx = 0, mn = INT_MAX;for(auto e : s) cnt[e-'a']++;for(auto x : cnt){if(x){if(x & 1) mx = max(mx, x);else mn = min(mn, x);}}return mx - mn;}
};

# python
class Solution:def maxDifference(self, s: str) -> int:cnt = Counter(s)max1 = max(c for c in cnt.values() if c % 2 == 1)min0 = min(c for c in cnt.values() if c % 2 == 1)return max1 - min0

二、K 次修改后的最大曼哈顿距离

求在移动的过程中，距离原点的最大曼哈顿距离，并且我们可以改变 $k$ 次移动的方向。我们可以计算出每一个时刻距离原点的最大距离，取 $max$ 即为答案

• 对于任意时刻，我们所在的位置和之前移动方向的顺序无关，只和四个方向的移动次数有关，比如已知：向 $N$ 走了 $5$ 步，向 $S$ 走了 $2$ 步，向 $E$ 走了 $6$ 步，向 $W$ 走了 $3$ 步，则当前位置坐标为 $(+5-2,+6-3)=(3,3)$，曼哈顿距离为 $|3|+|3|=6$。故只要统计四个方向的移动次数即可
• 如何改变移动方向，才能让曼哈顿距离变大？减少相反方向的移动次数，比如向 $N$ 走 $5$ 步，向 $S$ 走 $3$ 步，显然我们要让向 $S$ 的移动次数变小，向 $N$ 的移动次数变多。即对于两个相反方向来说，我们改变移动次数少的方向

代码如下

// c++
class Solution {
public:int maxDistance(string s, int k) {int n = s.size(), ans = 0;int f[4]{};for(auto e : s){// 统计四个方向上的移动次数switch(e){case 'N': f[0]++; break;case 'S': f[1]++; break;case 'E': f[2]++; break;case 'W': f[3]++; break;}// cnt 表示改变移动方向后，会使得答案更大的移动次数，即统计相反方向上移动次数更小的移动次数int cnt = min(f[0], f[1]) + min(f[2], f[3]);// res 表示不考虑 cnt 的最大曼哈顿距离int res = max(f[0], f[1]) + max(f[2], f[3]);// min(cnt, k) 表示可修改移动方向的移动次数，max(cnt, k) - k 表示不可修改的移动次数ans = max(ans, res + min(cnt, k) - (max(cnt, k) - k));}return ans;}
};

# python
class Solution:def maxDistance(self, s: str, k: int) -> int:n = len(s)f = defaultdict(int)ans = 0for x in s:f[x] += 1a = max(f['N'], f['S']) + max(f['E'], f['W'])b = min(f['N'], f['S']) + min(f['E'], f['W'])ans = max(ans, a + min(b, k) - (max(b, k) - k))return ans

三、使数组包含目标值倍数的最少增量

为了让 $target$ 中的每个元素在 $nums$ 中至少有一个倍数存在，我们需要让 $nums$ 中的某些数成为 $target$ 中一个数或多个数的倍数。

• 为了保证操作次数最少，我们进行操作的数必然要成为 $target$ 中一个数或多个数的倍数，故我们可以采用选或不选的思路考虑

  • 由于 $target$ 的最多有 $4$ 个数，我们可以预处理出不同数字组合的公倍数，如 $[2,3,4]$，我们可以计算出 $[2]、[3]、[4]、[2,3]、[2,4]、[3,4]、[2,3,4]$ 这些集合数字的公倍数。可以用动态规划$+$位运算来解决

    • 令 $f[mask]$ 表示 $mask$ 中二进制为 $1$ 的数字集合的公倍数
    • 则 $f[mask|1<<i]=lcm(f[mask],target[i])$，其中 $lcm$ 为求两个数的最小公倍数的函数

  • 对于任意一个数 $nums[i]$，如果我们选择它，则让它成为 $target$ 中一个数或多个数的倍数，即 $f[sub]$ 的倍数，其中 $sub$ 表示 $target$ 中部分数字的集合。如果不选，则考虑让剩下的数字

    • 故我们定义 $dp[i][j]$ 表示前 $i$ 个数让 $j$ 的二进制集合中的数字都有倍数的最小操作次数
    • 不选 $nums[i]$，$dp[i][j]=dp[i-1][j]$
    • 选 $nums[i]$，$dp[i][j]=min(dp[i-1][j-sub]+(l-nums[i]\%l)\%l)$，其中 $sub$ 为 $j$ 的子集，$l=f[sub]$ 表示 $sub$ 集合的最小公倍数
    • $(l-nums[i]\%l)\%l$ 计算 $nums[i]$ 变成 $l$ 的倍数的最少操作次数

代码如下

// c++
class Solution {
public:int minimumIncrements(vector<int>& nums, vector<int>& target) {int n = nums.size(), m = target.size();vector<long long> lcms(1<<m);lcms[0] = 1;for(int i = 0; i < m; i++){int bit = 1 << i;for(int mask = 0; mask < bit; mask++){lcms[mask|bit] = lcm(lcms[mask], target[i]);}}vector f(n + 1, vector<long long>(1 << m));for(int j = 1; j < (1<<m); j++) f[0][j] = LLONG_MAX/2;for(int i = 0; i < n; i++){for(int j = 0; j < (1<<m); j++){f[i+1][j] = f[i][j];for(int sub = j; sub; sub = (sub - 1) & j){ // 枚举 j 的子集long long l = lcms[sub];f[i+1][j] = min(f[i+1][j], f[i][j-sub] + (l - nums[i]%l)%l);}}}return f[n][(1<<m)-1];}
};

#python
class Solution:def minimumIncrements(self, nums: List[int], target: List[int]) -> int:n = len(nums)m = len(target)lcms = [0] * (1 << m)lcms[0] = 1for i in range(m):bit = 1 << ifor mask in range(bit):lcms[mask | bit] = lcm(lcms[mask], target[i])f = [[0]*(1<<m) for _ in range(n + 1)]for j in range(1, 1<<m):f[0][j] = inffor i in range(n):for j in range(1<<m):f[i+1][j] = f[i][j]sub = jwhile sub:l = lcms[sub]f[i+1][j] = min(f[i+1][j], f[i][j-sub] + (l - nums[i]%l)%l)sub = (sub - 1) & jreturn f[n][(1<<m)-1]

四、奇偶频次间的最大差值 II

本题的思路如下

• 由于 $s$ 中最多有 $5$ 中数字字符，可以两重循环暴力枚举 $a、b$ 两个字符 $(a!=b)$

• 在不考虑奇偶性的情况下，求 $[l,r]$ 区间内出现次数之差的最大值，我们可以用前缀和快速计算出区间内字符 $a、b$ 的出现次数，在相减得 $pr{e}_a[r]-pr{e}_a[l-1]-(pr{e}_b[r]-pr{e}_b[l-1])=pr{e}_a[r]-pr{e}_b[r]-(pr{e}_a[l-1]-pr{e}_b[l-1])$，对于这样的式子，我们可以边计算 $pr{e}_a、pr{e}_b$，边跟新 $pr{e}_a-pr{e}_b$ 的最小值，同时跟新答案

• 如何考虑奇偶性？定义一个数组 $diff[2][2]$ 记录前 $i$ 个 $pr{e}_a-pr{e}_b$ 的最小值

  • $diff[0][0]$ 表示 $pr{e}_a$ 为偶数，$pr{e}_b$ 为偶数的情况
  • $diff[0][1]$ 表示 $pr{e}_a$ 为偶数，$pr{e}_b$ 为奇数的情况
  • $diff[1][0]$ 表示 $pr{e}_a$ 为奇数，$pr{e}_b$ 为偶数的情况
  • $diff[1][1]$ 表示 $pr{e}_a$ 为奇数，$pr{e}_b$ 为奇数的情况
  • 如此一来，我们就能根据当前 $pr{e}_a、pr{e}_b$ 的奇偶性，来匹配合适的最小值 $diff[p][q]$，其中 $p=1-pr{e}_a\%2，q=pr{e}_b\%2$

• 注意：题目要求区间内字符 $a、b$ 的出现次数不能为 $0$，所以我们要保证 $pre[r]-pre[l-1]!=0$，即 $pre[r]!=pre[l-1]$，由于 $pre$ 数组是递增的，则 $pre[r]>pre[l-1]$，同时题目要求区间长度 $\ge k$，我们可以用类似滑动窗口的思想更新 $diff$ 数组，具体见代码

代码如下

// c++
class Solution {
public:int maxDifference(string s, int k) {int n = s.size();int ans = INT_MIN;for(int a = 0; a < 5; a++){for(int b = 0; b < 5; b++){if(a == b) continue;vector diff(2, vector<int>(2, INT_MAX));vector<int> cnta(n + 1), cntb(n + 1);for(int i = 0, j = 0; i < n; i++){int x = s[i] - '0';cnta[i + 1] = cnta[i] + (x == a);cntb[i + 1] = cntb[i] + (x == b);// 跟新 diff 最小值，保证 区间长度 >= k && 字符a、b的出现次数 > 0while(i - j + 1 >= k && cnta[j] < cnta[i+1] && cntb[j] < cntb[i+1]){int p = cnta[j] % 2, q = cntb[j] % 2;diff[p][q] = min(diff[p][q], cnta[j] - cntb[j]);j++;}if(i >= k - 1){int p = 1 - cnta[i+1] % 2, q = cntb[i+1] % 2;if(diff[p][q] < INT_MAX){ans = max(ans, cnta[i+1] - cntb[i+1] - diff[p][q]);}}}}}return ans;}
};

# python
class Solution:def maxDifference(self, s: str, k: int) -> int:n = len(s)ans = -inffor a in range(5):for b in range(5):if a == b:continuediff = [[inf, inf], [inf, inf]]cnta, cntb = [0]*(n+1), [0]*(n+1)j = 0for i in range(n):x = ord(s[i]) - ord('0')cnta[i+1] = cnta[i] + (x == a)cntb[i+1] = cntb[i] + (x == b)while i - j + 1 >= k and cnta[j] < cnta[i+1] and cntb[j] < cntb[i+1]:p, q = cnta[j] % 2, cntb[j] % 2diff[p][q] = min(diff[p][q], cnta[j]-cntb[j])j += 1if i >= k - 1:p, q = 1 - cnta[i+1] % 2, cntb[i+1] % 2if diff[p][q] < inf:ans = max(ans, cnta[i+1] - cntb[i+1] - diff[p][q])return ans