Q1、统计符合条件长度为3的子数组数目

1、题目描述

给你一个整数数组 nums ，请你返回长度为 3 的子数组，满足第一个数和第三个数的和恰好为第二个数的一半。

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

2、解题思路

我们需要在给定的数组 nums 中找出长度为 3 的子数组（即三个连续元素的子数组），满足以下条件：

• 第一个数（nums[i-2]）与第三个数（nums[i]）的和，恰好是第二个数（nums[i-1]）的一半。

换句话说，对于任意满足条件的子数组 [nums[i-2], nums[i-1], nums[i]]，需要满足数学关系：

​ $$nums[i-2]+nums[i]=\frac{nums[i-1]}{2}$$

或等价地：

​ $$(nums[i-2]+nums[i])\times 2=nums[i-1]$$

连续子数组的定义：

• 一个长度为 3 的子数组是数组中的三个连续元素。即对于数组 nums 的一个长度为 3 的子数组 [nums[i-2], nums[i-1], nums[i]]，三个数的索引分别是 i-2, i-1, i。

条件判断：

• 对于每一个可能的长度为 3 的子数组，只需要检查是否满足上述等式。
• 注意，由于需要三个元素，数组的长度必须至少为 3。如果 nums.size() < 3，直接返回 0。

遍历方法：

• 从索引 i = 2 开始，检查 [nums[i-2], nums[i-1], nums[i]] 是否满足条件。
• 遍历到数组的末尾，并统计所有满足条件的子数组的个数。

时间复杂度：

• 由于我们只需遍历数组一次，对每个子数组执行一次常数时间的计算，时间复杂度为 O(n)，其中 n 是数组的长度。

3、代码实现

