Q1、最长乘积等价子数组

1、题目描述

给你一个由 正整数 组成的数组 nums。

如果一个数组 arr 满足 prod(arr) == lcm(arr) * gcd(arr)，则称其为 乘积等价数组 ，其中：

• prod(arr) 表示 arr 中所有元素的乘积。
• gcd(arr) 表示 arr 中所有元素的最大公因数 (GCD)。
• lcm(arr) 表示 arr 中所有元素的最小公倍数 (LCM)。

返回数组 nums 的 最长 乘积等价子数组 的长度。

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

术语 gcd(a, b) 表示 a 和 b 的 最大公因数 。

术语 lcm(a, b) 表示 a 和 b 的 最小公倍数 。

2、解题思路

核心公式的推导：
根据公式，我们需要检查：

​ $\text{prod(arr)}=\text{lcm(arr)}\times \text{gcd(arr)}$

其中：

• $\text{prod(arr)}$ 是子数组所有元素的乘积；
• $\text{lcm(arr)}$ 是子数组所有元素的最小公倍数，可以通过递归计算得到；
• $\text{gcd(arr)}$ 是子数组所有元素的最大公约数，也可以通过递归计算得到。

暴力枚举子数组：
使用双层循环枚举所有可能的子数组的起点和终点，逐步计算子数组的：

• $\text{prod(arr)}$：通过逐一相乘得到；
• $\text{lcm(arr)}$：动态更新；
• $\text{gcd(arr)}$：动态更新。 对每个子数组，检查是否满足条件。

剪枝优化：

• 如果子数组的乘积 $\text{prod(arr)}$ 超过合理范围（即 $\text{maxElement}\times \text{overallLcm}$），直接提前终止当前循环；
• 用整体数组的最小公倍数 $\text{overallLcm}$ 来限制子数组可能的最大值，减少不必要的计算。

辅助函数：

• lcm(a, b)：计算两个数的最小公倍数。
• gcd(a, b)：计算两个数的最大公约数。

3、代码实现

