第435场周赛：奇偶频次间的最大差值Ⅰ、K次修改后的最大曼哈顿距离、使数组包含目标值倍数的最少增量、奇偶频次间的

Q1、奇偶频次间的最大差值 Ⅰ 1、题目描述

给你一个由小写英文字母组成的字符串 s 。请你找出字符串中两个字符的出现频次之间的 最大 差值，这两个字符需要满足：

一个字符在字符串中出现 偶数次 。另一个字符在字符串中出现 奇数次 。

返回 最大 差值，计算方法是出现 奇数次 字符的次数 减去 出现 偶数次 字符的次数。

2、解题思路

统计字符出现次数

由于字符串只包含小写英文字母，我们可以使用 哈希表（unordered_map） 记录每个字符的出现次数。

遍历哈希表，分类统计

找到 出现次数是奇数的最大值。

找到 出现次数是偶数的最小值。

计算并返回结果

如果 mineven 仍然是 INT_MAX，说明没有出现次数为偶数的字符，应返回 0。

计算 maxodd - mineven 并返回。

3、代码实现 class Solution { public: int maxDifference(string s) { unordered_map<char, int> hash; // 统计每个字符出现的次数 // 统计字符出现次数 for (const auto& ch : s) { hash[ch]++; } int maxodd = 0; // 记录出现奇数次的最大值 int mineven = INT_MAX; // 记录出现偶数次的最小值 // 遍历哈希表, 找到最大奇数次和最小偶数次 for (const auto& kv : hash) { if (kv.second % 2) { // 如果次数是奇数 maxodd = max(maxodd, kv.second); } else { // 如果次数是偶数 mineven = min(mineven, kv.second); } } // 如果不存在出现偶数次的字符, 返回 0 if (mineven == INT_MAX) { return 0; } return maxodd - mineven; } };

4、复杂度分析

时间复杂度：

统计字符频率：O(n)

遍历哈希表：O(26)（最多 26 个字母）

总时间复杂度： O(n)

空间复杂度：

需要 O(26) = O(1) 的空间存储哈希表（最多 26 个字符）。

总空间复杂度： O(1)

Q2、K 次修改后的最大曼哈顿距离 1、题目描述

给你一个由字符 'N'、'S'、'E' 和 'W' 组成的字符串 s，其中 s[i] 表示在无限网格中的移动操作：

'N'：向北移动 1 个单位。'S'：向南移动 1 个单位。'E'：向东移动 1 个单位。'W'：向西移动 1 个单位。

初始时，你位于原点 (0, 0)。你 最多 可以修改 k 个字符为任意四个方向之一。

请找出在 按顺序 执行所有移动操作过程中的 任意时刻 ，所能达到的离原点的 最大曼哈顿距离 。

曼哈顿距离 定义为两个坐标点 (xi, yi) 和 (xj, yj) 的横向距离绝对值与纵向距离绝对值之和，即 |xi - xj| + |yi - yj|。

2、解题思路

为了求解最大曼哈顿距离，我们需要动态地计算经过每一步移动后的曼哈顿距离，并考虑在每一步是否修改某些操作来增加这个距离。

分为北南和东西方向： 在任意时刻，当前位置的 x 和 y 坐标分别受东西方向（‘E’、‘W’）和南北方向（‘N’、‘S’）的影响。对于北南方向，我们关心的是 'N' 和 'S' 的出现次数，计算它们之间的差值来表示当前在 y 轴上的位置。对于东西方向，我们关心的是 'E' 和 'W' 的出现次数，计算它们之间的差值来表示当前在 x 轴上的位置。 修改操作： 我们可以修改最多 k 个字符，从而最大化曼哈顿距离。修改字符时，我们的目标是让北南方向和东西方向的距离尽量增大，因此在每次修改时，我们应选择最有利于增加距离的方向。 动态更新曼哈顿距离： 对于每一移动操作，我们都会根据当前的方向更新当前的 x 和 y 坐标。然后计算当前的曼哈顿距离，并查看是否需要修改操作来进一步增加距离。 3、代码实现 class Solution { private: // 计算给定方向的曼哈顿距离 int calculateManhattanDistance(int a, int b, int& modify) { // 计算 a 和 b 之间的距离, 以及我们最多可以修改的步数 modify int d = min({a, b, modify}); // 可以修改的最小步数 modify -= d; // 修改步数减少 // 返回总的曼哈顿距离 return abs(a - b) + d * 2; // 绝对差 + 修改带来的额外距离 } public: int maxDistance(string s, int k) { int ret = 0; // 用于记录最大曼哈顿距离 // 统计四个方向的出现次数 int cnt['X'] = {}; // 用一个数组来记录 'N', 'S', 'E', 'W' 出现的次数 // 遍历字符串s, 计算每步的曼哈顿距离 for (char ch : s) { cnt[ch]++; // 更新对应方向的次数 int modify = k; // 重置剩余可以修改的步数 // 计算北南方向的曼哈顿距离 int northSouthDist =calculateManhattanDistance(cnt['N'], cnt['S'], modify); // 计算东西方向的曼哈顿距离 int eastWestDist =calculateManhattanDistance(cnt['E'], cnt['W'], modify); // 更新最远距离 ret = max(ret, northSouthDist + eastWestDist); } return ret; // 返回最大曼哈顿距离 } };

4、复杂度分析

时间复杂度：

遍历字符串 s 计算每步的曼哈顿距离，时间复杂度为 O(n)，其中 n 是字符串 s 的长度。计算每次曼哈顿距离需要常数时间 O(1)。总时间复杂度： O(n)。

空间复杂度：

使用一个大小为 4 的数组 cnt 来记录各方向的计数，空间复杂度为 O(1)。总空间复杂度： O(1)。 Q3、使数组包含目标值倍数的最少增量 1、题目描述

给你两个数组 nums 和 target 。

在一次操作中，你可以将 nums 中的任意一个元素递增 1 。

返回要使 target 中的每个元素在 nums 中 至少 存在一个倍数所需的 最少操作次数 。

2、解题思路

这个问题可以通过 动态规划 和 子集最小公倍数（LCM） 的思想来解决。

最小公倍数的概念： 假设 a 是 nums 中的一个元素，b 是 target 中的一个元素。如果 a 是 b 的倍数，则 a % b == 0。如果我们希望在 nums 中的每个元素都至少是 target 中某元素的倍数，我们需要根据每个元素的倍数关系来计算递增次数。 子集 LCM 的计算： 对于 target 中的多个元素，我们可以计算这些元素的最小公倍数（LCM）。假设我们正在考虑 target 中某个元素的子集，我们需要计算该子集的最小公倍数，这样才能判断 nums 中哪些元素可以满足这些条件。为了计算每个子集的 LCM，可以使用动态规划的思想，遍历所有子集并更新 LCM。 递归与记忆化搜索： 对于 nums 中的每个元素，我们尝试递增它使其成为 target 中某个元素的倍数。使用一个 memo 数组记录已计算过的状态，避免重复计算。

步骤详解

计算子集 LCM： 对于 target 数组的每个子集，计算其最小公倍数（LCM）。在 nums 中，如果一个元素是某个子集 LCM 的倍数，那么我们可以考虑它作为这个子集的代表元素。 递归动态规划： 使用深度优先搜索（DFS）结合记忆化搜索（Memoization）计算最小的操作次数。dfs(i, j) 表示我们已经处理了 nums 中前 i 个元素，并且 target 中的子集状态为 j（j 是一个位掩码，表示 target 中哪些元素已被满足）。 返回结果： 最终返回的结果是从 nums 中选择最小操作次数的答案。 3、代码实现 class Solution { public: // 计算两个数的最小公倍数 (LCM) long long lcm(long long a, long long b) { return a * b / __gcd(a, b); } // 预处理 target 数组的所有子集的 LCM vector<long long> calculateLCMSubsets(const vector<int>& target) { int m = target.size(); vector<long long> lcms(1 << m, 1); // 初始化 lcms 数组, 大小为 2^m, 每个值都初始化为 1 // 对每个 target 的元素进行处理 for (int i = 0; i < m; ++i) { int bit = 1 << i; // 当前元素对应的位 for (int mask = 0; mask < bit; ++mask) { lcms[bit | mask] = lcm(target[i], lcms[mask]); // 更新子集的 LCM } } return lcms; } // 计算最少的操作次数, 确保 nums 中每个元素是 target 中某元素的倍数 int minimumIncrements(vector<int>& nums, vector<int>& target) { int n = nums.size(); int m = target.size(); // 计算 target 数组的所有子集的 LCM vector<long long> lcms = calculateLCMSubsets(target); // 创建 memo 数组, 缓存已经计算过的状态, 避免重复计算 vector<vector<long long>> memo(n, vector<long long>(1 << m, -1)); // 定义 dfs 函数, 递归计算最小操作次数 auto dfs = [&](auto&& dfs, int i, int j) -> long long { if (j == 0) { return 0; // 如果 j 为 0, 说明已经满足条件, 不需要操作 } if (i < 0) { return LLONG_MAX / 2; // 超过范围时返回一个很大的值, 防止溢出 } long long& res = memo[i][j]; if (res != -1) { return res; // 如果已经计算过, 直接返回缓存的结果 } res = dfs(dfs, i - 1, j); // 不修改 nums[i] // 枚举 j 的所有非空子集 for (int sub = j; sub; sub = (sub - 1) & j) { long long l = lcms[sub]; // 当前子集的 LCM res = min(res, dfs(dfs, i - 1, j ^ sub) + (l - nums[i] % l) % l); // 更新最小操作数 } return res; // 返回结果 }; // 从数组的最后一个元素开始, 计算整个数组的最小操作次数 return dfs(dfs, n - 1, (1 << m) - 1); } };

Q4、奇偶频次间的最大差值 Ⅱ 1、题目描述

给你一个字符串 s 和一个整数 k 。请你找出 s 的子字符串 subs 中两个字符的出现频次之间的 最大 差值，freq[a] - freq[b] ，其中：

subs 的长度 至少 为 k 。字符 a 在 subs 中出现奇数次。字符 b 在 subs 中出现偶数次。

返回 最大 差值。

注意 ，subs 可以包含超过 2 个 互不相同 的字符。.

子字符串 是字符串中的一个连续字符序列。

2、解题思路

字母频次计数：

为了方便处理，我们可以将字符串 s 中的字符映射为数字 0 到 4，即用整数表示字符。例如，假设 s 只包含字符 0, 1, 2, 3, 4，我们可以直接用这些数字来进行频率统计。

滑动窗口的应用：

使用 滑动窗口 来遍历字符串中的每一个可能的子字符串，并检查子字符串的频次是否符合题目条件。窗口的大小需要至少为 k，即 right - left + 1 >= k。

频次条件：

我们需要一个子字符串，使得某个字符 a 在子字符串中的出现次数为奇数，另一个字符 b 的出现次数为偶数。通过更新频次并调整窗口的左右指针来找到合适的子字符串。

最大差值的计算：

对于每个字符对 (odd_char, even_char)，我们维护两个频次数组：current_freq（当前子字符串的频次）和 prev_freq（上一个子字符串的频次）。通过滑动窗口不断更新这两个数组，计算最大差值。 3、代码实现 class Solution { public: int maxDifference(string s, int k) { // 常量, 表示一个很大的数, 用于初始化 const int INF = INT_MAX / 2; int result = -INF; // 用于存储最终的最大差值 // 遍历所有可能的字符对 (x, y), 其中 x 和 y 不相同 for (int odd_char = 0; odd_char < 5; ++odd_char) { for (int even_char = 0; even_char < 5; ++even_char) { if (odd_char == even_char) { continue; // 如果两个字符相同, 则跳过 } // 初始化频率数组 int current_freq[5] = {0}; // 当前子串中每个字符的出现次数 int prev_freq[5] = {0}; // 上一个子串中每个字符的出现次数 int min_diff[2][2] = {{INF, INF}, {INF, INF}}; // 最小差值数组 int left = 0; // 左指针, 表示当前子串的起始位置 // 遍历字符串 for (int right = 0; right < s.size(); ++right) { // 增加当前字符的频率 current_freq[s[right] - '0']++; // 当子串长度大于等于 k 且字符 x 和 y 的频次符合要求时 while (right - left + 1 >= k && current_freq[odd_char] > prev_freq[odd_char] && current_freq[even_char] > prev_freq[even_char]) { // 计算当前子串的频次差 int parity_x = prev_freq[odd_char] & 1; // x字符的奇偶性 int parity_y = prev_freq[even_char] & 1; // y字符的奇偶性 // 更新最小差值 min_diff[parity_x][parity_y] = min(min_diff[parity_x][parity_y], prev_freq[odd_char] - prev_freq[even_char]); // 移动左指针, 更新 prev_freq prev_freq[s[left] - '0']++; left++; } // 计算当前的最大差值 result = max(result, current_freq[odd_char] - current_freq[even_char] - min_diff[current_freq[odd_char] & 1 ^ 1][current_freq[even_char] & 1]); } } } return result; } };

4、复杂度分析

时间复杂度： O(n)，其中 n 是字符串 s 的长度。

空间复杂度： O(1)，使用常数空间。