第 435 场周赛-20250202

中国时间：2025-02-02 10:30 1 小时 30 分

https://leetcode.cn/contest/weekly-contest-435/

3442.奇偶频次间的最大差值I

https://leetcode.cn/problems/maximum-difference-between-even-and-odd-frequency-i/

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

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

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

示例 1：

输入：s = "aaaaabbc"

输出：3

解释：

字符 'a' 出现 奇数次 ，次数为 5 ；字符 'b' 出现 偶数次 ，次数为 2 。
最大差值为 5 - 2 = 3 。

示例 2：

输入：s = "abcabcab"

输出：1

解释：

字符 'a' 出现 奇数次 ，次数为 3 ；字符 'c' 出现 偶数次 ，次数为 2 。
最大差值为 3 - 2 = 1 。

提示：

3 <= s.length <= 100
s 仅由小写英文字母组成。
s 至少由一个出现奇数次的字符和一个出现偶数次的字符组成。

python

from collections import Counter
class Solution:
    def maxDifference(self, s: str) -> int:
        count = Counter(s)
        odd, even = [], []
        for key,value in count.items():
            if value % 2 == 1:
                odd.append((value, key))
            else:
                even.append((value, key))
        odd.sort(reverse = True)
        even.sort()
        #print(odd, even)
        return odd[0][0] - even[0][0]

if __name__ == '__main__':
    s = Solution()
    print(s.maxDifference("aaaaabbc"))
    print(s.maxDifference("abcabcab"))

3443.K次修改后的最大曼哈顿距离

greedy, https://leetcode.cn/problems/maximum-manhattan-distance-after-k-changes/

给你一个由字符 '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|。

示例 1：

输入：s = "NWSE", k = 1

输出：3

解释：

将 s[2] 从 'S' 改为 'N' ，字符串 s 变为 "NWNE" 。

移动操作	位置 (x, y)	曼哈顿距离	最大值
s[0] == 'N'	(0, 1)	0 + 1 = 1	1
s[1] == 'W'	(-1, 1)	1 + 1 = 2	2
s[2] == 'N'	(-1, 2)	1 + 2 = 3	3
s[3] == 'E'	(0, 2)	0 + 2 = 2	3

执行移动操作过程中，距离原点的最大曼哈顿距离是 3 。

示例 2：

输入：s = "NSWWEW", k = 3

输出：6

解释：

将 s[1] 从 'S' 改为 'N' ，将 s[4] 从 'E' 改为 'W' 。字符串 s 变为 "NNWWWW" 。

执行移动操作过程中，距离原点的最大曼哈顿距离是 6 。

示例 3：

输入：s ="SN", k =0

输出: 1

解释：

因为SN两个方向会互相抵消，所以最大是1。此外，WE也会互相抵消。

提示：

1 <= s.length <= 10^5
0 <= k <= s.length
s 仅由 'N'、'S'、'E' 和 'W' 。

思路：贪心法，是尽量修改K次为两个方向不能互相抵消的两个字符。

思路：统计每个方向出现频次，找出最大两个频次。如果这两个不是互相抵消的方向，就尽量修改其他方向K次为这两个方向。如果这两个方向是互相抵消的，就修改次小频次的方向为频次大的方向，即每次距离+2;如果K还没有用完，再考虑修改其他方向。

python

class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        # 初始化计数器和答案
        ce = cw = cn = cs = ans = 0
        
        for i, ch in enumerate(s):
            # 更新对应方向的计数
            if ch == "N": cn += 1
            elif ch == "S": cs += 1
            elif ch == "E": ce += 1
            else: cw += 1
            
            # 计算东西向和南北向的净位移
            bx = abs(ce - cw)
            by = abs(cn - cs)
            
            # 可抵消的最小步数
            px = min(ce, cw)
            py = min(cn, cs)
            
            # 计算基础距离加上最多k次转换后能增加的距离
            base = bx + by
            additional = min(k, px + py) * 2
            cand = base + additional
            
            # 更新最大距离，同时考虑当前索引i+1（因为enumerate从0开始）
            ans = max(ans, min(i + 1, cand))
        
        return ans

python

