第425场周赛:最小正和子数组、重排子字符串以形成目标字符串、最小数组和、移除边之后的权重最大和

Q1、[简单] 最小正和子数组

1、题目描述

给你一个整数数组 nums 和 两个 整数 l 和 r。你的任务是找到一个长度在 l 和 r 之间（包含）且和大于 0 的 子数组 的 最小 和。

返回满足条件的子数组的 最小 和。如果不存在这样的子数组，则返回 -1。

子数组 是数组中的一个连续 非空 元素序列。

2、解题思路

1. 滑动窗口：
   • 使用滑动窗口遍历数组，可以高效地计算子数组和。
   • 在窗口长度范围内逐一检查是否满足条件。
2. 暴力双层循环优化：
   • 第一层循环选择子数组的左边界。
   • 第二层循环从左边界延伸到右边界，并动态累加子数组的和，避免重复计算。
3. 判断合法性：
   • 每当子数组的长度满足 [l,r] 且和大于 0 时，记录其和。
   • 更新符合条件的最小和。
4. 最终结果：
   • 如果遍历完数组仍未找到符合条件的子数组，返回 −1 。

3、代码实现

int minimumSumSubarray(vector<int>& nums, int l, int r) {int n = nums.size();int minSum = INT_MAX; // 初始化最小和为无穷大int left = 0; // 滑动窗口的左边界// 遍历数组的每个起始点作为窗口的左边界while (left < n) {int right = left; // 窗口的右边界从左边界开始int currentSum = 0; // 当前窗口的和// 扩展右边界，直到窗口长度超过 r 或到达数组末尾while (right < n && right - left + 1 <= r) {currentSum += nums[right]; // 累加当前窗口的和// 判断当前窗口是否满足长度 [l, r] 且和大于 0if (right - left + 1 >= l && currentSum > 0) {minSum = min(minSum, currentSum); // 更新最小和}++right; // 扩展右边界}++left; // 移动左边界}// 如果没有符合条件的子数组，返回 -1；否则返回最小和return minSum == INT_MAX ? -1 : minSum;
}

4、复杂度

时间复杂度分析

• 外层循环：左边界最多遍历 n 次。
• 内层循环：右边界最多遍历 r 次（窗口长度限制为 r）。
• 总复杂度：O(n⋅r)，其中 r 是窗口的最大长度。

空间复杂度分析

• 仅使用常数额外空间，空间复杂度为 O(1) 。

Q2、[中等] 重排子字符串以形成目标字符串

1、题目描述

给你两个字符串 s 和 t（它们互为字母异位词），以及一个整数 k。

你的任务是判断是否可以将字符串 s 分割成 k 个等长的子字符串，然后重新排列这些子字符串，并以任意顺序连接它们，使得最终得到的新字符串与给定的字符串 t 相匹配。

如果可以做到，返回 true；否则，返回 false。

字母异位词 是指由另一个单词或短语的所有字母重新排列形成的单词或短语，使用所有原始字母恰好一次。

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

2、解题思路

基本条件判断：

• 如果 s 和 t 的长度不同，直接返回 false。
• 如果字符串长度不能被 k 整除，无法将字符串等分为 k 段，返回 false。

字符频率验证：

• s 和 t 是字母异位词，它们的字符频率应该完全相同。
• 使用哈希表统计 s 和 t 的字符频率，如果两者不相等，返回 false。

检查分割和重排：

• 将 s 分割成 k 个子字符串，并统计这些子字符串的频率。
• 将 t 也分割成 k 个子字符串，验证是否可以通过重新排列 s 的子字符串匹配 t 的分割。

返回结果：

• 如果所有子字符串都能被正确匹配，返回 true，否则返回 false。

3、代码实现

