第147场双周赛:子字符串匹配模式、设计任务管理器、最长相邻绝对差递减子序列、删除所有值为某个元素后的最大子数组和

Q1、子字符串匹配模式

1、题目描述

给你一个字符串 s 和一个模式字符串 p ，其中 p 恰好 包含 一个 '*' 符号。

p 中的 '*' 符号可以被替换为零个或多个字符组成的任意字符序列。

如果 p 可以变成 s 的子字符串，那么返回 true ，否则返回 false 。

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

2、解题思路

核心思路

1. 模式 p 中的 '*' 将字符串划分为两部分：left（* 左侧部分）和 right（* 右侧部分）。
2. 我们需要检查：
   • left 是否是字符串 s 的某个前缀。
   • right 是否是字符串 s 的某个后缀，且满足在 left 和 right 之间可以插入任意字符序列。

解题步骤

1. 提取模式的前缀和后缀：通过 '*' 将模式划分为 left 和 right。
2. 前缀匹配：在字符串 s 中查找 left 的位置。
3. 后缀匹配：在 left 之后的字符串中查找是否存在 right。
4. 整体判断：如果满足上述两部分，返回 true；否则返回 false。

3、代码实现

class Solution {
public:bool hasMatch(string s, string p) {// 找到 '*' 的位置size_t starPos = p.find('*');if (starPos == string::npos) { // 如果模式中没有 '*'return false;}// 分离出模式的前缀和后缀string left = p.substr(0, starPos);   // '*' 左侧部分string right = p.substr(starPos + 1); // '*' 右侧部分// 遍历字符串 s 检查是否满足条件for (size_t i = 0; i <= s.size(); ++i) {// 检查是否匹配模式的前缀部分if (i < left.size() ||s.substr(i - left.size(), left.size()) != left) {continue;}// 如果后缀部分为空，直接匹配成功if (right.empty() || s.substr(i).find(right) != string::npos) {return true;}}// 无法匹配返回 falsereturn false;}
};

4、复杂度分析

时间复杂度分析

1. 遍历字符串 s：O(n)，其中 n 是字符串 s 的长度。
2. 子串匹配操作：O(m)，其中 m 是模式的长度。

综合时间复杂度：O(n * m)。

空间复杂度分析

只使用了常量级空间进行模式划分和子串匹配操作。

空间复杂度：O(1)。

Q2、设计任务管理器

1、题目描述

一个任务管理器系统可以让用户管理他们的任务，每个任务有一个优先级。这个系统需要高效地处理添加、修改、执行和删除任务的操作。

请你设计一个 TaskManager 类：

• TaskManager(vector<vector<int>>& tasks) 初始化任务管理器，初始化的数组格式为 [userId, taskId, priority] ，表示给 userId 添加一个优先级为 priority 的任务 taskId 。
• void add(int userId, int taskId, int priority) 表示给用户 userId 添加一个优先级为 priority 的任务 taskId ，输入 保证 taskId 不在系统中。
• void edit(int taskId, int newPriority) 更新已经存在的任务 taskId 的优先级为 newPriority 。输入 保证 taskId 存在于系统中。
• void rmv(int taskId) 从系统中删除任务 taskId 。输入 保证 taskId 存在于系统中。
• int execTop() 执行所有用户的任务中优先级 最高 的任务，如果有多个任务优先级相同且都为 最高 ，执行 taskId 最大的一个任务。执行完任务后，taskId 从系统中 删除 。同时请你返回这个任务所属的用户 userId 。如果不存在任何任务，返回 -1 。

注意 ，一个用户可能被安排多个任务。

2、解题思路

数据结构设计

我们需要以下两个数据结构：

1. 任务表 tasks：
   • 类型：unordered_map<int, pair<int, int>>
   • 功能：通过 taskId 快速找到任务的 userId 和 priority。
   • 键：taskId，值：{userId, priority}。
2. 全局任务集合 globalTasks：
   • 类型：set<pair<int, int>, greater<>>
   • 功能：按优先级降序排列所有任务（若优先级相同，按 taskId 降序排列），用于快速查找最高优先级任务。
   • 元素：{priority, taskId}。

3、代码实现

class TaskManager {
private:// 存储每个任务的详细信息: taskId -> {userId, priority}unordered_map<int, pair<int, int>> tasks;// 全局任务集合: {priority, taskId}, 按优先级降序排列, 优先级相同时按 taskId 降序set<pair<int, int>, greater<>> globalTasks;public:// 构造函数, 初始化任务管理器TaskManager(vector<vector<int>>& tasksInit) {for (const auto& task : tasksInit) {int userId = task[0], taskId = task[1], priority = task[2];add(userId, taskId, priority);}}// 添加任务void add(int userId, int taskId, int priority) {tasks[taskId] = {userId, priority};    // 在任务表中记录任务信息globalTasks.emplace(priority, taskId); // 添加到全局任务集合}// 修改任务优先级void edit(int taskId, int newPriority) {auto [userId, oldPriority] = tasks[taskId]; // 获取任务的用户和旧优先级globalTasks.erase({oldPriority, taskId});   // 从全局任务集合中移除旧任务tasks[taskId].second = newPriority;         // 更新任务的优先级globalTasks.emplace(newPriority, taskId);   // 添加更新后的任务到集合}// 删除任务void rmv(int taskId) {auto [userId, priority] = tasks[taskId];    // 获取任务信息globalTasks.erase({priority, taskId});      // 从全局任务集合中删除tasks.erase(taskId);                        // 从任务表中删除}// 执行最高优先级任务int execTop() {// 如果没有任务, 返回 -1if (globalTasks.empty()) {return -1;}// 获取全局任务集合中的最高优先级任务auto [priority, taskId] = *globalTasks.begin();int userId = tasks[taskId].first;           // 获取任务所属用户rmv(taskId);                                // 删除任务return userId;}
};

4、复杂度分析

时间复杂度

• 添加任务：O(log n)（由于 set 操作）。
• 修改任务优先级：O(log n)。
• 删除任务：O(log n)。
• 执行最高优先级任务：O(log n)。

空间复杂度

• O(n)，存储任务表和任务集合的空间。

Q3、最长相邻绝对差递减子序列

1、题目描述

给你一个整数数组 nums 。

你的任务是找到 nums 中的 最长子序列 seq ，这个子序列中相邻元素的 绝对差 构成一个 非递增 整数序列。换句话说，nums 中的序列 seq0, seq1, seq2, …, seqm 满足 |seq1 - seq0| >= |seq2 - seq1| >= ... >= |seqm - seqm - 1| 。

请你返回这个子序列的长度。

一个 子序列 指的是从一个数组中删除零个或多个元素后，剩下元素不改变顺序得到的 非空 数组。

2、解题思路

我们使用动态规划（Dynamic Programming, DP）来解决此问题。

定义动态规划状态

1. 状态定义：
   • dpLeft[i][j] 表示以 nums[i] 为最后一个元素，倒数第二个元素不大于 j 的最长子序列长度。
   • dpRight[i][j] 表示以 nums[i] 为最后一个元素，倒数第二个元素不小于 j 的最长子序列长度。
2. 初始状态：
   • 当序列中只有一个元素时，任何合法的 j 都可以使得子序列长度为 1。
3. 转移方程：
   • 当前元素为 nums[i]，倒数第二个元素为 j：
     • dpLeft[nums[i]][j] = max(dpLeft[j][lowerBound], dpRight[j][upperBound]) + 1，其中：
       • lowerBound 是满足 abs(nums[i] - j) 范围内的最小值。
       • upperBound 是满足 abs(nums[i] - j) 范围内的最大值。
   • 类似地更新 dpRight。
4. 优化：
   • 利用前缀和后缀最大值数组快速计算 lowerBound 和 upperBound，避免暴力遍历。

3、代码实现

class Solution {
public:int longestSubsequence(vector<int>& nums) {int n = nums.size(); // 数组长度int maxValue = 0;    // 数组中元素的最大值for (int num : nums) {maxValue = max(maxValue, num);}const int INF = 1e9;// dpLeft[i][j]: 子序列最后一个元素为 i, 倒数第二个元素不大于 j 的最长长度 // dpRight[i][j]: 子序列最后一个元素为 i, 倒数第二个元素不小于 j 的最长长度// 注意到第二维的取值范围是 0 ~ m + 1, 这是为了处理序列里只有一个元素的情况。我们认为 0 表示负无穷, m + 1 表示正无穷。vector<vector<int>> dpLeft(maxValue + 2, vector<int>(maxValue + 2, -INF));vector<vector<int>> dpRight(maxValue + 2, vector<int>(maxValue + 2, -INF));// 初始化第一个元素for (int j = 0; j <= maxValue + 1; ++j) {dpLeft[nums[0]][j] = 1;dpRight[nums[0]][j] = 1;}// 遍历数组, 逐步更新动态规划数组for (int i = 1; i < n; ++i) {vector<int> prefixMax(maxValue + 2, 1); // 前缀最大值vector<int> suffixMax(maxValue + 2, 1); // 后缀最大值// 计算当前元素可能的最长子序列for (int j = 1; j <= maxValue; ++j) {int diff = abs(nums[i] - j); // 计算绝对差int lowerBound = max(0, j - diff);int upperBound = min(maxValue + 1, j + diff);// 利用前后缀数组更新当前值prefixMax[j] = suffixMax[j] = max(dpLeft[j][lowerBound], dpRight[j][upperBound]) + 1;}// 更新前缀和后缀的最大值for (int j = 1; j <= maxValue + 1; ++j) {prefixMax[j] = max(prefixMax[j], prefixMax[j - 1]);}for (int j = maxValue; j >= 0; --j) {suffixMax[j] = max(suffixMax[j], suffixMax[j + 1]);}// 将结果更新到动态规划表for (int j = 0; j <= maxValue + 1; ++j) {dpLeft[nums[i]][j] = max(dpLeft[nums[i]][j], prefixMax[j]);dpRight[nums[i]][j] = max(dpRight[nums[i]][j], suffixMax[j]);}}// 找到最长子序列的长度int result = 0;for (int i = 1; i <= maxValue; ++i) {result = max(result, dpLeft[i][maxValue + 1]);}return result;}
};

4、复杂度分析

时间复杂度：

• 外层循环遍历数组：O(n)。
• 内层动态规划更新：处理前缀和后缀数组的复杂度为 O(maxValue)。
• 总复杂度为 O(n * maxValue)。

空间复杂度：

• 动态规划数组 dpLeft 和 dpRight 占用 O(maxValue^2) 空间。

Q4、删除所有值为某个元素后的最大子数组和

1、题目描述

给你一个整数数组 nums 。

你可以对数组执行以下操作 至多 一次：

• 选择 nums 中存在的 任意 整数 X ，确保删除所有值为 X 的元素后剩下数组 非空 。
• 将数组中 所有 值为 X 的元素都删除。

请你返回 所有 可能得到的数组中 最大 子数组和为多少。

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

2、解题思路

核心思想

使用线段树来高效维护区间的最大子数组和，并动态模拟删除某个值 X 的影响：

1. 初始化线段树，计算原数组的最大子数组和。
2. 遍历数组的所有值 X，对于每个值：
   • 暂时将数组中所有等于 X 的元素变为 0，并更新线段树。
   • 计算修改后的最大子数组和。
   • 恢复原数组，并更新线段树。
3. 返回所有可能情况下的最大子数组和。

数据结构

1. 线段树节点结构:
   • sum：区间总和。
   • leftMax：从左侧开始的最大子段和。
   • rightMax：从右侧开始的最大子段和。
   • maxSum：区间内的最大子数组和。
2. 辅助哈希表： 用于记录每个值在数组中的所有索引，方便快速定位需要更新的元素。

3、代码实现

class Solution {
public:long long maxSubarraySum(vector<int>& nums) {int n = nums.size();// 特殊情况处理: 如果数组中所有元素都 <= 0, 只能选择最大的负数int maxElement = *max_element(nums.begin(), nums.end());if (maxElement <= 0) {return maxElement;}// 线段树节点结构struct SegmentTreeNode {long long sum;      // 区间总和long long leftMax;  // 左侧子段最大和long long rightMax; // 右侧子段最大和long long maxSum;   // 区间内的最大子数组和};// 初始化线段树数组vector<SegmentTreeNode> segmentTree(n * 4);// 合并两个区间的函数auto mergeNodes = [&](const SegmentTreeNode& left, const SegmentTreeNode& right) -> SegmentTreeNode {return {left.sum + right.sum, // 总和为左右区间的总和之和max(left.leftMax, left.sum + right.leftMax), // 左侧子段最大和max(right.rightMax, right.sum + left.rightMax), // 右侧子段最大和max({left.maxSum, right.maxSum, left.rightMax + right.leftMax}) // 最大子数组和};};// 根据单个值创建节点auto createNode = [&](int value) -> SegmentTreeNode {return {value, value, value, value};};// 建立线段树auto buildTree = [&](auto&& self, int node, int start, int end) -> void {if (start == end) {// 叶子节点segmentTree[node] = createNode(nums[start]);} else {int mid = (start + end) / 2;int leftChild = node * 2, rightChild = node * 2 + 1;// 递归建立左右子树self(self, leftChild, start, mid);self(self, rightChild, mid + 1, end);// 合并左右子树信息segmentTree[node] = mergeNodes(segmentTree[leftChild], segmentTree[rightChild]);}};// 更新线段树auto updateTree = [&](auto&& self, int node, int start, int end, int idx, int value) -> void {if (start == end) {// 更新叶子节点segmentTree[node] = createNode(value);} else {int mid = (start + end) / 2;int leftChild = node * 2, rightChild = node * 2 + 1;if (idx <= mid) {self(self, leftChild, start, mid, idx, value);} else {self(self, rightChild, mid + 1, end, idx, value);}// 合并左右子树信息segmentTree[node] = mergeNodes(segmentTree[leftChild], segmentTree[rightChild]);}};// 初始化线段树buildTree(buildTree, 1, 0, n - 1);// 初始情况下的最大子数组和long long result = segmentTree[1].maxSum;// 映射值到索引，用于快速找到需要删除的元素位置unordered_map<int, vector<int>> valueToIndices;for (int i = 0; i < n; ++i) {valueToIndices[nums[i]].push_back(i);}// 遍历所有可能删除的值for (const auto& entry : valueToIndices) {const vector<int>& indices = entry.second;int value = entry.first;// 如果数组中只有此一个值，跳过if (indices.size() == n) {continue;}// 将所有等于该值的元素暂时设置为 0for (int index : indices) {updateTree(updateTree, 1, 0, n - 1, index, 0);}// 更新最大子数组和result = max(result, segmentTree[1].maxSum);// 恢复原值for (int index : indices) {updateTree(updateTree, 1, 0, n - 1, index, value);}}return result;}
};

4、复杂度分析

时间复杂度：

• 初始化线段树：O(n)。
• 遍历数组元素进行更新：每次更新 O(log⁡n)，最多更新 n 次，因此复杂度为 O(nlog⁡n)。
• 总复杂度：O(nlog⁡n)。

空间复杂度：

• 线段树占用 O(n) 空间。
• 哈希表存储索引，额外占用 O(n)) 空间。
• 总空间复杂度：O(n)。