第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;
            }
        }

        // 无法匹配返回 false
        return 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() {
        // 如果没有任务, 返回 -1
        if (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;
            }

            // 将所有等于该值的元素暂时设置为 0
            for (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)。