class Solution {
public:int maxLength(vector<int>& nums) {// 找到数组中的最大值, 用于限制子数组的最大可能 LCM 值int maxElement = *max_element(nums.begin(), nums.end());// 计算整个数组的最小公倍数, 用于减少无效计算int overallLcm = 1;for (int num : nums) {overallLcm = lcm(overallLcm, num);}int maxLength = 0; // 记录满足条件的最长子数组长度// 遍历每个子数组的起点for (int start = 0; start < nums.size(); ++start) {long long product = 1;    // 子数组元素的乘积long long currentLcm = 1; // 子数组的最小公倍数long long currentGcd = 0; // 子数组的最大公约数// 遍历从当前起点开始的子数组for (int end = start; end < nums.size(); ++end) {int currentElement = nums[end];// 更新子数组的乘积、LCM 和 GCDproduct *= currentElement;currentLcm = lcm(currentLcm, currentElement);currentGcd = gcd(currentGcd, currentElement);// 如果乘积等于 LCM * GCD, 则更新最大长度if (product == currentLcm * currentGcd) {maxLength = max(maxLength, end - start + 1);}// 如果当前乘积超过合理范围 (避免无效计算), 提前终止循环if (product > overallLcm * maxElement) {break;}}}return maxLength;}private:// 计算两个数的 LCM（最小公倍数）long long lcm(long long a, long long b) { return (a * b / gcd(a, b));}// 计算两个数的 GCD (最大公约数)long long gcd(long long a, long long b) {return b == 0 ? a : gcd(b, a % b);}
};

4、复杂度分析

时间复杂度：

• 外层循环：遍历所有可能的子数组起点 O(n)；
• 内层循环：遍历每个起点对应的终点，最坏情况下是 O(n)；
• 动态更新 LCM 和 GCD 的复杂度约为 $O(\log (\text{maxElement}))$。
  综合复杂度为 $O(n^2\log (\text{maxElement}))$。

空间复杂度：
使用常量辅助空间，因此空间复杂度为 O(1)。

Q2、计算字符串的镜像分数

1、题目描述

给你一个字符串 s。

英文字母中每个字母的 镜像 定义为反转字母表之后对应位置上的字母。例如，'a' 的镜像是 'z'，'y' 的镜像是 'b'。

最初，字符串 s 中的所有字符都 未标记 。

字符串 s 的初始分数为 0 ，你需要对其执行以下过程：

• 从左到右遍历字符串。
• 对于每个下标 i ，找到距离最近的 未标记 下标 j，下标 j 需要满足 j < i 且 s[j] 是 s[i] 的镜像。然后 标记 下标 i 和 j，总分加上 i - j 的值。
• 如果对于下标 i，不存在满足条件的下标 j，则跳过该下标，继续处理下一个下标，不需要进行标记。

返回最终的总分。

2、解题思路

初始化数据结构：

• 使用一个大小为 26 的向量 charStacks，其中每个元素是一个栈，表示英文字母从 'a' 到 'z' 的未标记位置索引。
• 用变量 totalScore 记录最终分数。

遍历字符串：

• 遍历字符串的每个字符，计算其索引和镜像索引。
• 如果当前字符的镜像栈中有元素 (存在未标记的镜像字符索引)，从镜像栈中弹出栈顶元素，计算得分并累加到 totalScore。
• 如果镜像栈为空，则将当前字符索引压入该字符的栈中。

返回总分：

• 遍历完成后，totalScore 即为最终结果。

3、代码实现

class Solution {
public:long long calculateScore(string s) {// 使用26个栈, 分别对应 a-z 的字符vector<stack<int>> charStacks(26);long long totalScore = 0; // 记录总得分// 遍历字符串中的每个字符for (int index = 0; index < s.size(); ++index) {int currentChar = s[index] - 'a';         // 当前字符的索引 (0-25)int complementaryChar = 25 - currentChar; // 互补字符的索引 (0-25)// 如果互补字符的栈不为空, 则可以匹配, 计算得分if (!charStacks[complementaryChar].empty()) {// 计算当前得分: 当前索引减去互补字符的最近索引totalScore += index - charStacks[complementaryChar].top();// 弹出互补字符的栈顶元素 (标记为已使用)charStacks[complementaryChar].pop();} else {// 否则, 将当前字符的索引压入对应栈charStacks[currentChar].push(index);}}return totalScore; // 返回总得分}
};

4、复杂度分析

时间复杂度：
每个字符在遍历过程中只会被压栈和弹栈一次，时间复杂度为 O(n)。

空间复杂度：
需要额外的 26 个栈，每个栈的大小总和不超过 n，空间复杂度为 O(n)。

Q3、收集连续 K 个袋子可以获得的最多硬币数量

1、题目描述

在一条数轴上有无限多个袋子，每个坐标对应一个袋子。其中一些袋子里装有硬币。

给你一个二维数组 coins，其中 coins[i] = [li, ri, ci] 表示从坐标 li 到 ri 的每个袋子中都有 ci 枚硬币。

数组 coins 中的区间互不重叠。

另给你一个整数 k。

返回通过收集连续 k 个袋子可以获得的 最多 硬币数量。

2、解题思路

滑动窗口法

由于地毯覆盖的是连续的袋子，因此我们可以用 滑动窗口 来计算当前地毯位置下的硬币总和，并动态调整窗口以获取最大硬币数。

• 使用窗口 [left, right] 表示当前地毯覆盖的范围。
• 窗口右边界扩展：每次将当前区间的硬币加入到总和中。
• 窗口左边界收缩：当地毯的覆盖范围超过 k 时，移除左边部分的硬币。

双向覆盖

为了考虑不同覆盖方向（从左到右，从右到左）的影响，算法需要：

1. 按照区间起点升序排序，计算从左到右的最大覆盖硬币数。
2. 将区间起点和终点取反后再次排序，计算从右到左的最大覆盖硬币数。

最终结果为两种覆盖方向的最大值。

3、代码实现

class Solution {
public:long long maximumCoins(vector<vector<int>>& coins, int carpetLen) {// 按起点升序排序区间, 方便从左到右计算sort(coins.begin(), coins.end());// 计算从左到右的最大硬币覆盖数量long long maxCoins = calculateMaxCoins(coins, carpetLen);// 反转每个区间的起点和终点for (auto& tile : coins) {int temp = tile[0];tile[0] = -tile[1];         // 起点变为负的终点tile[1] = -temp;            // 终点变为负的起点}// 按新起点升序排序区间, 方便从右到左计算sort(coins.begin(), coins.end());// 计算从右到左的最大硬币覆盖数量, 并更新最终结果maxCoins = max(maxCoins, calculateMaxCoins(coins, carpetLen));return maxCoins;}private:// 计算滑动窗口内的最大硬币覆盖数量long long calculateMaxCoins(const vector<vector<int>>& tiles, int carpetLen) {long long maxCovered = 0;       // 记录最大覆盖硬币数long long currentCovered = 0;   // 当前窗口的硬币总数int left = 0;                   // 左指针, 表示窗口的起始位置// 遍历每个区间, 调整滑动窗口for (int right = 0; right < tiles.size(); ++right) {int start = tiles[right][0]; // 当前区间的起始位置int end = tiles[right][1];   // 当前区间的终点位置int coins = tiles[right][2]; // 当前区间的硬币数// 增加当前区间的硬币到窗口总和currentCovered += static_cast<long long>(end - start + 1) * coins;// 如果当前窗口超出地毯长度, 收缩左指针while (tiles[left][1] + carpetLen - 1 < end) {int leftStart = tiles[left][0];int leftEnd = tiles[left][1];int leftCoins = tiles[left][2];// 减去左指针对应的硬币数currentCovered -= static_cast<long long>(leftEnd - leftStart + 1) * leftCoins;++left; // 左指针右移}// 计算当前窗口的未完全覆盖部分, 并更新最大覆盖硬币数long long uncovered = max(static_cast<long long>(end - carpetLen + 1 - tiles[left][0]) * tiles[left][2], 0LL);maxCovered = max(maxCovered, currentCovered - uncovered);}return maxCovered; // 返回当前方向的最大硬币覆盖数}
};

4、复杂度分析

时间复杂度：

• 排序：两次排序，时间复杂度为 $O(n\log n)$，其中 n 是区间数量。
• 滑动窗口：遍历每个区间的右边界，时间复杂度为 $O(n)$。
• 总时间复杂度为 $O(n\log n)$。

空间复杂度：

• 使用了辅助变量和少量指针，空间复杂度为 $O(1)$。

Q4、不重叠区间的最大得分

1、题目描述

给你一个二维整数数组 intervals，其中 intervals[i] = [li, ri, weighti]。区间 i 的起点为 li，终点为 ri，权重为 weighti。你最多可以选择 4 个互不重叠 的区间。所选择区间的 得分 定义为这些区间权重的总和。

返回一个至多包含 4 个下标且字典序最小的数组，表示从 intervals 中选中的互不重叠且得分最大的区间。

如果两个区间没有任何重叠点，则称二者 互不重叠 。特别地，如果两个区间共享左边界或右边界，也认为二者重叠。

数组 a 的字典序小于数组 b 的前提是：当在第一个不同的位置上，a 的元素小于 b 的对应元素。如果前 min(a.length, b.length) 个元素均相同，则较短的数组字典序更小。

2、解题思路

1. 预处理与排序：

