第146场双周赛：统计符合条件长度为3的子数组数目、统计异或值为给定值的路径数目、判断网格图能否被切割成块、唯一中间众数子序列 Ⅰ

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, 直接返回 0
        if (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. 不合法: 只有一个 x
            invalidCount += 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, 右边一个 x
                invalidCount += 1LL * comb2(pre_y) * suf_x * (right - suf_x);

                // b) 右边两个 y, 左边一个 x
                invalidCount += 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;

        // 枚举每个可能的正中间元素 x
        for (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。