class Solution {
public:bool isPossibleToRearrange(string s, string t, int k) {int n = s.size();// 基础条件判断if (n != t.size() || n % k != 0) {return false;}int segmentLength = n / k; // 每个子字符串的长度// 统计 s 和 t 的字符频率unordered_map<char, int> sFreq, tFreq;for (char c : s)sFreq[c]++;for (char c : t)tFreq[c]++;// 验证 s 和 t 的字符频率是否完全相等if (sFreq != tFreq) {return false;}// 检查能否将 s 分割成 k 个子串，每个子串重排后匹配 t 的子串unordered_map<string, int> hash;for (int i = 0; i < n; i += segmentLength) {string tmp = s.substr(i, segmentLength); // 提取 s 的子字符串hash[tmp]++;}for (int i = 0; i < n; i += segmentLength) {string tmp = t.substr(i, segmentLength); // 提取 t 的子字符串if (!hash.count(tmp)) {return false; // 如果对应的子字符串不存在，返回 false} else {if ((--hash[tmp]) == 0) {hash.erase(tmp); // 减少频率，并在频率为 0 时移除}}}return true; // 所有子字符串都能匹配}
};

代码详细注释

1. 基本条件判断：
   • 如果 s 和 t 的长度不同，或者 n%k≠0，无法分割为 k 段，直接返回 false。
   • 计算每个子字符串的长度 segmentLength = n / k。
2. 统计字符频率：
   • 使用哈希表 sFreq 和 tFreq 分别统计 s 和 t 的字符频率。
   • 如果两者频率不相同，说明 s 和 t 无法通过重排列匹配，返回 false。
3. 统计子字符串频率：
   • 遍历 s，将其分割为 k 段子字符串，统计每段出现的频率存入哈希表 hash。
   • 遍历 t，检查分割出的每段是否可以通过重排列匹配 s 的分割子字符串。
4. 子字符串匹配：
   • 如果 t 的某段子字符串在 hash 中不存在，说明匹配失败。
   • 每次匹配成功后，减少对应子字符串的频率，当频率为 0 时将其移除。
5. 返回结果：
   • 如果所有子字符串匹配成功，返回 true，否则返回 false。

4、复杂度

时间复杂度分析

1. 字符频率统计：
   • 遍历 s 和 t，时间复杂度为 O(n)。
2. 子字符串分割与统计：
   • 遍历 s 和 t 分割为 k 段，每段长度为 n/k。总时间复杂度为 O(n)。
3. 总复杂度：
   • 整体复杂度为 O(n)，其中 n 是字符串 s 和 t 的长度。

空间复杂度分析

1. 字符频率哈希表：
   • 需要额外的空间存储字符频率和子字符串频率，空间复杂度为 O(m)，其中 m 是字符集大小（对于英文字母最多为 26）。
2. 总空间复杂度：
   • 空间复杂度为 O(m+k)，其中 k 是分割出的子字符串数量。

Q3、[中等] 最小数组和

1、题目描述

给你一个整数数组 nums 和三个整数 k、op1 和 op2。

你可以对 nums 执行以下操作：

• 操作 1：选择一个下标 i，将 nums[i] 除以 2，并 向上取整 到最接近的整数。你最多可以执行此操作 op1 次，并且每个下标最多只能执行一次。
• 操作 2：选择一个下标 i，仅当 nums[i] 大于或等于 k 时，从 nums[i] 中减去 k。你最多可以执行此操作 op2 次，并且每个下标最多只能执行一次。

注意： 两种操作可以应用于同一下标，但每种操作最多只能应用一次。

返回在执行任意次数的操作后，nums 中所有元素的 最小 可能 和 。

2、解题思路

核心思想：
使用动态规划 (Dynamic Programming, DP) 方法，逐步计算在指定的操作次数限制下，nums 中前若干元素能达到的最小和。

动态规划的状态转移基于以下思路：

1. 每个元素在当前操作次数的约束下，可能有多种结果：
   • 不对该元素使用任何操作。
   • 对该元素使用操作 1 或操作 2。
   • 对该元素同时使用操作 1 和操作 2（若条件允许）。
2. 根据上述情况，选择所有可能结果的最小值更新当前状态。

解题步骤

1. 状态定义

• 三维 DP（递归解法）：
  memo[i][op1][op2] 表示处理到第 i 个元素时，最多使用 op1 次操作 1 和 op2 次操作 2 的最小数组和。
• 二维 DP（迭代优化解法）：
  f[p][q] 表示在当前元素下，使用最多 p 次操作 1 和 q 次操作 2 时的最小数组和。

2. 状态转移方程

• 如果不对当前元素执行任何操作：

  res = f[p][q] + x;
  

• 如果对当前元素执行操作 1：

  res = min(res, f[p-1][q] + (x + 1) / 2);
  

• 如果对当前元素执行操作 2 (且 x >= k) ：

  res = min(res, f[p][q-1] + x - k);
  

• 如果对当前元素同时执行操作 1 和操作 2 (且 x >= k 且 p > 0)：