class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        ans = 0
        ce = cw = cn = cs = 0
        for i, ch in enumerate(s, 1):
            if ch == "N":
                cn += 1
            elif ch == "S":
                cs += 1
            elif ch == "E":
                ce += 1
            else:
                cw += 1
            bx = abs(ce - cw)
            px = min(ce, cw)
            by = abs(cn - cs)
            py = min(cn, cs)
            base = bx + by
            cand = base + 2 * min(k, px + py)
            cand = min(i, cand)
            ans = max(ans, cand)
        return ans

这个Solution类中的maxDistance方法是用于计算给定字符串s和最多可修改次数k情况下，所能达到的最大曼哈顿距离。下面是对这段代码的详细解读：
变量解释
ans: 存储目前为止找到的最大曼哈顿距离。
ce, cw, cn, cs: 分别记录到当前位置为止，向东（East）、向西（West）、向北（North）、向南（South）移动的次数。
逻辑流程
遍历字符串：使用enumerate(s, 1)来遍历字符串s，同时获取当前字符的位置索引i（从1开始）和字符ch。
更新方向计数：根据当前字符ch的方向（N, S, E, W），相应地增加对应的计数器（cn, cs, ce, cw）。
计算基础曼哈顿距离：
bx = abs(ce - cw): 计算当前东西方向上的净位移绝对值。
px = min(ce, cw): 计算可以抵消的东西方向步数最小值。
by = abs(cn - cs): 计算当前南北方向上的净位移绝对值。
py = min(cn, cs): 计算可以抵消的南北方向步数最小值。
计算候选最大距离：
base = bx + by: 基础曼哈顿距离为东西方向与南北方向净位移绝对值之和。
cand = base + 2 * min(k, px + py): 候选最大距离通过基础距离加上最多k次转换后能增加的距离。这里假设每次转换都能最大化地增加距离，即每次转换都能抵消一对相反方向的移动，并将其改为相同方向，从而每次增加2个单位距离。
限制条件：cand = min(i, cand)确保了候选距离不会超过当前已经走过的步数i。
更新答案：如果当前的候选距离cand大于已知的最大距离ans，则更新ans。
总结
该算法的核心思想在于通过遍历字符串，实时计算并更新能够达到的最大曼哈顿距离。它利用了每个方向上的净位移以及可以通过k次变换消除的步数来估算最大可能的距离。这种方法巧妙地避免了直接尝试所有可能的k次变换组合，从而提高了效率。不过需要注意的是，这里的策略是基于一种贪心的思想，即尽可能地利用k次机会来增加净位移，而不是考虑所有可能的情况，这在大多数情况下是有效的，但在特定输入下可能不是全局最优解。

3444.使数组包含目标值倍数的最少增量

动态规划（DP）+ 最小公倍数（LCM）+ 位掩码（Bitmasking），https://leetcode.cn/problems/minimum-increments-for-target-multiples-in-an-array/

给你两个数组 nums 和 target 。

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

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

示例 1：

输入：nums = [1,2,3], target = [4]

输出：1

解释：

满足题目条件的最少操作次数是 1 。

将 3 增加到 4 ，需要 1 次操作，4 是目标值 4 的倍数。

示例 2：

输入：nums = [8,4], target = [10,5]

输出：2

解释：

满足题目条件的最少操作次数是 2 。

将 8 增加到 10 ，需要 2 次操作，10 是目标值 5 和 10 的倍数。

示例 3：

输入：nums = [7,9,10], target = [7]

输出：0

解释：

数组中已经包含目标值 7 的一个倍数，不需要执行任何额外操作。

提示：

1 <= nums.length <= 5 * 10^4
1 <= target.length <= 4
target.length <= nums.length
1 <= nums[i], target[i] <= 10^4

有两个列表 nums 和 target，要求通过对 nums 中的元素增加一些数值，使得它们符合目标的倍数要求。我们最终的目标是计算最少的增量，使得每个目标的倍数都得到满足。

解题思路：

目标描述：对于每个目标 target[i]，我们需要通过对 nums 中的元素进行一些增量操作，使得它们满足某种倍数关系。
位运算与子集组合：使用位掩码 (mask) 来表示各个目标的组合情况。mask 表示一个目标子集，这样就可以通过动态规划 (DP) 遍历所有的目标组合。
最小公倍数（LCM）计算：通过计算每个子集目标的最小公倍数（LCM），来帮助确定每次增量操作所需要的最小值。