class Solution {
public:int countSubarrays(vector<int>& nums) {int n = nums.size();// 如果数组长度小于 3, 直接返回 0if (n < 3) {return 0;}int ret = 0; // 记录满足条件的子数组个数// 从索引 2 开始遍历数组, 检查每个长度为 3 的子数组for (int i = 2; i < n; ++i) {// 检查条件 (nums[i-2] + nums[i]) * 2 == nums[i-1]if ((nums[i - 2] + nums[i]) * 2 == nums[i - 1]) {++ret; // 满足条件的子数组个数 +1}}return ret; // 返回最终结果}
};

4、复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

Q2、统计异或值为给定值的路径数目

1、题目描述

给你一个大小为 m x n 的二维整数数组 grid 和一个整数 k 。

你的任务是统计满足以下 条件 且从左上格子 (0, 0) 出发到达右下格子 (m - 1, n - 1) 的路径数目：

• 每一步你可以向右或者向下走，也就是如果格子存在的话，可以从格子 (i, j) 走到格子 (i, j + 1) 或者格子 (i + 1, j) 。
• 路径上经过的所有数字 XOR 异或值必须 等于 k 。

请你返回满足上述条件的路径总数。

由于答案可能很大，请你将答案对 1e9 + 7 取余 后返回。

2、解题思路

我们需要计算从二维数组 grid 的左上角 (0, 0) 出发到右下角 (m-1, n-1) 的所有路径中，路径上所有数字异或值等于 k 的路径数。

关键点分析

1. 路径定义：
   • 每次可以向右或向下移动，因此路径会从 (0, 0) 到 (m-1, n-1)，只能通过这两种移动方式到达目标。
2. 异或值：
   • 对于路径上的所有数字 $a_1,a_2,\dots ,a_n$ ，路径的异或值是 $a_1\oplus a_2\oplus \cdots \oplus a_n$ ，其中 $\oplus$ 表示按位异或操作。
3. 目标：
   • 找出满足异或值 =k 的路径数。
4. 动态规划思路：
   • 定义状态：dp[i][j][x] 表示从 (0, 0) 出发到达格子 (i, j) 且路径异或值为 x 的路径数。
   • 转移方程：可以从上方或左侧到达 (i, j)，并更新路径异或值。
   • 初始化：起点 (0, 0) 的路径异或值为 grid[0][0]，路径数为 1。
   • 结果：返回 dp[m-1][n-1][k]。
5. 注意点：
   • 路径数可能非常大，因此每次计算结果需要对 $10^9+7$ 取模。
   • 为了处理路径异或值，使用哈希表存储当前异或值对应的路径数。

动态规划详细过程

1. 状态定义

dp[i][j][x] 表示从 (0, 0) 出发到达 (i, j) 且路径异或值为 x 的路径数。

2. 状态转移

对于每个格子 (i, j)：

1. 如果从上方 (i-1, j) 到达：
   • 异或值为 x，更新：dp[i][j][x ^ grid[i][j]] += dp[i-1][j][x]。
2. 如果从左侧 (i, j-1) 到达：
   • 异或值为 x，更新：dp[i][j][x ^ grid[i][j]] += dp[i][j-1][x]。

最终状态需要对 $10^9+7$ 取模。

3. 初始化

• 起点 (0, 0) 的初始状态：dp[1][1][grid[0][0]] = 1。

4. 结果

• 返回右下角 (m-1, n-1) 的路径异或值为 k 的路径数，即：dp[m][n][k]。

3、代码实现

class Solution {
public:const int mod = 1e9 + 7;int countPathsWithXorValue(vector<vector<int>>& grid, int k) {int row = grid.size();int col = grid[0].size();// 定义 dp 数组, dp[i][j] 是一个哈希表, 存储路径异或值及其路径数vector<vector<unordered_map<int, int>>> dp(row + 1, vector<unordered_map<int, int>>(col + 1));// 初始化起点dp[1][1][grid[0][0]] = 1;// 遍历每个格子for (int i = 1; i <= row; ++i) {for (int j = 1; j <= col; ++j) {// 当前格子值int currentVal = grid[i - 1][j - 1];// 从上方转移到当前格子for (const auto& kv : dp[i - 1][j]) {int xorVal = kv.first ^ currentVal;dp[i][j][xorVal] += kv.second;dp[i][j][xorVal] %= mod;}// 从左侧转移到当前格子for (const auto& kv : dp[i][j - 1]) {int xorVal = kv.first ^ currentVal;dp[i][j][xorVal] += kv.second;dp[i][j][xorVal] %= mod;}}}// 返回右下角格子中异或值为 k 的路径数return dp[row][col][k];}
};

4、复杂度分析

时间复杂度：

• 遍历每个格子 (i, j)：O(m×n)。
• 对于每个格子的哈希表操作，最坏情况是路径异或值的取值范围较大，复杂度为 O(X)，其中 X 是最大可能的异或值范围（通常较小）。
• 总时间复杂度为 O(m×n×X)。

空间复杂度：

• 每个格子存储一个哈希表，空间复杂度为 O(m×n×X)。

Q3、判断网格图能否被切割成块

1、题目描述

给你一个整数 n 表示一个 n x n 的网格图，坐标原点是这个网格图的左下角。同时给你一个二维坐标数组 rectangles ，其中 rectangles[i] 的格式为 [startx, starty, endx, endy] ，表示网格图中的一个矩形。每个矩形定义如下：

• (startx, starty)：矩形的左下角。
• (endx, endy)：矩形的右上角。

注意 ，矩形相互之间不会重叠。你的任务是判断是否能找到两条 要么都垂直要么都水平 的 两条切割线 ，满足：

• 切割得到的三个部分分别都 至少 包含一个矩形。
• 每个矩形都 恰好仅 属于一个切割得到的部分。

如果可以得到这样的切割，请你返回 true ，否则返回 false 。

2、解题思路

1. 按照 x- 坐标和 y- 坐标分开处理

我们将矩形的范围分解为以下两类：

• 水平维度：通过矩形的 x- 范围 [startx, endx]。
• 垂直维度：通过矩形的 y- 范围 [starty, endy]。

通过分别在水平和垂直维度判断是否能形成至少 3 个独立区域，我们只要任一维度满足条件即可返回 true。

2. 如何判断独立区域

• 排序后贪心算法：
  • 将所有矩形的范围按起点进行排序。
  • 遍历排序后的范围，用变量 right 跟踪当前范围的右边界。
  • 当遇到一个新的范围起点大于 right 时，说明该范围与之前的区域不重叠，可以算作一个新的独立区域。
  • 每次增加一个独立区域计数器 num，当 num >= 3 时即可返回 true。

3. 处理步骤

• 构造两个范围数组：
  • v1：存储所有矩形的水平范围 [startx, endx]。
  • v2：存储所有矩形的垂直范围 [starty, endy]。
• 分别对 v1 和 v2 进行独立区域计数，任意一个维度满足条件即可。

4. 类似题目 – 合并区间

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {int n = intervals.size();if (n == 0) {return {};}sort(intervals.begin(), intervals.end());vector<vector<int>> ret;for (int i = 0; i < n; i++) {int left = intervals[i][0], right = intervals[i][1];if (ret.empty() || ret.back()[1] < left) {ret.push_back({left, right});} else {ret.back()[1] = max(ret.back()[1], right);}}return ret;}
};

class Solution {
public:bool checkValidCuts(int n, vector<vector<int>>& rectangles) {vector<vector<int>> v1, v2;for (const auto& rect : rectangles) {v1.push_back({rect[0], rect[2]});v2.push_back({rect[1], rect[3]});}sort(v1.begin(), v1.end());vector<vector<int>> ret1;for (int i = 0; i < v1.size(); i++) {int left = v1[i][0], right = v1[i][1];if (ret1.empty() || ret1.back()[1] <= left) {ret1.push_back({left, right});} else {ret1.back()[1] = max(ret1.back()[1], right);}if (ret1.size() >= 3) {return true;}}sort(v2.begin(), v2.end());vector<vector<int>> ret2;for (int i = 0; i < v2.size(); i++) {int left = v2[i][0], right = v2[i][1];if (ret2.empty() || ret2.back()[1] <= left) {ret2.push_back({left, right});} else {ret2.back()[1] = max(ret2.back()[1], right);}if (ret2.size() >= 3) {return true;}}return false;}
};

3、代码实现

class Solution {
public:bool checkValidCuts(int n, vector<vector<int>>& rectangles) {// 存储水平和垂直范围vector<vector<int>> v1, v2;// 存储矩形的范围for (const auto& rect : rectangles) {v1.push_back({rect[0], rect[2]}); // 水平范围v2.push_back({rect[1], rect[3]}); // 垂直范围}// 排序水平范围sort(v1.begin(), v1.end());int num = 0;    // 独立区域计数int right = -1; // 当前右边界// 贪心统计独立区域for (const auto& v : v1) {// 新的独立区域if (v[0] >= right) {num++;// 剪枝: 找到 3 个独立区域, 立马结束if (num >= 3) {return true;}}right = max(right, v[1]); // 更新右边界}// 排序垂直范围sort(v2.begin(), v2.end());num = 0;    // 重置计数right = -1; // 重置右边界// 贪心统计独立区域for (const auto& v : v2) {// 新的独立区域if (v[0] >= right) {num++;// 剪枝: 找到 3 个独立区域, 立马结束if (num >= 3) {return true;}}right = max(right, v[1]); // 更新右边界}return false; // 无法找到符合条件的切割}
};

4、复杂度分析

时间复杂度：

• 构造 v1 和 v2：O(m)，其中 m 是矩形数量。
• 排序 v1 和 v2：O(mlog⁡m)。
• 贪心遍历 v1 和 v2：O(m)。
• 总时间复杂度为 O(mlog⁡m)。

空间复杂度：

• 额外存储 v1 和 v2：O(m)。
• 总空间复杂度为 O(m)。

Q4、唯一中间众数子序列 Ⅰ

1、题目描述

给你一个整数数组 nums ，请你求出 nums 中大小为 5 的子序列的数目，它是 唯一中间众数序列 。

由于答案可能很大，请你将答案对 109 + 7 取余 后返回。

众数 指的是一个数字序列中出现次数 最多 的元素。

如果一个数字序列众数只有一个，我们称这个序列有 唯一众数 。

一个大小为 5 的数字序列 seq ，如果它中间的数字（seq[2]）是唯一众数，那么称它是 唯一中间众数 序列。

子序列 指的是将一个数组删除一些（也可以不删除）元素后，剩下元素不改变顺序得到的 非空 数组。

2、解题思路

问题分解

1. 子序列的定义：
   • 子序列可以通过删除原数组中的若干元素（不改变顺序）得到。
   • 因此，对于大小为 n 的数组，总共有 C(n, 5) 个大小为 5 的子序列。
2. 唯一中间众数的定义：
   • 中间元素必须是子序列的众数，且是唯一众数。
   • 为了满足条件，子序列两边的元素不能包含比中间元素更多的重复值。
3. 结果计算：
   • 我们需要计算所有大小为 5 的子序列总数，然后减去不合法的子序列数。

解题思路

1. 总数计算：
   • 总共有 $C(n,5)=\frac{n\cdot (n-1)\cdot (n-2)\cdot (n-3)\cdot (n-4)}{120}$ 个大小为 5 的子序列。
2. 不合法子序列的分类：
   • 仅有一个中间元素：两边元素不足以形成有效的众数。
   • 有两个中间元素：
     • 左右两边元素分布不均，导致中间元素不是唯一众数。
3. 具体实现：
   • 使用前缀计数 preCount 和后缀计数 sufCount，分别记录当前中间元素左右两侧的元素分布。
   • 遍历每个元素作为潜在的中间元素，动态计算不合法方案数。

3、代码实现

class Solution {// 计算组合数 C(n, 2)int comb2(int num) { return num * (num - 1) / 2; }public:int subsequencesWithMiddleMode(vector<int>& nums) {int n = nums.size();const int MOD = 1'000'000'007;// 所有子序列的总数 (长度为 5 的组合)long long totalSubsequences = 1LL * n * (n - 1) * (n - 2) * (n - 3) * (n - 4) / 120;// 用于记录元素的出现次数unordered_map<int, int> preCount, sufCount;for (int x : nums) {sufCount[x]++;}// 用于计算不合法方案auto calculateInvalidSequences = [&](int x, int left, int right) -> long long {long long invalidCount = 0;int pre_x = preCount[x], suf_x = sufCount[x];// 1. 不合法: 只有一个 xinvalidCount += 1LL * comb2(left - pre_x) * comb2(right - suf_x);// 2. 不合法: 只有两个 x, 且至少有两个 y (y != x)for (const auto& [y, suf_y] : sufCount) {if (y == x) {continue;}int pre_y = preCount[y];// a) 左边两个 y, 右边一个 xinvalidCount += 1LL * comb2(pre_y) * suf_x * (right - suf_x);// b) 右边两个 y, 左边一个 xinvalidCount += 1LL * comb2(suf_y) * pre_x * (left - pre_x);// c) 左右各一个 y, 另一个 x 在左边invalidCount += 1LL * pre_y * suf_y * pre_x * (right - suf_x - suf_y);// d) 左右各一个 y，另一个 x 在右边invalidCount += 1LL * pre_y * suf_y * suf_x * (left - pre_x - pre_y);}return invalidCount;};long long validSubsequences = totalSubsequences;// 枚举每个可能的正中间元素 xfor (int left = 0; left < n - 2; left++) {int x = nums[left];sufCount[x]--;if (left > 1) {int right = n - 1 - left;validSubsequences -= calculateInvalidSequences(x, left, right);}preCount[x]++;}return validSubsequences % MOD;}
};

4、复杂度分析

时间复杂度：$O(n^2)$

• 外层遍历所有元素作为中间值 x，复杂度 $O(n)$。
• 内层统计不合法方案，复杂度与不同元素个数 k 成正比，最坏情况下 k = n 。

空间复杂度：$O(n)$

• 主要用于存储 preCount 和 sufCount。