  reducedTwiceX = (x + 1) / 2 >= k ? (x + 1) / 2 - k : (x - k + 1) / 2;
  res = min(res, f[p-1][q-1] + reducedTwiceX);
  

3. 返回值
最终结果为 f[n][op1][op2]，即在处理完所有元素后，最多使用 op1 次操作 1 和 op2 次操作 2 的最小数组和。

3、代码实现

解法 1：递归 + 记忆化搜索

class Solution {
public:int minArraySum(vector<int>& nums, int k, int op1, int op2) {int n = nums.size();// 初始化记忆化数组, memo[i][op1][op2] 表示在第 i 个元素及之前, 使用 op1 次操作 1 和 op2 次操作 2 的最小数组和。vector<vector<vector<int>>> memo(n, vector<vector<int>>(op1 + 1, vector<int>(op2 + 1, -1)));// 深度优先搜索函数, 使用 lambda 捕获自身 dfs。auto dfs = [&](auto&& dfs, int i, int remainingOp1, int remainingOp2) -> int {// 递归基: 如果索引越界, 返回 0, 因为没有元素可以处理。if (i < 0) {return 0;}// 引用当前状态的结果, 避免多次重复计算。int& res = memo[i][remainingOp1][remainingOp2];// 如果已经计算过, 直接返回结果。if (res != -1) {return res;}// 获取当前元素值。int x = nums[i];// 初始化为不使用任何操作时的情况: 跳过当前元素, 继续处理前面的元素。res = dfs(dfs, i - 1, remainingOp1, remainingOp2) + x;// 尝试使用操作 1 (将当前元素除以2并向上取整), 如果还可以使用操作 1。if (remainingOp1 > 0) {int reducedX = (x + 1) / 2; // 计算操作 1 后的值。res = min(res, dfs(dfs, i - 1, remainingOp1 - 1, remainingOp2) + reducedX);}// 尝试使用操作 2 (从当前元素中减去 k), 如果还可以使用操作 2 且当前值 >= k。if (remainingOp2 > 0 && x >= k) {int reducedX = x - k; // 计算操作2后的值。res = min(res, dfs(dfs, i - 1, remainingOp1, remainingOp2 - 1) + reducedX);// 如果同时使用操作 1 和操作 2, 计算结果并更新最优值。if (remainingOp1 > 0) {int reducedTwiceX = (x + 1) / 2 >= k ? (x + 1) / 2 - k : (x - k + 1) / 2;res = min(res, dfs(dfs, i - 1, remainingOp1 - 1, remainingOp2 - 1) + reducedTwiceX);}}// 返回当前状态的最优解。return res;};// 从数组的最后一个元素开始递归, 初始操作次数为 op1 和 op2。return dfs(dfs, n - 1, op1, op2);}
};

解法 2：动态规划（迭代解法）

class Solution {
public:int minArraySum(vector<int>& nums, int k, int op1, int op2) {// 定义 DP 数组 f[p][q]// f[p][q] 表示使用最多 p 次操作 1 和 q 次操作 2 时, 当前元素的最小数组和vector<vector<int>> f(op1 + 1, vector<int>(op2 + 1, 0));// 遍历每个数组元素for (int x : nums) {// 倒序遍历操作次数, 防止状态更新覆盖影响其他计算for (int p = op1; p >= 0; p--) {for (int q = op2; q >= 0; q--) {// 初始化当前状态的最小值int res = f[p][q] + x; // 不使用任何操作// 尝试使用操作 1: 将 x 除以 2 并向上取整if (p > 0) {int reducedX = (x + 1) / 2; // 操作 1 的结果res = min(res, f[p - 1][q] + reducedX);}// 尝试使用操作 2: 从 x 减去 k (仅当 x >= k 时才有效)if (q > 0 && x >= k) {int reducedX = x - k; // 操作 2 的结果res = min(res, f[p][q - 1] + reducedX);// 同时尝试使用操作 1 和操作 2if (p > 0) {// 计算两种操作同时执行后的值int reducedTwiceX = (x + 1) / 2 >= k ? (x + 1) / 2 - k : (x - k + 1) / 2;res = min(res, f[p - 1][q - 1] + reducedTwiceX);}}// 更新状态f[p][q] = res;}}}// 返回最终结果, 即最多使用 op1 次操作1和 op2 次操作 2 后的最小数组和return f[op1][op2];}
};

4、复杂度分析

时间复杂度：

• 递归解法：O(n * op1 * op2)（每次状态查询的复杂度为常数）。
• 动态规划解法：O(n * op1 * op2)（每个状态需遍历两个操作次数）。

空间复杂度：

• 递归解法：O(n * op1 * op2)（记忆化数组）。
• 动态规划解法：O(op1 * op2)（二维 DP 数组）。

Q4、[困难] 移除边之后的权重最大和

1、题目描述

存在一棵具有 n 个节点的无向树，节点编号为 0 到 n - 1。给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ui, vi, wi] 表示在树中节点 ui 和 vi 之间有一条权重为 wi 的边。

你的任务是移除零条或多条边，使得：

• 每个节点与至多 k 个其他节点有边直接相连，其中 k 是给定的输入。
• 剩余边的权重之和 最大化 。

返回在进行必要的移除后，剩余边的权重的 最大 可能和。

2、解题思路

建图
将输入的 edges 转换为图的邻接表表示，方便进行深度优先搜索。

提前判断特殊情况
如果树中所有节点的度数都不超过 k，则不需要移除任何边，直接返回所有边的总权重。

深度优先搜索 (DFS)
在限制条件下，递归计算每个节点是否选择与其父节点相连，以及如何在子节点中分配边以最大化权重和：

• 定义两种状态：
  • notChoose：当前节点不选择与其父节点相连时，子树中的最大权重和。
  • choose：当前节点选择与其父节点相连时，子树中的最大权重和。
• 递归处理每个节点，动态计算增量值，选择权重增量最大的若干条边。

增量排序
在每个节点的子树中，选择能够提供最大收益（权重增量）的边，这些增量从大到小排序，并取前 k-1 个增量。

动态规划递归返回
通过递归返回值，结合当前节点的增量值，逐步计算出最终结果。

3、代码实现

class Solution {
public:long long maximizeSumOfWeights(vector<vector<int>>& edges, int k) {int n = edges.size() + 1; // 节点数vector<vector<pair<int, int>>> graph(n);long long totalWeight = 0;// 构建无向图并计算总权重for (const auto& edge : edges) {int u = edge[0], v = edge[1], weight = edge[2];graph[u].emplace_back(v, weight);graph[v].emplace_back(u, weight);totalWeight += weight;}// 检查是否可以直接返回总权重 (即所有节点的度数均 <= k)bool isSimple = true;for (const auto& neighbors : graph) {if (neighbors.size() > k) {isSimple = false;break;}}if (isSimple) {return totalWeight;}// 定义 DFS 函数auto dfs = [&](auto& self, int node, int parent) -> pair<long long, long long> {// notChoose: 当前节点及其子树的最大权重和, 当前节点不与父节点相连// choose: 当前节点及其子树的最大权重和, 当前节点与父节点相连long long notChoose = 0;vector<int> increment; // 增量列表// 遍历子节点for (const auto& [neighbor, weight] : graph[node]) {// 忽略回到父节点的边if (neighbor == parent) {continue;}// 子树递归计算auto [subtreeNotChoose, subtreeChoose] = self(self, neighbor, node);// 默认选择子树的 notChoosenotChoose += subtreeNotChoose;// 计算从 notChoose 到 choose 的增量int delta = subtreeChoose + weight - subtreeNotChoose;if (delta > 0) {increment.push_back(delta);}}// 按增量从大到小排序ranges::sort(increment, greater());// 增量取前 k-1 个加到 notChoose 中for (int i = 0; i < min((int)increment.size(), k - 1); ++i) {notChoose += increment[i];}// 计算 choose, 尝试额外选择第 k 个增量long long choose = notChoose;if (increment.size() >= k) {notChoose += increment[k - 1];}return {notChoose, choose};};// 从根节点 (0号节点) 开始 DFS, 返回最大可能权重和return dfs(dfs, 0, -1).first;}
};

4、复杂度分析

时间复杂度

• 遍历构建图：O(n)，其中 n 是节点数。
• DFS 递归：O(n)，每个节点访问一次。
• 增量排序：O(klog⁡k)，每个节点对其子节点的增量排序。
• 总时间复杂度：O(n+klog⁡k)。

空间复杂度

• 图的存储：O(n)。
• 递归栈：最坏情况下 O(n)。
• 总空间复杂度：O(n)。