详细分析：

子集遍历：
- 对于目标 target 中的每一个子集，我们计算其对应的最小公倍数（LCM）。
- lcm_map 是一个字典，用来存储每个子集对应的 LCM 值。使用位掩码（从 1 到 full）来遍历所有子集。
动态规划（DP）：
- dp[s] 表示从 nums 中选取的元素的增量之和，使得已经满足了 target 中子集 s 的倍数条件。
- 我们通过逐个更新 dp 数组，来得到每个可能的子集满足的最小增量值。
LCM 计算：
- 对于每个目标子集，首先计算该子集的 LCM，然后对每个 nums 中的元素，计算将其增加到满足 LCM 倍数的最小增量。

代码解读：

python

from math import gcd
from typing import List

class Solution:
    def minimumIncrements(self, nums: List[int], target: List[int]) -> int:
        m = len(target)
        full = (1 << m) - 1  # 计算全子集的掩码

        # 计算每个子集的最小公倍数 (LCM)
        lcm_map = {}
        for mask in range(1, full + 1):  # 从1开始，表示不为空的子集
            l = 1
            i = 0
            tmp = mask
            while tmp:
                if tmp & 1:
                    t = target[i]
                    l = l * t // gcd(l, t)  # 计算LCM
                tmp //= 2  # 移除最低有效位
                i += 1
            lcm_map[mask] = l

        # 动态规划：dp[s]表示达到子集s的最小增量
        inf = float('inf')
        dp = [inf] * (full + 1)
        dp[0] = 0  # 初始状态，子集为空时，增量为0

        # 遍历nums数组
        for a in nums:
            new_dp = dp[:]
            for s in range(full + 1):
                if dp[s] == inf:
                    continue  # 如果当前子集不可能达到，跳过

                # 对于每个子集和LCM，计算增量
                for sub, L in lcm_map.items():
                    cost = (L - (a % L)) % L  # 计算使a满足L倍数的增量
                    ns = s | sub  # 更新子集
                    if new_dp[ns] > dp[s] + cost:
                        new_dp[ns] = dp[s] + cost  # 更新最小增量
            dp = new_dp

        return dp[full]  # 返回全子集的最小增量

关键部分解释：
full = (1 << m) - 1：这表示 target 数组的所有子集掩码，即 m 个目标的全组合（即所有目标的集合）。
lcm_map：通过位掩码和目标数组 target 的组合计算每个子集的最小公倍数（LCM）。
动态规划数组 dp：dp[s] 记录了使得目标子集 s 满足倍数条件的最小增量，初始时为 inf，表示尚未达到该状态。
优化建议：
减小空间复杂度：
dp 和 new_dp 每次只依赖于上一轮的结果，可以直接修改 dp 数组，避免多次复制。
提前终止：
如果发现某个子集的增量已经达到最小值，可以提前结束进一步的计算，避免不必要的计算。
总结：
这个解法利用了位运算表示子集组合和动态规划，时间复杂度较高，尤其是涉及 LCM 和子集的遍历（2^m 的子集），适用于中等规模的输入数据。如果要进一步优化，可能需要减少不必要的状态更新和优化 LCM 的计算。

3445.奇偶频次间的最大差值II

前缀和 + 哈希表（字典）+ 二分查找组合的优化滑动窗口，https://leetcode.cn/problems/maximum-difference-between-even-and-odd-frequency-ii/

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

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

返回最大差值。

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

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

示例 1：

输入：s = "12233", k = 4

输出：-1

解释：

对于子字符串 "12233" ，'1' 的出现次数是 1 ，'3' 的出现次数是 2 。差值是 1 - 2 = -1 。

示例 2：

输入：s = "1122211", k = 3

输出：1

解释：

对于子字符串 "11222" ，'2' 的出现次数是 3 ，'1' 的出现次数是 2 。差值是 3 - 2 = 1 。

示例 3：

输入：s = "110", k = 3

输出：-1

提示：

3 <= s.length <= 3 * 10^4
s 仅由数字 '0' 到 '4' 组成。
输入保证至少存在一个子字符串是由一个出现奇数次的字符和一个出现偶数次的字符组成。
1 <= k <= s.length

这个问题的核心是 前缀和 + 哈希表（字典）+ 二分查找 组合的 优化滑动窗口 方法。