   • 将输入数据转换为结构体数组以便操作。

   • 按区间的 右端点升序 排序，方便后续计算前一个不重叠区间。

2. 动态规划：

   • 定义 dp[i][j] 表示前 i 个区间中选择 j 个的最大权重及对应区间索引。

   • 对于每个区间，既可以选择，也可以不选择；需要比较两种情况：

     • 不选择：直接继承前一个状态。
     • 选择：通过二分找到最后一个不与当前区间重叠的区间，加上当前权重。
     • 若两种选择的权重相等，则选择字典序更小的方案。

3. 回溯最优解：

   • 最终结果是 dp[n][4]，即前 n 个区间中选择最多 4 个的最优解。

3、代码实现

class Solution {
private:struct Interval {int start;  // 区间起点int end;    // 区间终点int weight; // 区间权重int index;  // 区间索引};public:vector<int> maximumWeight(vector<vector<int>>& intervals) {int n = intervals.size();// 1. 将输入的二维数组转换为结构体数组, 便于操作vector<Interval> sortedIntervals(n);for (int i = 0; i < n; ++i) {sortedIntervals[i] = {intervals[i][0], intervals[i][1], intervals[i][2], i};}// 2. 按区间的右端点升序排序sort(sortedIntervals.begin(), sortedIntervals.end(),[](const Interval& a, const Interval& b) {return a.end < b.end;});// 3. 动态规划表, dp[i][j] 表示前 i 个区间选择 j 个的最大权重及对应区间索引vector<array<pair<long long, vector<int>>, 5>> dp(n + 1);for (int i = 0; i < n; ++i) {const auto& current = sortedIntervals[i];// 找到当前区间左端点之前结束的最近区间索引int previous = lower_bound(sortedIntervals.begin(), sortedIntervals.begin() + i, current.start,[](const Interval& interval, int value) {return interval.end < value;}) - sortedIntervals.begin();for (int j = 1; j < 5; ++j) {// 不选当前区间的情况long long excludeWeight = dp[i][j].first;// 选当前区间的情况long long includeWeight = dp[previous][j - 1].first + current.weight;// 如果选择当前区间更优, 则更新 DP 表if (excludeWeight < includeWeight) {vector<int> newIndices = dp[previous][j - 1].second;newIndices.push_back(current.index);sort(newIndices.begin(), newIndices.end()); // 保持字典序// 更新权重和区间索引dp[i + 1][j] = {includeWeight, newIndices};} else if (excludeWeight > includeWeight) {// 如果不选当前区间更优，则继承上一步的状态dp[i + 1][j] = dp[i][j];} else {// 如果两种选择权重相等, 选择字典序更小的方案vector<int> newIndices = dp[previous][j - 1].second;newIndices.push_back(current.index);sort(newIndices.begin(), newIndices.end()); // 保持字典序if (dp[i][j].second < newIndices) {dp[i + 1][j] = dp[i][j];} else {dp[i + 1][j] = {includeWeight, newIndices};}}}}// 4. 返回选择 4 个区间时的区间索引return dp[n][4].second;}
};

4、时间复杂度分析

1. 排序： $O(n\log n)$
2. 动态规划： $O(n\times 4\times \log n)$，二分查找的复杂度为 $O(\log n)$。
3. 总复杂度： $O(n\log n)$