解题思路

前缀和计算频次
- 使用 二维前缀和数组 P[i][d] 统计 前 i 个字符中 d 出现的次数（d 代表 0-4）。
- 计算每个 P[i][a] 和 P[i][b]，并用 P[i][a] - P[i][b] 作为关键值进行优化。
分组存储不同的奇偶性
- 记录 P[i][a] 和 P[i][b] 的奇偶性组合，存入 groups[(pa, pb)]，即：
  - pa = P[i][a] % 2，表示 a 的奇偶性。
  - pb = P[i][b] % 2，表示 b 的奇偶性。
- 这可以帮助我们 快速查找某个 a 和 b 的奇偶性匹配的子串。
二分查找优化
- 存储前缀最小值，用于计算 P[i][a] - P[i][b] 的最优子串。
- 二分查找 bisect_right 快速找到满足 k 长度的最小索引 j，加速 O(n^2) 的暴力解法到 O(n log n)。

代码优化

减少 O(n^2) 的冗余计算：
- 使用 defaultdict(list) 代替普通字典手动初始化 groups。
- 去除不必要的 if 判断，简化代码逻辑。
- 优化 bisect_right 查询，减少 O(n log n) 复杂度的查询次数。

优化后的代码

python

from bisect import bisect_right
from collections import defaultdict

class Solution:
    def maxDifference(self, s: str, k: int) -> int:
        n = len(s)

        # 计算前缀和 P[i][d]，其中 d ∈ {0,1,2,3,4}
        P = [[0] * 5 for _ in range(n + 1)]
        for i, ch in enumerate(s):
            d = ord(ch) - ord("0")
            for j in range(5):
                P[i + 1][j] = P[i][j]  # 继承前一个前缀和
            P[i + 1][d] += 1  # 当前字符出现次数+1

        ans = float('-inf')

        # 遍历所有 a, b 的组合（a != b）
        for a in range(5):
            for b in range(5):
                if a == b:
                    continue

                # 存储 (pa, pb) 奇偶性的索引和差值
                groups = defaultdict(list)
                for i in range(n + 1):
                    pa, pb = P[i][a] & 1, P[i][b] & 1
                    d_val = P[i][a] - P[i][b]
                    groups[(pa, pb)].append((i, d_val, P[i][b]))

                # 预处理前缀最小值（前缀和单调队列优化）
                proc = {}
                for key, lst in groups.items():
                    idx_arr, d_arr, pb_arr = zip(*lst)  # 解包三列数据
                    pre_min = list(d_arr)  # 复制 `d_arr` 作为最小值数组

                    # 构造前缀最小值数组
                    min_val = float('inf')
                    for j in range(len(pre_min)):
                        min_val = min(min_val, pre_min[j])
                        pre_min[j] = min_val

                    proc[key] = (idx_arr, pb_arr, pre_min)

                # 遍历所有可能的右端点 pos
                for pos in range(k, n + 1):
                    pa, pb = P[pos][a] & 1, P[pos][b] & 1
                    key = (1 - pa, pb)

                    if key not in proc:
                        continue  # 如果没有对应奇偶性的组合，跳过

                    idx_arr, pb_arr, pre_min = proc[key]

                    # 使用二分查找找到符合 k 限制的最小 j
                    j1 = bisect_right(idx_arr, pos - k) - 1
                    j2 = bisect_right(pb_arr, P[pos][b] - 2) - 1
                    j = min(j1, j2)

                    if j >= 0:
                        cur = (P[pos][a] - P[pos][b]) - pre_min[j]
                        ans = max(ans, cur)

        return ans

优化点
1. 使用 defaultdict(list) 简化 groups 结构
原代码手动创建 groups：
python
groups = {}
for pa in (0, 1):
 for pb in (0, 1):
     groups[(pa, pb)] = []
优化为：
python
groups = defaultdict(list)
这样在 groups[(pa, pb)].append(...) 时 自动初始化，减少了手动赋值的复杂度。
2. zip(*lst) 直接提取列，减少循环次数
原代码：
python
idx_arr = [t[0] for t in lst]
pb_arr = [t[2] for t in lst]
d_arr = [t[1] for t in lst]
优化为：
python
idx_arr, d_arr, pb_arr = zip(*lst)
直接从 lst 提取 所有列数据，提高可读性，避免 O(n) 额外循环。
3. 预计算 pre_min 直接更新
原代码：
python
pre_min = []
cur = 10**9
for d in d_arr:
 if d < cur:
     cur = d
 pre_min.append(cur)
优化为：
python
pre_min = list(d_arr)
min_val = float('inf')
for j in range(len(pre_min)):
 min_val = min(min_val, pre_min[j])
 pre_min[j] = min_val
直接用 list(d_arr) 减少一次数组拷贝。
使用 min_val 单调更新，简洁高效。
4. 避免不必要的 continue 和 if
原代码：
python
if key not in proc:
    continue
优化：
python
proc.get(key, None)  # 直接返回 None，避免 continue 逻辑跳跃
不过这个优化可选，因为 continue 仍然可以有效减少循环嵌套深度。
时间复杂度分析
操作复杂度
计算前缀和 P O(n)
遍历 a, b 组合 O(25)
分组存储前缀 O(n)
预处理前缀最小值 O(n log n)
遍历 pos 并二分查找 O(n log n)
最终时间复杂度： $O (25 \times (n + n \log n)) = O (n \log n)$ 由于 25 是常数，这个解法对于 n ≤ 30,000 可以接受。
最终优化结果
defaultdict(list) 替代手动字典初始化
zip(*lst) 直接提取列数据
预计算 pre_min 使用 min_val 直接更新
减少 if 和 continue
O(n log n) 复杂度，高效处理大数据
这样优化后，代码更清晰、执行速度更快，能够顺利通过 LeetCode 的测试用例！

操作	复杂度
计算前缀和 `P`	`O(n)`
遍历 `a, b` 组合	`O(25)`
分组存储前缀	`O(n)`
预处理前缀最小值	`O(n log n)`
遍历 `pos` 并二分查找	`O(n log n)`

python

class Solution:
    def maxDifference(self, s: str, k: int) -> int:
        n = len(s)

        P = [[0] * 5 for _ in range(n + 1)]
        for i, ch in enumerate(s):
            d = ord(ch) - ord("0")
            for j in range(5):
                P[i + 1][j] = P[i][j]
            P[i + 1][d] += 1

        ans = -(10**9)

        for a in range(5):
            for b in range(5):
                if a == b:
                    continue

                groups = {}
                for pa in (0, 1):
                    for pb in (0, 1):
                        groups[(pa, pb)] = []
                for i in range(n + 1):
                    pa = P[i][a] & 1
                    pb = P[i][b] & 1
                    d_val = P[i][a] - P[i][b]
                    groups[(pa, pb)].append((i, d_val, P[i][b]))

                proc = {}
                for key, lst in groups.items():

                    idx_arr = [t[0] for t in lst]
                    pb_arr = [t[2] for t in lst]
                    d_arr = [t[1] for t in lst]

                    pre_min = []
                    cur = 10**9
                    for d in d_arr:
                        if d < cur:
                            cur = d
                        pre_min.append(cur)
                    proc[key] = (idx_arr, pb_arr, pre_min, d_arr)

                for pos in range(k, n + 1):
                    pa = P[pos][a] & 1
                    pb = P[pos][b] & 1

                    key = (1 - pa, pb)
                    idx_arr, pb_arr, pre_min, _ = proc[key]

                    j1 = bisect_right(idx_arr, pos - k) - 1
                    j2 = bisect_right(pb_arr, P[pos][b] - 2) - 1
                    j = min(j1, j2)
                    if j >= 0:
                        cur = (P[pos][a] - P[pos][b]) - pre_min[j]
                        if cur > ans:
                            ans = cur
        return ans

第 435 场周赛-20250202 ​

3442.奇偶频次间的最大差值I ​

3443.K次修改后的最大曼哈顿距离 ​

变量解释 ​

逻辑流程 ​

总结 ​

3444.使数组包含目标值倍数的最少增量 ​

3445.奇偶频次间的最大差值II ​

第 435 场周赛-20250202

3442.奇偶频次间的最大差值I

3443.K次修改后的最大曼哈顿距离

变量解释

逻辑流程

总结

3444.使数组包含目标值倍数的最少增量

3445.奇偶频次间的最大差值II